## 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 $\left(2^n a, 2^n b, 2^n c\right)$, 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.