Angel has a warehouse, which initially contains 100 piles of 100 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 199 but not earlier.
If we have n piles with at least two pieces of rubbish and m piles with exactly one piece of rubbish, then we define the value of the pile to be V=⎩⎨⎧nn+21n+1m=0,m=1,m≥2. We also denote this position by (n,m). Implicitly we will also write k for the number of piles with exactly two pieces of rubbish.
Angel's strategy is the following: (i) From position (0,m) remove one piece from each pile to go position (0,0). The game ends. (ii) From position (n,0), where n≥1, remove one pile to go to position (n−1,0). Either the game ends, or the demon can move to position (n−1,0) or (n−1,1). In any case V reduces by at least 1/2. (iii) From position (n,1), where n≥1, remove one pile with at least two pieces to go to position (n−1,1). The demon can move to position (n,0) or (n−1,2). In any case V reduces by (at least) 1/2. (iv) From position (n,m), where n≥1 and m≥2, remove one piece from each pile to go to position (n−k,k). The demon can move to position (n,0) or (n−k,k+1). In any case V reduces by at least 1/2. (The value of position (n−k,k+1) is n+21 if k=0, and n−k+1≤n if k≥1.)
So during every day if the game does not end then V is decreased by at least 1/2. So after 198 days if the game did not already end we will have V≤1 and we will be in one of positions (0,m), (1,0). The game can then end on the morning of day 199.
We will now provide a strategy for demon which guarantees that at the end of each day V has decreased by at most 1/2 and furthermore at the end of the day m≤1. (i) If Angel moves from (n,0) to (n−1,0) (by removing a pile) then create a new pile with one piece to move to (n−1,1). Then V decreases by 1/2 and m=1≤1. (ii) If Angel moves from (n,0) to (n−k,k) (by removing one piece from each pile) then add one piece back to each pile to move to (n,0). Then V stays the same and m=0≤1. (iii) If Angel moves from (n,1) to (n−1,1) or (n,0) (by removing a pile) then add one piece to each pile to move to (n,0). Then V decreases by 1/2 and m=0≤1. (iv) If Angel moves from (n,1) to (n−k,k) (by removing a piece from each pile) then add one piece to each pile to move to (n,0). Then V decreases by 1/2 and m=0≤1.
Since after every move of demon we have m≤1, in order for Angel to finish the game in the next morning we must have n=1,m=0 or n=0,m=1 and therefore we must have V≤1.
But now inductively the demon can guarantee that by the end of day N, where N≤198 the game has not yet finished and that V≥100−N/2.
Solution 2
Define Angel's score SA to be SA=2n+m−1. The Angel can clear the rubbish in at most max{SA,1} days. The proof is by induction on (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 SA reduces by at least 1 in each day. (Case (i) is trivial as the game ends in one day.)
Now define demon's score SD to be SD=2n−1 if m=0 and SD=2n if m≥1. The claim is that if (n,m)=(0,0), then the demon can ensure that Angel requires SD 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 SD reduced by at most 1 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.