2008 USAMO Problems/Problem 5

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.

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.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

2008 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2008 USAMO Problems/Problem 5

Problem

Solution

See Also