Difference between revisions of "2008 USAMO Problems/Problem 5"
(spliced work by t0rajir0u, jb05, not sure if its complete or not) |
|||
(5 intermediate revisions by 4 users not shown) | |||
Line 2: | Line 2: | ||
(''Kiran Kedlaya'') Three nonnegative real numbers <math>r_1</math>, <math>r_2</math>, <math>r_3</math> are written on a blackboard. These numbers have the property that there exist integers <math>a_1</math>, <math>a_2</math>, <math>a_3</math>, not all zero, satisfying <math>a_1r_1 + a_2r_2 + a_3r_3 = 0</math>. We are permitted to perform the following operation: find two numbers <math>x</math>, <math>y</math> on the blackboard with <math>x \le y</math>, then erase <math>y</math> and write <math>y - x</math> in its place. Prove that after a finite number of such operations, we can end up with at least one <math>0</math> on the blackboard. | (''Kiran Kedlaya'') Three nonnegative real numbers <math>r_1</math>, <math>r_2</math>, <math>r_3</math> are written on a blackboard. These numbers have the property that there exist integers <math>a_1</math>, <math>a_2</math>, <math>a_3</math>, not all zero, satisfying <math>a_1r_1 + a_2r_2 + a_3r_3 = 0</math>. We are permitted to perform the following operation: find two numbers <math>x</math>, <math>y</math> on the blackboard with <math>x \le y</math>, then erase <math>y</math> and write <math>y - x</math> in its place. Prove that after a finite number of such operations, we can end up with at least one <math>0</math> on the blackboard. | ||
− | == Solution == | + | == Solutions == |
+ | |||
+ | === Solution === | ||
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 a rational number 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. |
+ | |||
+ | |||
− | |||
− | |||
− | |||
+ | == See also == | ||
* <url>viewtopic.php?t=202910 Discussion on AoPS/MathLinks</url> | * <url>viewtopic.php?t=202910 Discussion on AoPS/MathLinks</url> | ||
+ | |||
+ | {{USAMO newbox|year=2008|num-b=4|num-a=6}} | ||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 23:37, 21 July 2020
Contents
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.
Solutions
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 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.
See also
- <url>viewtopic.php?t=202910 Discussion on AoPS/MathLinks</url>
2008 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.