Author |
Topic: Three Reals On a Blackboard (Read 1510 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Three Reals On a Blackboard
« on: May 5th, 2008, 7:08pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Three Reals On a Blackboard
« Reply #1 on: May 6th, 2008, 4:19am » |
Quote Modify
|
-- 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  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  |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| |B|, so if |B|=0, then we must have x=0
|
| « Last Edit: May 6th, 2008, 4:21am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Three Reals On a Blackboard
« Reply #2 on: May 6th, 2008, 8:24am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Three Reals On a Blackboard
« Reply #3 on: May 6th, 2008, 8:29am » |
Quote Modify
|
on May 6th, 2008, 8:24am, 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.
|
| « Last Edit: May 6th, 2008, 8:30am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Three Reals On a Blackboard
« Reply #4 on: May 6th, 2008, 8:52am » |
Quote Modify
|
Oh, OK. Misread your last post. Thanks for the clarification.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Three Reals On a Blackboard
« Reply #5 on: May 9th, 2008, 3:02am » |
Quote Modify
|
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.
|
| « Last Edit: May 9th, 2008, 4:11pm by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Three Reals On a Blackboard
« Reply #6 on: May 9th, 2008, 3:47am » |
Quote Modify
|
on May 9th, 2008, 3:02am, 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..
|
| « Last Edit: May 9th, 2008, 3:57am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Three Reals On a Blackboard
« Reply #7 on: May 10th, 2008, 12:25am » |
Quote Modify
|
Eigenray must be widely smiling  . 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. ... Always choose pair of reals with accompanying integers with different signs. This reduces sum of accompanying integers absolute values.
|
| « Last Edit: May 10th, 2008, 7:39am by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Three Reals On a Blackboard
« Reply #8 on: May 10th, 2008, 1:32am » |
Quote Modify
|
on May 10th, 2008, 12:25am, Hippo wrote:| Always choose pair of reals with occompanying integers with different signs. This reduces sum of accompaniing integers absolute values. |
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Three Reals On a Blackboard
« Reply #9 on: May 10th, 2008, 7:39am » |
Quote Modify
|
Oops, you are right ... I will return to it.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Three Reals On a Blackboard
« Reply #10 on: May 10th, 2008, 11:04am » |
Quote Modify
|
on May 9th, 2008, 3:47am, towr wrote:| My contention is you can at each step bring one of the accompanying integers closer to 0. |
|
Precisely.
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|  A, |B-C| B,
no?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Three Reals On a Blackboard
« Reply #11 on: May 10th, 2008, 1:06pm » |
Quote Modify
|
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 
|
| « Last Edit: May 20th, 2008, 2:06am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print