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

        riddles >> hard >> Three Reals On a Blackboard
        
(Message started by: william wu on May 5th, 2008, 7:08pm)
Title: Three Reals On a Blackboard
Post by william wu on May 5th, 2008, 7:08pm
Three nonnegative real numbers r1, r2, r3 are written on a blackboard. These numbers have the property that there exist integers a1, a2, a3, not all zero, satisfying

a1 r1 +a2 r2 +a3 r3 = 0.

We are permitted to perform the following operation: find two numbers x, y on the blackboard with x <= y, then erase y and write y - x in its place. Prove that after a finite number of such operations, we can end up with at least one 0 on the blackboard.

Source: USAMO 2008
Title: Re: Three Reals On a Blackboard
Post by towr on May 6th, 2008, 4:19am
[hide]-- If two of the integers are 0, then the other real must be 0 (because it's integer factor can't be)

-- If none of the integers is 0, we can make one 0 in a finite number of steps using the process of replacing y by y-x. (To be proven.)

-- If one of the integers is 0, then we can disregard that term entirely and work only with the other two, see below

Let's suppose we have Ax + By = 0
If x=y, then we're done
So x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif y. WLOG assume 0 < x < y, then |A| > |B| and sign(A) = -sign(B)
We then take one step to get
(A+B)x + B(y-x) = 0 with 0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif |A+B| < |A|
So each step |A|+|B| decreases in integer decrements, with 0 as lower limit. Therefore the process ends. But unless x=y (which is already taken care of), we have |A| http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif |B|, so if |B|=0, then we must have x=0[/hide]
Title: Re: Three Reals On a Blackboard
Post by Obob on May 6th, 2008, 8:24am
The only thing the problem asks is to make one of the numbers zero in a finite number of steps.  So all analysis in cases where there is already a zero is moot.
Title: Re: Three Reals On a Blackboard
Post by towr on May 6th, 2008, 8:29am

on 05/06/08 at 08:24:09, Obob wrote:
The only thing the problem asks is to make one of the numbers zero in a finite number of steps.  So all analysis in cases where there is already a zero is moot.
It asks to make one of the reals 0; so the cases where one of the integers (which aren't on the board but merely exist) is 0 is not moot.
Title: Re: Three Reals On a Blackboard
Post by Obob on May 6th, 2008, 8:52am
Oh, OK.  Misread your last post.  Thanks for the clarification.
Title: Re: Three Reals On a Blackboard
Post by Hippo on May 9th, 2008, 3:02am
I just started to think about it ... it seems to me the real numbers got only integral linear combinations of original values.
What would be sufficient to show is that only finite number of such combinations (whose are lexicographically smaller than the original values) exist. (Each replacement creates lexicographically smaller combination). ...
[edit]Actually we can consider the sum of the reals, it decreases at each step, so if there is only finite number of such linear combinations ...[/edit]

towr: It seems to me we cannot choose the sequence of operations, we should work with all possible choices.
So I don't agree with your reduction from 3 to 2 reals.
Title: Re: Three Reals On a Blackboard
Post by towr on May 9th, 2008, 3:47am

on 05/09/08 at 03:02:50, Hippo wrote:
towr: It seems to me we cannot choose the sequence of operations, we should work with all possible choices.
So I don't agree with your reduction from 3 to 2 reals.
My contention is you can  at each step bring one of the accompanying integers closer to 0. So in a finite number of steps one of them will be zero, and then you focus on the other two. (I suppose I needn't even have split it up; but it's simpler to do for two)

Of course, I still need to prove it..
Title: Re: Three Reals On a Blackboard
Post by Hippo on May 10th, 2008, 12:25am
Eigenray must be widely smiling  ;D. Of course starting with 1, \sqrt 2, and 1+\sqrt 2 allows you infinite sequence of moves.

So your understanding is correct. Riddle asks whether there exists short path. But such riddle does not belong to hard. ... [hide]Always choose pair of reals with accompanying integers with different signs. This reduces sum of accompanying integers absolute values[/hide].
Title: Re: Three Reals On a Blackboard
Post by towr on May 10th, 2008, 1:32am

on 05/10/08 at 00:25:33, Hippo wrote:
[hide]Always choose pair of reals with occompanying integers with different signs. This reduces sum of accompaniing integers absolute values[/hide].
Actually, it's not quite that simple. Because given two integers of opposite sign you operate on, you don't have the choice which of the two can be replaced.
Suppose we have 5 and -11, and the 5 will be replaced: |5 - 11| > |5|
It remains to be proven that you can (if need be in multiple steps) make a choice that reduces the sum of absolute values.

I haven't got my notes with me, but If I recall, these are the cases that are problematic:
Ax+By-Cz with A < C, B < C
Ax-By+Cz with A < B, B < C
(where x<y<z are the reals and A,B,C are positive integers)

I thought I had the first one in two steps, but in between the order changes, and I hadn't accounted for that.
Title: Re: Three Reals On a Blackboard
Post by Hippo on May 10th, 2008, 7:39am
Oops, you are right ... I will return to it.
Title: Re: Three Reals On a Blackboard
Post by Eigenray on May 10th, 2008, 11:04am

on 05/09/08 at 03:47:06, towr wrote:
My contention is you can at each step bring one of the accompanying integers closer to 0.

[hide]Precisely[/hide].


Quote:
I haven't got my notes with me, but If I recall, these are the cases that are problematic:
Ax+By-Cz with A < C, B < C
Ax-By+Cz with A < B, B < C

You almost have it.  But I think you should be considering, e.g.,
Ax+By-Cz = 0, with |A-C| http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif A,  |B-C| http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif B,
no?
Title: Re: Three Reals On a Blackboard
Post by Hippo on May 10th, 2008, 1:06pm
Let 0<x1<x2<x3 be the reals. Let \sumi<=3 aixi=0 for integers ai.

Let ai is the integer whose sign differs from the others. If i<3 clearly |ai| > |a3| therefore you can decrease x3 by xi and ai by a3.

Suppose i=3. If for j<3 2|aj|>|a3| we can decrease x3 by xj and aj by a3 absolute value of aj is decreased.

What remains? For j<3 2|aj|<=|a3|. But than 2\sum j<3 |aj|xj<2|a3|x3. Contradiction.

BTW: Yes ... trivial for Eigenray ... as expected ;)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board