There are three piles of coins, with , and coins respectively, where , , are positive integers. The following operations are allowed:
(1) Choose a pile with an even number of coins and remove all coins from this pile. Add coins to each of the remaining two piles with amount equal to half of that removed; or
(2) Choose a pile with an odd number of coins and at least coins. Remove coins from this pile. Add coins to each of the remaining two piles.
Suppose there are sufficiently many spare coins. Find all ordered triples such that after some finite sequence of allowed operations, there exists a pile with at least coins.
Solution
can be any integer triple with , , except .
It is obvious that no operation can be carried out in the exceptional case. For the other cases, we claim that it is always possible to increase the total number of coins in some operations. If this is true, then the total number of coins will exceed after some operations, and hence there is a pile with at least coins.
Consider any integer triple with (which is ).
Note that operation (1) does not change the sum , while operation (2) always increases by . Since we always have , there must be a pile with at least coins after each operation, and hence one of the operations can be carried out.
Suppose on the contrary that there exists a case with such that can no longer be increased. Thus, only operation (1) is possible, which means the number of coins in each pile is always even or at most . Applying operation (1) if necessary, we may assume there is an empty pile. Afterwards, we apply operation (1) repeatedly to the nonempty pile with the smallest number of coins until this is not possible. The number of coins of the nonempty pile with the smallest number of coins is halved in each operation. Therefore, it must become an odd number after some steps.
We are now in a situation where the number of coins are , , respectively, where is odd and . As , we deduce . Note that must be even since otherwise no more operation (1) can be carried out. Hence, we have . Next, we apply operation (1) on the pile with coins. The number of coins becomes , , . Each of the nonempty piles contains at least coins. As is odd, one of these piles has an odd number of coins. This contradicts our assumption that there cannot be an odd pile with more than coins.
Therefore, the total number of coins can always be increased. The goal can be attained in a finite number of operations whenever the total number of coins is at least .