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 ; then pick some chocolates from one of the remaining boxes and transfer them to the temporarily empty box so that no box stays empty.
The game ends with the current player’s loss when this is no longer possible.
Example start:
Initial state : (7,8,17)
Kid A empties the 1st box: (0,8,17),
then transfers 3 pieces from the 2nd box to the
1st creating new situation (3,5,17)
and now Kid B goes on.
What is the optimal strategy?
Source: The French "Le Monde"
My remark: Although we don’t know the initial quantities of chocolates in each box, the kids do. Please assume: (a,b, 32-a-b) for conformity sake.
(1,1,1) is an immediate loss for the current player. Similarly any triplet of odd numbers is a losing position for a player.
For any combination of one odd plus two even numbers the strategy is to discard one even pile and split the other even pile into two odd piles.
A winning move for (1,4,8) is to discard 8 and split 4 into 1 and 3.
Similarly for any of two odd plus one even numbers the strategy is to discard one if the odd piles and split the even pile into two odd piles.
A winning move for (1,6,9) is to discard 9 and split 4 into 1 and 5.
If all three numbers are even then a player does not want to create any odd piles. In this case divide all the piles by 2 and find the strategy for that situation, then multiply everything by 2 to restore the original quantities.
For (2,6,12), dividing by 2 becomes (1,3,6) which has a winning move of discarding 3 and splitting 6 into 1 and 5. This implies a winning move for (2,6,12) is to discard the 6 and split the 12 into 2 and 10.
For (2,6,10), dividing by 2 becomes (1,3,5) which is a losing position, implying that (2,6,10) is also a losing position.
More generally, for each number determine the largest power of 2 that divides each number. If the powers of 2 are all the same then that is a losing position. Otherwise keep a number with the lowest power of 2, split a number with a highest power of 2 into a pair of numbers each with the lowest power of 2, and discard the third number.
(4,12,20) each have 4 as the highest power of 2 so it is a losing position.
(24,12,16) have 8, 4, and 16 as their respective powers of 2. One winning move is to keep 12, discard 24, and split 16 into 4 and 12.
Can the first player always force a win? The total of a losing position is of the form (2k+3)*2^n, with k and n both non-negative integers. This covers all positive integers except powers of 2. Then all valid starting positions are winning positions for the first player with 32 (or any other power of 2) chocolates available.
Edited on July 1, 2017, 11:14 pm
Solution
