Maths Olympiad Prep

Library / /48 of 48

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Hong Kong

There are three piles of coins, with aa, bb and cc coins respectively, where aa, bb, c2015c \ge 2015 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 20172017 coins. Remove 20172017 coins from this pile. Add 10091009 coins to each of the remaining two piles.
Suppose there are sufficiently many spare coins. Find all ordered triples (a,b,c)(a, b, c) such that after some finite sequence of allowed operations, there exists a pile with at least 201720172017^{2017} coins.

Solution

(a,b,c)(a, b, c) can be any integer triple with aa, bb, c2015c \ge 2015 except (2015,2015,2015)(2015, 2015, 2015).
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 3×201720173 \times 2017^{2017} after some operations, and hence there is a pile with at least 201720172017^{2017} coins.

Consider any integer triple (a,b,c)(a, b, c) with S=a+b+c6046S = a + b + c \ge 6046 (which is 3×2015+13 \times 2015 + 1).
Note that operation (1) does not change the sum SS, while operation (2) always increases SS by 11. Since we always have S3>2015\lfloor \frac{S}{3} \rfloor > 2015, there must be a pile with at least 20162016 coins after each operation, and hence one of the operations can be carried out.

Suppose on the contrary that there exists a case with S6046S \ge 6046 such that SS 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 20152015. 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 00, xx, yy respectively, where xx is odd and 0<x2015<y0 < x \le 2015 < y. As x+y6046x + y \ge 6046, we deduce y4031y \ge 4031. Note that yy must be even since otherwise no more operation (1) can be carried out. Hence, we have y4032y \ge 4032. Next, we apply operation (1) on the pile with yy coins. The number of coins becomes 00, y2\frac{y}{2}, x+y2x + \frac{y}{2}. Each of the nonempty piles contains at least y22016\frac{y}{2} \ge 2016 coins. As S=x+yS = x + y 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 20162016 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 60466046.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.