IMO 2012 Shortlist C4

Category: Combinatorics

Problem

Players A and B play a game with N ≥ 2012 coins and 2012 boxes arranged around a circle. Initially A distributes the coins among the boxes so that there is at least 1 coin in each box. Then the two of them make moves in the order B,A,B,A,... by the following rules: • On every move of his B passes 1 coin from every box to an adjacent box. • On every move of hers A chooses several coins that were not involved in B’s previous move and are in different boxes. She passes every chosen coin to an adjacent box. Player A’s goal is to ensure at least 1 coin in each box after every move of hers, regardless of how B plays and how many moves are made. Find the least N that enables her to succeed. Solution. We argue for a general n ≥ 7 instead of 2012 and prove that the required minimum N is 2n − 2. For n = 2012 this gives Nmin = 4022. a) If N = 2n − 2 player A can achieve her goal. Let her start the game with a regular distribution: n−2 boxes with 2 coins and 2 boxes with 1 coin. Call the boxes of the two kinds red and white respectively. We claim that on her first move A can achieve a regular distribution again, regardless of B’s first move M. She acts according as the following situation S occurs after M or not: The initial distribution contains a red box R with 2 white neighbors, and R receives no coins from them on move M. Suppose that S does not occur. Exactly one of the coins c1 and c2 in a given red box X is involved in M, say c1. If M passes c1 to the right neighbor of X, let A pass c2 to its left neighbor, and vice versa. By doing so with all red boxes A performs a legal move M′ . Thus M and M′ combined move the 2 coins of every red box in opposite directions. Hence after M and M′ are complete each neighbor of a red box X contains exactly 1 coin that was initially in X. So each box with a red neighbor is non-empty after M′ . If initially there is a box X with 2 white neighbors (X is red and unique) then X receives a coin from at least one of them on move M since S does not occur. Such a coin is not involved in M′ , so X is also non-empty after M′ . Furthermore each box Y has given away its initial content after M and M′ . A red neighbor of Y adds 1 coin to it; a white neighbor adds at most 1 coin because it is not involved in M′ . Hence each box contains 1 or 2 coins after M′ . Because N = 2n−2, such a distribution is regular. Now let S occur after move M. Then A leaves untouched the exceptional red box R. With all remaining red boxes she proceeds like in the previous case, thus making a legal move M′′ . Box R receives no coins from its neighbors on either move, so there is 1 coin in it after M′′ . Like above M and M′′ combined pass exactly 1 coin from every red box different from R to each of its neighbors. Every box except R has a red neighbor different from R, hence all boxes are non-empty after M′′ . Next, each box Y except R loses its initial content after M and M′′ . A red neighbor of Y adds at most 1 coin to it; a white neighbor also adds at most 1 coin as it does not participate in M′′ . Thus each box has 1 or 2 coins after M′′ , and the obtained distribution is regular. Player A can apply the described strategy indefinitely, so N = 2n−2 enables her to succeed. b) For N ≤ 2n − 3 player B can achieve an empty box after some move of A. Let α be a set of ℓ consecutive boxes containing a total of N(α) coins. We call α an arc if ℓ ≤ n − 2 and N(α) ≤ 2ℓ − 3. Note that ℓ ≥ 2 by the last condition. Moreover if both extremes of α are non-empty boxes then N(α) ≥ 2, so that N(α) ≤ 2ℓ − 3 implies ℓ ≥ 3. Observe also that if an extreme X of α has more than 1 coin then ignoring X yields a shorter arc. It follows that every arc contains an arc whose extremes have at most 1 coin each. Given a clockwise labeling 1,2,...,n of the boxes, suppose that boxes 1,2,...,ℓ form an arc α, with ℓ ≤ n − 2 and N(α) ≤ 2ℓ − 3. Suppose also that all n ≥ 7 boxes are non-empty. Then B can move so that an arc α′ with N(α′ ) < N(α) will appear after any response of A.23 One may assume exactly 1 coin in boxes 1 and ℓ by a previous remark. Let B pass 1 coin in counterclockwise direction from box 1 and box n, and in clockwise direction from each remaining box. This leaves N(α)−2 coins in the boxes of α. In addition, due to 3 ≤ ℓ ≤ n−2, box ℓ has exactly 1 coin c, the one received from box ℓ − 1. Let player A’s next move M pass k ≤ 2 coins to boxes 1,2,...,ℓ from the remaining ones. Only boxes 1 and ℓ can receive such coins, at most 1 each. If k < 2 then after move M boxes 1,2,...,ℓ form an arc α′ with N(α′ ) < N(α). If k = 2 then M adds a coin to box ℓ. Also M does not move coin c from ℓ because c is involved in the previous move of B. In summary boxes 1,2,...,ℓ contain N(α) coins like before, so they form an arc. However there are 2 coins now in the extreme ℓ of the arc. Ignore ℓ to obtain a shorter arc α′ with N(α′ ) < N(α). Consider any initial distribution without empty boxes. Since N ≤ 2n − 3, there are at least 3 boxes in it with exactly 1 coin. It follows from n ≥ 7 that some 2 of them are the extremes of an arc α. Hence B can make the move described above, which leads to an arc α′ with N(α′ ) < N(α) after A’s response. If all boxes in the new distribution are non-empty he can repeat the same, and so on. Because N(α) cannot decrease indefinitely, an empty box will occur after some move of A.24