Difference between revisions of "2008 USAMO Problems/Problem 5"
(create template) |
|||
(7 intermediate revisions by 6 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. | ||
− | + | == 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>.) | ||
+ | |||
+ | 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> | ||
− | |||
{{USAMO newbox|year=2008|num-b=4|num-a=6}} | {{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 22:37, 21 July 2020
Contents
[hide]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.