wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> take 4 real numbers...
        
(Message started by: BenVitale on May 2^nd, 2010, 11:29am)

Title: take 4 real numbers...
Post by BenVitale on May 2^nd, 2010, 11:29am

Take 4 real numbers x,y,z,u and let "a" be their arithmetical mean.
Below them write the distances they have to a, that is, the 4 numbers
|x-a|,|y-a|,|z-a|,|u-a|.
If you repeat this process a few times, you arrive at 4 zeros
(almost always, there's one exception)

This is similar to Ducci sequences (http://en.wikipedia.org/wiki/Ducci_sequence)

It's easy to find the exception.
Could you prove that the number of steps to arrive at 4 zeros is between 3 and 6?

Could you offer a solution without using programming?

Title: Re: take 4 real numbers...
Post by BenVitale on May 3^rd, 2010, 1:45pm

This property is supposed to hold independently of the size of the numbers we start with.

If three, but not all four, of the numbers we start with are equal, then you never reach zero.

For example, if we take 1 1 1 7, we never reach zero.

I took few examples. In some examples it took me 4 steps, in others it took me a little longer to reach zero.

replacing "a" by the sum x+y+z+u = s
then we continue with the numbers
|4x-s|,|4y-s|,|4z-s|,|4u-s|

Then what? I got nowhere

Title: Re: take 4 real numbers...
Post by towr on May 3^rd, 2010, 2:10pm

on 05/03/10 at 13:45:14, BenVitale wrote:

This property is supposed to hold independently of the size of the numbers we start with.

It would be invariant under both addition and multiplication.
x, y, z, u http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 0, (y-x)/(u-x), (z-x)/(u-x), 1

Title: Re: take 4 real numbers...
Post by towr on May 4^th, 2010, 6:04am

You can make the process take an arbitrary number of steps, by starting with 0,0,1,x where if you pick x = (2 + 4ⁿ)/6, it takes 2n steps before you reach 0,0,0,0.

(I had wanted to prove as intermediate lemma that if you start with two equal values that you will always end up with all zeros. I hoped there would just be a finite number of branches to work through, but instead I ran into this.)

Title: Re: take 4 real numbers...
Post by BenVitale on May 4^th, 2010, 3:38pm

My math prof gave this problem as an assignment. I'm glad that this did not come up a test. The same problem was presented to physics students and computer science students.

The physics students are confused about this problem. So now, it is the math major students(including myself) competing against the computer science students.

Title: Re: take 4 real numbers...
Post by towr on May 5^th, 2010, 2:51am

If you subtract the minimum from the other numbers, the log of the ratio of the maximum two numbers seems to be strictly decreasing over any two steps, and possibly decreases by a fixed minimum amount over every four steps.
If you can prove the latter, then I think you can prove that all numbers become the same (you can at least prove the maximum two become the same, because the log of the ration can't become less than zero. And of course you can reverse the order by multiplying by -1; so you can prove the other two become the same as well. And once you have two pairs, they all become equal, then zero.)

Title: Re: take 4 real numbers...
Post by BenVitale on May 5^th, 2010, 10:38am

I found this problem discussed Here (http://myweb.dal.ca/waue/Trans/Meyer-Fountain-Clausing.pdf)

Title: Re: take 4 real numbers...
Post by Obob on May 5^th, 2010, 11:17am

Very interesting!

Title: Re: take 4 real numbers...
Post by towr on May 5^th, 2010, 11:36am

This should just about suffice. Although it could use some prettifying and tying up of loose ends.

0,0,y,y+d,   y,d > 0
a = (2y+d)/4

1:2y>=d
  2y+d, 2y+d, 2y-d, 2y+3d
  a = 2y+d  

  2: 0,0,2d,2d   (end)

1:2y<=d
  2y+d, 2y+d, d-2y, 2y+3d
  a = 2y+3d/2  

  2:  d-2y, d-2y, 6y+d, 2y+3d 
      a=(3d+2y)/2

  3:10y>=d
    6y+d, 6y+d, 10y-d, 3d+2y
    a=6y+d
    0, 0, 2d-4y, 2d-4y  (end)

  3:10y<=d
    6y+d, 6y+d, d-10y, 3d+2y
    a=(3d+2y)/2
    4:  d-10y, d-10y, d+22y, 3d+2y

(y+d)/y = 1+d/y
(1/16d+6/16y)/y = 1/16 d/y + 6/16 > 1

16(d+y)/(d+6y) > 8/3



0,1,y,y+d+1, y>=1, d>=0
a = (2y+2+d)/4

1:2y>=2+d 
  2y+2+d, 2y-2+d, 2y-2-d, 2y+3d+2
  a=d+2y

  2: 2, 2, 2d+2, 2d+2  (end)

1:2y<=2+d 
  2y+2+d, 2y-2+d, -2y+2+d, 2y+3d+2
  a=(3d+2y+2)/2

  2:2y+2>=d 
    2y+2-d, 6+d-2y, 6y-2+d, 3d+2y+2
    a=d+2y+2

    3:  2d, 4y-4, 4y-4, 2d  (end)

  2:2y+2<=d 
    d-2y-2, 6+d-2y, 6y-2+d, 3d+2y+2
    a=(3d+2y+2)/2

    3:10y>=d+6 
      d+6y+6, d+6y-10, 10y-d-6, 3d+2y+2
      a=d+6y-2
      4:  8, 8, 2d+4-4y, 2d+4-4y  (end)

    3:10y<=d+6 
      d+6y+6, d+6y-10, d+6-10y, 3d+2y+2
      a=(3d+2y+2)/2
      4:10y+10>=d 
        10y+10-d, d+22-10y, d+22y-10, 3d+2y+2
        a=d+6y+6
        5: 2d-4y-4, 16y-16, 16y-16, 2d-4y-4  (end)

      4:10y+10<=d 
        d-10y-10, d+22-10y, d+22y-10, 3d+2y+2
        0, 16, 16y, d+6y+6
        
16(d+(y+1))/(d+6(y+1)) >= 8/3

Title: Re: take 4 real numbers...
Post by towr on May 5^th, 2010, 11:48am

on 05/05/10 at 10:38:45, BenVitale wrote:

I found this problem discussed Here (http://myweb.dal.ca/waue/Trans/Meyer-Fountain-Clausing.pdf)

Interesting article, and a less bloody-minded approach than mine :)

Title: Re: take 4 real numbers...
Post by BenVitale on May 7^th, 2010, 11:40am

Thank you towr.