2008 USAMO Problems/Problem 5
(Kiran Kedlaya) Three nonnegative real numbers , , are written on a blackboard. These numbers have the property that there exist integers , , , not all zero, satisfying . We are permitted to perform the following operation: find two numbers , on the blackboard with , then erase and write in its place. Prove that after a finite number of such operations, we can end up with at least one on the blackboard.
Every time we perform an operation on the numbers on the blackboard , we perform the corresponding operation on the integers so that continues to hold. (For example, if we replace with then we replace with .)
It's possible to show we can always pick an operation so that is strictly decreasing. Without loss of generality, let and be positive. Then it cannot be true that both and are at least , or else . Without loss of generality, let . Then we can replace with and with to make smaller. Since it is a strictly decreasing sequence of positive integers, after a finite number of operations we have . We can now see that this result holds for if and only if it holds for . We can see that is a rational number given that = 0. It is a well known result of the euclidean algorithm that if we continue to perform these operations, or will eventually be 0.
- <url>viewtopic.php?t=202910 Discussion on AoPS/MathLinks</url>
|2008 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|