Maths Olympiad Prep

Library / /6 of 17

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Balkan Mathematical Olympiad

Angel has a warehouse, which initially contains 100100 piles of 100100 pieces of rubbish each. Each morning, Angel either clears every piece of rubbish from a single pile, or one piece of rubbish from each pile. However, every evening, a demon sneaks into the warehouse and adds one piece of rubbish to each non-empty pile, or creates a new pile with one piece. What is the first morning when Angel can guarantee to have cleared all the rubbish from the warehouse?

Proposed by United Kingdom

Solutions — 2

Solution 1

We will show that he can do so by the morning of day 199199 but not earlier.

If we have nn piles with at least two pieces of rubbish and mm piles with exactly one piece of rubbish, then we define the value of the pile to be
V={nm=0,n+12m=1,n+1m2. V = \begin{cases} n & m = 0, \\ n + \frac{1}{2} & m = 1, \\ n + 1 & m \ge 2. \end{cases}
We also denote this position by (n,m)(n, m). Implicitly we will also write kk for the number of piles with exactly two pieces of rubbish.

Angel's strategy is the following:
(i) From position (0,m)(0, m) remove one piece from each pile to go position (0,0)(0, 0). The game ends.
(ii) From position (n,0)(n, 0), where n1n \ge 1, remove one pile to go to position (n1,0)(n - 1, 0). Either the game ends, or the demon can move to position (n1,0)(n - 1, 0) or (n1,1)(n - 1, 1). In any case VV reduces by at least 1/21/2.
(iii) From position (n,1)(n, 1), where n1n \ge 1, remove one pile with at least two pieces to go to position (n1,1)(n - 1, 1). The demon can move to position (n,0)(n, 0) or (n1,2)(n - 1, 2). In any case VV reduces by (at least) 1/21/2.
(iv) From position (n,m)(n, m), where n1n \ge 1 and m2m \ge 2, remove one piece from each pile to go to position (nk,k)(n - k, k). The demon can move to position (n,0)(n, 0) or (nk,k+1)(n - k, k + 1). In any case VV reduces by at least 1/21/2. (The value of position (nk,k+1)(n - k, k + 1) is n+12n + \frac{1}{2} if k=0k = 0, and nk+1nn - k + 1 \le n if k1k \ge 1.)

So during every day if the game does not end then VV is decreased by at least 1/21/2. So after 198198 days if the game did not already end we will have V1V \le 1 and we will be in one of positions (0,m)(0, m), (1,0)(1, 0). The game can then end on the morning of day 199199.

We will now provide a strategy for demon which guarantees that at the end of each day VV has decreased by at most 1/21/2 and furthermore at the end of the day m1m \le 1.
(i) If Angel moves from (n,0)(n, 0) to (n1,0)(n - 1, 0) (by removing a pile) then create a new pile with one piece to move to (n1,1)(n - 1, 1). Then VV decreases by 1/21/2 and m=11m = 1 \le 1.
(ii) If Angel moves from (n,0)(n, 0) to (nk,k)(n - k, k) (by removing one piece from each pile) then add one piece back to each pile to move to (n,0)(n, 0). Then VV stays the same and m=01m = 0 \le 1.
(iii) If Angel moves from (n,1)(n, 1) to (n1,1)(n - 1, 1) or (n,0)(n, 0) (by removing a pile) then add one piece to each pile to move to (n,0)(n, 0). Then VV decreases by 1/21/2 and m=01m = 0 \le 1.
(iv) If Angel moves from (n,1)(n, 1) to (nk,k)(n - k, k) (by removing a piece from each pile) then add one piece to each pile to move to (n,0)(n, 0). Then VV decreases by 1/21/2 and m=01m = 0 \le 1.

Since after every move of demon we have m1m \le 1, in order for Angel to finish the game in the next morning we must have n=1,m=0n = 1, m = 0 or n=0,m=1n = 0, m = 1 and therefore we must have V1V \le 1.

But now inductively the demon can guarantee that by the end of day NN, where N198N \le 198 the game has not yet finished and that V100N/2V \ge 100 - N/2.

Solution 2

Define Angel's score SAS_A to be SA=2n+m1S_A = 2n + m - 1. The Angel can clear the rubbish in at most max{SA,1}\max\{S_A, 1\} days. The proof is by induction on (n,m)(n, m) in lexicographic order.

Angel's strategy is the same as in Solution 1 and in each of cases (ii)-(iv) one needs to check that SAS_A reduces by at least 11 in each day. (Case (i) is trivial as the game ends in one day.)

Now define demon's score SDS_D to be SD=2n1S_D = 2n - 1 if m=0m = 0 and SD=2nS_D = 2n if m1m \ge 1. The claim is that if (n,m)(0,0)(n, m) \ne (0, 0), then the demon can ensure that Angel requires SDS_D days to clear the rubbish.

Again, demon's strategy is the same as in the Solution by PSC and in each of cases (i)-(iv) one needs to check that SDS_D reduced by at most 11 in each day.

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.