Difference between revisions of "2008 USAMO Problems/Problem 5"
(→Resources: => see also) |
|||
Line 5: | Line 5: | ||
Every time we perform an operation on the numbers on the blackboard <math>R = \left < r_1, r_2, r_3 \right ></math>, we perform the corresponding operation on the integers <math>A = \left < a_1, a_2, a_3 \right ></math> so that <math>R \cdot A = 0</math> continues to hold. (For example, if we replace <math>r_1</math> with <math>r_1 - r_2</math> then we replace <math>a_2</math> with <math>a_1 + a_2</math>.) | Every time we perform an operation on the numbers on the blackboard <math>R = \left < r_1, r_2, r_3 \right ></math>, we perform the corresponding operation on the integers <math>A = \left < a_1, a_2, a_3 \right ></math> so that <math>R \cdot A = 0</math> continues to hold. (For example, if we replace <math>r_1</math> with <math>r_1 - r_2</math> then we replace <math>a_2</math> with <math>a_1 + a_2</math>.) | ||
− | It's possible to show we can always pick an operation so that <math>|A|^2</math> is strictly decreasing. [[Without loss of generality]], let <math>r_3 > r_2 > r_1</math> and <math>a_3</math> be positive. Then it cannot be true that both <math>a_1</math> and <math>a_2</math> are at least <math>\frac { - a_3}{2}</math>, or else <math>a_1r_1 + a_2r_2 + a_3r_3 > 0</math>. Without loss of generality, let <math>a_1 < \frac { - a_3}{2}</math>. Then we can replace <math>a_1</math> with <math>a_1 + a_3</math> and <math>r_3</math> with <math>r_3 - r_1</math> to make <math>|A|</math> smaller. Since it is a strictly decreasing sequence of positive integers, after a finite number of operations we have <math> | + | It's possible to show we can always pick an operation so that <math>|A|^2</math> is strictly decreasing. [[Without loss of generality]], let <math>r_3 > r_2 > r_1</math> and <math>a_3</math> be positive. Then it cannot be true that both <math>a_1</math> and <math>a_2</math> are at least <math>\frac { - a_3}{2}</math>, or else <math>a_1r_1 + a_2r_2 + a_3r_3 > 0</math>. Without loss of generality, let <math>a_1 < \frac { - a_3}{2}</math>. Then we can replace <math>a_1</math> with <math>a_1 + a_3</math> and <math>r_3</math> with <math>r_3 - r_1</math> to make <math>|A|</math> smaller. Since it is a strictly decreasing sequence of positive integers, after a finite number of operations we have <math>a_3 = 0</math>. We can now see that this result holds for <math>(r_1,r_2,0)</math> if and only if it holds for <math>(1,\frac{r_2}{r_1},0)</math>. We can see that <math>\frac{r_2}{r_1}</math> is an integer given that <math>a_3</math> = 0. It is a well known result of the euclidean algorithm that if we continue to perform these operations, <math>r_1</math> or <math>r_2</math> will eventually be 0. |
{{alternate solutions}} | {{alternate solutions}} |
Revision as of 15:31, 21 March 2012
Problem
(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.
Solution
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 an integer 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.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
2008 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |