Candy branching process

Christian Robert has basically forced me to post my solution to last week’s Le Monde problem:

Two kids are given three boxes of chocolates with a total of 32 pieces. Rather than sharing evenly, they play the following game: Each in turn, they pick one of the three boxes, empty its contents in a jar and pick some chocolates from one of the remaining boxes so that no box stays empty. The game ends with the current player’s loss when this is no longer possible. What is the optimal strategy?

Although we don’t know the number of chocolates in each box, the kids do. A kid loses when at his turn, he is faced with the configuration (1,1,1): he has to leave one empty, thus losing. Note that the total number of chocolates decreases at each turn.

Because the initial number of chocolates is a power of 2, the first kid (A) is guaranteed to win. Let us look at the parity of the number of chocolates in each box. The strategy of player A is to give to the other kid (B) a configuration of the form (odd, odd, odd). Then B will necessarily return (odd, odd, even) to A. Kid A can empty a box with an odd number of chocolates, split the even number into two odd numbers, and B is faced again with (odd,odd,odd). Eventually, B will end up with (1,1,1) and lose.

Note also that any (odd, even, even) configuration wins: empty one of the even boxes, and split the other even number into two odd numbers.

The only remaining question is what to do with a configuration (even, even, even). Per the above, the first player to introduce a box with an odd number of chocolates loses. Kid A’s strategy is now to give B a configuration of the form (4a+2, 4b+2, 4c+2). To avoid odd numbers, B must give A a configuration of the form (4a+2, 4d+2, 4e), where the number of chocolates in box 3 is a multiple of 4. Kid A can then empty one of the first two boxes, giving B (4a+2, 4f+2, 4g+2) again, and so on until B is faced with (2, 2, 2), at which point he has lost.

This can be easily generalized: let a configuration be of the form , with n as large as possible (so at least one of a, b, c is odd). If a, b and c are all odd, the configuration loses; otherwise, it can be transformed into a configuration where a, b and c are all odd, and the other player loses.

Because the initial total number of chocolates is a power of 2, the initial configuration is necessarily a winning configuration.