Problem:
Three nonnegative real numbers r1​,r2​,r3​ are written on a blackboard. These numbers have the property that there exist integers a1​,a2​,a3​, not all zero, satisfying a1​r1​+a2​r2​+a3​r3​=0. We are permitted to perform the following operation: find two numbers x,y on the blackboard with x≤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:
If two of the ai​ vanish, say a2​ and a3​, then r1​ must be zero and we are done. Assume at most one ai​ vanishes. If any one ai​ vanishes, say a3​, then r2​/r1​=−a1​/a2​ is a nonnegative rational number. Write this number in lowest terms as p/q, and put r=r2​/p=r1​/q. We can then write r1​=qr and r2​=pr. Performing the Euclidean algorithm on r1​ and r2​ will ultimately leave r and 0 on the blackboard. Thus we are done again.
Thus it suffices to consider the case where none of the ai​ vanishes. We may also assume none of the ri​ vanishes, as otherwise there is nothing to check. In this case we will show that we can perform an operation to obtain r1′​,r2′​,r3′​ for which either one of r1′​,r2′​,r3′​ vanishes, or there exist integers a1′​,a2′​,a3′​, not all zero, with a1′​r1′​+a2′​r2′​+a3′​r3′​=0 and
∣a1′​∣+∣a2′​∣+∣a3′​∣<∣a1​∣+∣a2​∣+∣a3​∣
After finitely many steps we must arrive at a case where one of the ai​ vanishes, in which case we finish as above.
If two of the ri​ are equal, then we are immediately done by choosing them as x and y. Hence we may suppose 0<r1​,r2​<r3​. Since we are free to negate all the ai​, we may assume a3​>0. Then either a1​<−21​a3​ or a2​<−21​a3​ (otherwise a1​r1​+a2​r2​+a3​r3​>(a1​+ 21​a3​)r1​+(a2​+21​a3​)r2​>0). Without loss of generality, we may assume a1​<−21​a3​. Then choosing x=r1​ and y=r3​ gives the triple (r1′​,r2′​,r3′​)=(r1​,r2​,r3​−r1​) and (a1′​,a2′​,a3′​)= (a1​+a3​,a2​,a3​). Since a1​<a1​+a3​<21​a3​<−a1​, we have ∣a1′​∣=∣a1​+a3​∣<∣a1​∣ and hence this operation has the desired effect.
This problem was suggested by Kiran Kedlaya.
The problems on this page are the property of the MAA's American Mathematics Competitions