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.
  
__TOC__
+
== Solutions ==
== Solution ==
 
=== Solution 1 ===
 
=== Solution 2 ===
 
  
{{alternate 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>
  
== Resources ==
 
 
{{USAMO newbox|year=2008|num-b=4|num-a=6}}
 
{{USAMO newbox|year=2008|num-b=4|num-a=6}}
 
* <url>Forum/viewtopic.php?t=202910 Discussion on AoPS/MathLinks</url>
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 22:37, 21 July 2020

Problem

(Kiran Kedlaya) Three nonnegative real numbers $r_1$, $r_2$, $r_3$ are written on a blackboard. These numbers have the property that there exist integers $a_1$, $a_2$, $a_3$, not all zero, satisfying $a_1r_1 + a_2r_2 + a_3r_3 = 0$. We are permitted to perform the following operation: find two numbers $x$, $y$ on the blackboard with $x \le 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.

Solutions

Solution

Every time we perform an operation on the numbers on the blackboard $R = \left < r_1, r_2, r_3 \right >$, we perform the corresponding operation on the integers $A = \left < a_1, a_2, a_3 \right >$ so that $R \cdot A = 0$ continues to hold. (For example, if we replace $r_1$ with $r_1 - r_2$ then we replace $a_2$ with $a_1 + a_2$.)

It's possible to show we can always pick an operation so that $|A|^2$ is strictly decreasing. Without loss of generality, let $r_3 > r_2 > r_1$ and $a_3$ be positive. Then it cannot be true that both $a_1$ and $a_2$ are at least $\frac { - a_3}{2}$, or else $a_1r_1 + a_2r_2 + a_3r_3 > 0$. Without loss of generality, let $a_1 < \frac { - a_3}{2}$. Then we can replace $a_1$ with $a_1 + a_3$ and $r_3$ with $r_3 - r_1$ to make $|A|$ smaller. Since it is a strictly decreasing sequence of positive integers, after a finite number of operations we have $a_3 = 0$. We can now see that this result holds for $(r_1,r_2,0)$ if and only if it holds for $(1,\frac{r_2}{r_1},0)$. We can see that $\frac{r_2}{r_1}$ is a rational number given that $a_3$ = 0. It is a well known result of the euclidean algorithm that if we continue to perform these operations, $r_1$ or $r_2$ will eventually be 0.



See also

  • <url>viewtopic.php?t=202910 Discussion on AoPS/MathLinks</url>
2008 USAMO (ProblemsResources)
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. AMC logo.png