1994 IMO SL #C3

Peter has three accounts in a bank, each with an integral number of dollars. He is only allowed to transfer money from one account to another so that the amount of money in the latter is doubled. Prove that Peter can always transfer all his money into two accounts. Can Peter always transfer all his money into one account?

(a) WLOG, the accounts contain \(a<b<c\) dollars. We show that we can perform some moves to get an account with less than \(a\) dollars. Let \(b=ab'+r_1\) and \(c=ac'+r_2\) with \(0\le r_1,r_2<a\). Let \(b'=(\overline{1b_{k-1}b_{k-2}\ldots b_0})_2\) in base two. Iterating over \(i=0,1,\ldots,k-1\), we do the following operation: If \(b_i=1\), then transfer money from the second account to the first account, doubling \(a\) and removing the \(b_i\) bit from \(b'\). If \(b_i=0\), then transfer money from the third account to the first account, doubling \(a\). At the end of our process, the first account has \(2^ka\) dollars and the second account has \(2^ka+r_1\) dollars, so transferring money from the second account to the first account leaves the second account with \(r_1<a\) dollars. So, Peter now has all of his money in two accounts. $\square$

(b) Peter cannot possibly always transfer his money into one account. If we start with at least two nonzero balances and the sum of the three balances is odd, then observe that at the end of every move, the recipient balance must be even. But the final position includes a single nonzero balance that is odd. Hence, we have shown that Peter cannot transfer all his money into one account.$\square$