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 ------------------------------ So, B wins if a cannot make a valid move. If there was not the condition "were not involved in B's previous move", * A could simply counteract every B's move. * So A can win with 2012 coins, just uniformly distributed * And obviously cannot win with 2011 coins (even the first move is not possible) If there are enough coins, A can act almost like counteracting B's previous move (just with different coins) B can always put at most 2 new coins to a box, * so if in every box, there remained at least 2 other couns, A can counteract the move * In particular: with 3*2012 coins distributed uniformly, A can counteract evey B's move and win. What about 3*2012-1? So there is a box with only 2 coins (or less), and let's say the other boxes are uniformly distributed. u v x y z ... 3 3 2 3 3 ... B -- wants to make an irreversible move, so put 2 new coins to the middle for example, everything to the right except u u v x y z ... 3 3 3 2 3 ... well, this is pretty much reversible (A can pick one coin from x and move it to y), furthermore, it is almost the same as the beginning. Other move for B? I need to create at least one 1 to make it interesting but that can be still easily reversible. If A manages to keep only 3's and 2's, it will win. Or, with all 2's, that is if N = 2*2012, can B win? u v x y z a b c d e ... 2 2 2 2 2 ... 2 2 2 2 2 ... B move everything from c,d to x,y u v x y z a b c d e ... 2 2 3 3 2 ... 2 2 1 1 2 ... There is at least one unused coin in every box so A can counteract the move (she does not need to counteract x <-> y and c <-> d) Ah, so all 2's is probably sufficient for A. * if B puts one coin to a general box x, then A simply puts one untouched coin from x to where the coin came from * if B puts 2 coins from v,y to x, then B also had to put a coin from x somewhere, WLOG y A can then ignore the swap x <-> y, and only put back a coin from x to v. (this proof is not completely formal yet but believable for me) So, what if there is one 1, that is 2*2012-1. u v x y z a b c d e ... 2 2 1 2 2 ... 2 2 2 2 2 ... B: again from c,d to x,y. u v x y z a b c d e ... 2 2 2 3 2 ... 2 2 1 1 2 ... A cannot counteract this exactly -- she cannot take a coin from x. But she can move coins y -> z -> ... -> a -> b -> c, obtaining again a situation with all 2's and a single 1. Perhaps, it would be useful to interpret B's action in a more comprehensible way. * If we ignore the swaps between adjecent boxes, B's action can be seen as disjoint sequences of moves <- and -> (both of the sequences in the same amount) * 'A' can counteract all the sequences except the one passing through the box which was containing 1 (let's denote the box x again). * So there is a sequence -> -> ... -> passing through x. * resulting in u x v 1 2 2 ... 2 1 2 ... 2 3 * A cannot get a coin from 'v' to 'u' but it can get a coin from 'v' to 'x'. * so there is only one box with a single coin and all the other boxes have 2 coins. Let's try 6 boxes, and some number of coins between 6 and 11, let's say 9. A 1 2 1 2 1 2 B > > > < < < 0 2 2 3 1 1 A < 1 1 2 3 1 1 B > > > < < < 0 1 3 4 1 0 Oops. Just repeating the same move > > > < < < looked relatively good for B. Now, I will play only this strategy for B. A 2 2 1 1 1 2 B > > > < < < 1 2 2 2 1 1 A < 2 1 2 2 1 1 B > > > < < < 1 1 3 3 1 0 A: Oops. With more coins, 11 coins can be won by A. A 2 2 2 1 2 2 B > > > < < < 1 2 2 3 2 1 A oh, wait. I cannot touch the 3. Maybe, I cannot win even 11 coins. A < < > 2 2 1 3 1 2 B > > > < < < 1 2 2 4 1 1 A < 2> 2 1 2 2 3 1 B > > > < < < 1 1 3 3 3 0 A < > 2> 1 2 2 2 2 2 B > > > < < < 0 2 3 3 2 1 A < < > > 1 2 2 2 2 2 ha, the move was reversible now Similarly, the move is reversible with 10 coins A 1 2 2 2 2 1 B > > > < < < 0 2 3 3 2 0 A < < > > So with less than 2k-2 coins (k = 2012 from the problem statement) it seems that B could win by the strategy. What if we try another B's simple strategy such as B > > > > > < is better / worse / the same? Is it again reversible after 1 2 2 2 2 1? A 1 2 2 2 2 1 B > > > > > < 0 2 2 2 3 1 A < < < < (yes) 1 2 2 2 2 1 Can I prove that B wins with the > > > ... < < < strategy with less than 2k-2 coins? After each A's turn, there will be at least three ones (or some zero which is winning for B) I want to argue something like "B will put more coins to the center than A can put out of the center" * So, let a "score" of a position be the sum of all distances from the center of all the coins. * I also suppose that k is even here. * B moves k coins, k-2 of which are moved by 1 to the center. * So the score decreases by k-2. * A can move all the remaining coins N - k <= 2k-3-k = k-3 coins. * Therefore B will decrease the score, and eventually wins (the score cannot be decreased infinitely). Can A win with 2k-2 coins? I would like her to keep the position "uniform", that is only two ones and the rest 2's. There was however a position in which this could not be achieed even with 2k-1 coins: A 2 2 2 1 2 2 B > > > < < < 1 2 2 3 2 1 No, what? It does not make sense. The 1 cannot become 3 in B's turn. I made a mistake, I guess. Again, the 11 coins: A 2 2 2 1 2 2 B > > > < < < 1 2 3 2 2 1 A < < 2 2 2 2 2 1 So, I still hope it would be possible to keep it uniform. B played a sequence passing a 1 2 2 2 2 1 2 2 2 2 < > > > > > > < 1 2 2 1 2 3 A < < 1 2 2 2 2 2 approximatelly. What if te sequence passes through 2 ones 2 2 2 1 2 2 1 2 2 2 < > > > > > > > > < 1 2 1 2 2 1 2 3 < < Wait, how did B managed to win with 9 coins? 2 1 2 2 1 1 B > > > < < < 1 1 3 3 1 0 Ah, it was a sequence starting at an 1, not at 2. 2 2 1 2 2 2 1 2 2 1 2 2 < > > > > > > > > < 0 2 2 2 1 2 2 2 or it is ending at a 2. 2 2 1 2 2 2 1 2 2 2 2 2 < > > > > > > > > < 0 2 2 2 1 2 2 3 this still doesn't look so bad 0 2 2 2 1 2 2 3 < < < < 1 1 2 2 2 2 2 2 So the problem was with 2 1 1 2 2 < > > > < 0 1 3 Actually, what can A do, again on 6 coins 2 2 1 1 2 2 B < < > > > < 2 1 0 1 3 3 A > > < > 2 1 1 2 2 2 Yes, A can probably keep the state of two ones and many twos, but how to prove it? Other view, 'A' can move k-2 coins 1 ... 1 0 1 ... 1 0 1 ... What positions can she achieve with these coins only? She can put the zeroes anywhere else. She can also create some twos (possibly even threes but it seems unnecessary) * But what are exactly the restrictions? Or again, the perspective of reverting disjoint sequences. a b c ... x y z > > > ... > > 'A' cannot revert the sequence if there is an '1' on the positions a...z. Assume there is only one '1' among a...z before B's move. If the one is at the 'a'-position, 'A' can revert the move. If the 1 is in the middle, a b c ... k l m ... x y z 2 2 2 ... 2 1 2 ... 2 2 2 > > > ... > > > ... > > (B) 1 2 2 ... 2 1 2 ... 2 2 3 < < < < (A) so 'A' can leave again only one '1' among a...z (at the position l), and 2's everywhere else This works for any position of the 1 except 'a' and 'z'. If the one is at the end of the sequence (z), 'A' does not have to do anything in the sequence. So, the only problematic case is when there are two 1's in one sequence. 2 2 1 2 2 2 1 2 2 B > > > > > > > > 1 2 1 2 2 2 1 2 3 A < < 1 2 1 2 2 2 2 2 2 So, if both, first and last position of the sequence are 2's at the beginning, 'A' can just put a coin from the new 3 to the last 1, and again get two 1's and all the rest twos. If the first element of the sequence is 2, and the last is 1, then 'A' does not have to do anything. 2 2 1 2 2 2 1 B > > > > > > 1 2 1 2 2 2 2 If the first element of the sequence is 1 (before B's move) 1 2 2 2 1 2 2 B > > > > > > 0 2 2 2 1 2 3 A < < < or 1 2 2 2 2 2 1 B > > > > > > 0 2 2 2 2 2 2 A < If there is at least one 2 between the two 1's, then A can make only the first two positions of the sequence equal to 1, and all the others to 2. So the last case is when the sequence starts with 1 1. Either a b 1 1 B > 0 2 or a b c d e f 1 1 2 2 2 2 B > > > > > 0 1 2 2 2 3 'A' need to fix the 0 from some sequence at the left. So, 'A' just takes a coin from the left (the box l) to get two ones again. This is possible since reversing the sequence on the left does not require using the coin in l. l a b 2 1 1 B < > 0 2 A > or l a b c d e f 2 1 1 2 2 2 2 B < > > > > > 0 1 2 2 2 3 A > < < < < As far as I can see, all the options are discussed, problem solved! The least N in which A succeeds is 2*2012-2.