Two friends are playing a game with two boxes of chocolates. They take turns taking out some number of chocolates from the boxes, and whoever takes the last chocolate wins. Each turn they can take chocolates one of two ways:
- Take any number of chocolates from a single box
- Or take an equal number of chocolates from each box
If there are 25 chocolates in one box and 35 in the other, what is the winning strategy?
Solution
To figure out the winning strategy, work backwards:
- If you leave 0 chocolates in one box and there are any number of chocolates in the other box, the other player will take all of the chocolates in the other box and win.
- This means you should leave at least 1 chocolate in each box. But if you leave exactly 1 chocolate in each box, the other player will take 1 from each box and win as well. So you need to leave 1 chocolate in one box and 2 chocolates in the other box.
- This means (1, 2) is the first “safe” arrangement of chocolates. You want to take chocolates such that you always leave the boxes at the next “safe” arrangement.
- Note that (1, 2) is equivalent to (2, 1) since there is no difference between the boxes.
- After (1, 2), no other arrangement with 1 or 2 chocolates in any box will be safe, because the other player can remove chocolates such that (1, 2) is left. This leads to discover a rule for safe arrangements: no safe arrangement can share a number with any other safe arrangement.
- For example, (1, 5) is not safe because the other player will remove 3 from the 2nd box to get (1, 2) before you. And (2, 5) is not safe because the other player will remove 4 from the 2nd box and get (2, 1).
- This means the next safe arrangement can only be as low as (3, 4). But (3, 4) does not work because the other player can remove 2 from each box to get (1, 2). So (3, 5) is the next safe arrangement. This leads us to discover another rule for safe arrangements: the difference between the numbers of a safe arrangement cannot be the same as the difference between the numbers of any other safe arrangement. In other words, the difference in the first safe arrangement (1, 2) is 1, so the next safe arrangement must have a difference of 2.
- Using these two rules, we can fairly quickly figure out all of the safe arrangements: (1, 2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15), (11, 18), (12, 20), (14, 23), (16, 26), (17, 28), (19, 31), (21, 34), etc.
The winning strategy would be to keep aiming for the safe arrangements above. Since the game starts at (25, 35), the first player achieves safe arrangement (16, 26) by removing 9 from each box, so the first player can always win.
who is it!?