Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 USAMO Problems/Problem 5"

(spliced work by t0rajir0u, jb05, not sure if its complete or not)
(→‎Resources: => see also)
Line 9: Line 9:
 
{{alternate solutions}}
 
{{alternate solutions}}
  
−
== Resources ==
+
== See Also ==
 
{{USAMO newbox|year=2008|num-b=4|num-a=6}}
 
{{USAMO newbox|year=2008|num-b=4|num-a=6}}
−
 
−
* <url>viewtopic.php?t=202910 Discussion on AoPS/MathLinks</url>
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Revision as of 12:57, 6 June 2011

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|^2 = 1$, so $A$ is some permutation of $\left < 1, 0, 0 \right >$ and $R \cdot A = 0$ gives the desired result. Template:Incomplete

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_USAMO_Problems/Problem_5&oldid=39285"