IMO 1994 SL C3

Origin: MCD | Category: Combinatorics

Problem

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. (a) Prove that Peter can always transfer all his money into two accounts. (b) Can Peter always transfer all his money into one account?

Solution

(a) Let a, b, c, a \leqb \leqc be the amounts of money in dollars in Peter’s first, second, and third account, respectively. If a = 0, then we are done, so suppose that a > 0. Let Peter make transfers of money into the first account as follows. Write b = aq + r with 0 \leqr < a and let q = m0 + 2m1 + \cdot \cdot \cdot + 2kmk be the binary representation of q (mi \in{0, 1}, mk = 1). In the ith transfer, i = 1, 2, . . . , k + 1, if mi = 1 he transfers money from the second account, while if mi = 0 he does so from the third. In this way he has transferred exactly (m0+2m1+\cdot \cdot \cdot+2kmk)a dollars from the second account, thus leaving r dollars in it, r < a. Repeating this procedure, Peter can diminish the amount of money in the smallest account to zero, as required. (b) If Peter has an odd number of dollars, he clearly cannot transfer his money into one account.