Candy Game
I recently saw another puzzle on Facebook, a generalization of a problem from the 2002 Belarus Olympiad. In the problem, there are red and white boxes. Given how Russia and Belarus are filled with propaganda, my first question was whether the Belarusian flag was red and white. But in fact, the official flag is red and green; however, the opposition uses a red and white one. It could either be a coincidence or a sneaky way of protesting. Anyway, here is the problem.
Puzzle. There are two boxes filled with candy. The red box has R candies, and the white box has W candies. Alice and Bob are playing a game where Alice starts, and both players have the same options each turn: Either move one candy from the red box to the white box or take two candies from any box and eat them. The player who can’t move loses. For which values of R and W is each of the following true?
- Alice, following her optimal strategy, wins but might lose if she makes a mistake.
- Alice wins no matter what.
- Bob, following his optimal strategy, wins but might lose if he makes a mistake.
- Bob wins no matter what.
The list of options is weird, but I decided to keep it to emphasize …. Oops, I do not want to spoil it. You can decide for yourself what I wanted to emphasize.
Share:
Nickel:
For a minute, assume intellegent play, and the number of white candies is taken mod 4. Also, whenever there is a number followed by a name, the number represents what player number they are, so if a case would put Alice 2nd after a few moves, it would be 2/Alice, and whenever a number appears a pair of parenthesis, it says who won in that case.
4 September 2023, 5:45 pm(0,0), which means 0 red candies and 0 (mod 4) white candies. This is a 2/Bob win, because every 2 turns 4 candies would be eaten, making the boxes (0,0) again, until eventually 2/Bob takes the final 2 pieces
(0,1) would be another 2/Bob win, with similar reasoning to (0,0) except there is 1 candy left over
(0,2) would be an 1/Alice win, with similar reasoning to (0,0) and (0,1) except that after Bob takes his last turn, there are 2 candies for Alice to take leaving Bob with none
(0,3) would be another 1/Alice win, with similar reasoning to (0,2), except there is 1 candy left over
(1,0) either leads to (1,2)/U or (0,1)/2
(1,1)
Sanandan Swaminathan:
The possible starting red-white pairs can be enumerated in order as follows: First order by the total count in the two boxes. For a given total count, order by red count descending, white count ascending, as shown below. List can be generated to be as long as desired.
(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3), (4,0), (3,1), (2,2), (1,3), (0,4), (5,0), (4,1), (3,2), (2,3), (1,4), (0,5)…
If the game starts with a pair that is in an odd position in the above list of pairs, the first player (Alice) loses. If the game starts with a pair in an even position in the list above, the first player (Alice) wins. From what I can see, it does not matter whether either or both players make smart moves or not. In fact, there is no smart move they can make to force a win. Of course, though the players can make non-optimal moves, it’s assumed that the moves still need to be as per the rules of the game. Also, they must make a move if they can. The outcome is pre ordained and only depends on which pair they start the game with. In every move, the state of the game toggles from an odd position in the above list to an even position, or vice versa. Player1 wins any game which is in an even position just before his/her turn (any turn), and player2 wins any game in an odd position just before his/her turn (any turn). Thus, neither player can force a win, no matter what he/she or the other player does in any turn.
5 September 2023, 12:28 amSanandan Swaminathan:
Typo in the penultimate sentence… It should read “Player1 wins any game which is in an even position just before his/her turn (any turn), and PLAYER1 LOSES any game in an odd position just before his/her turn (any turn)”.
5 September 2023, 12:44 amZarunias:
W-R (mod 4) will change by 2, no matter what move a player does. So after both players had one move, the value of W-R (mod 4) stays the same. Every game is forced to come to an end (the total number R+w is never increasing and it can only stay the same for a finite amount of moves). There are only 2 endpositions (0,0) and (0,1), in which W-R=0(mod 4) or W-R=1(mod 4).
5 September 2023, 7:12 pmSo Bob wins if the start position has W-R=0 or 1 (mod 4), and Alice wins if the start position has W-R=2 or 3 (mod 4). No matter what the players are doing.
Kai:
I have a proposal on the winning or losing positions for the 1st player, where winning position = Alice wins and losing position = Bob wins.
The following proposal is based on the understanding that the action of “taking one candy from each box” is covered by the condition of “taking two candies from any box”.
1) If W >= R,
1.1) if R is odd, (W, R) is always a winning position.
1.2) if R is even,
1.2.1) if W – R = 0 or 1 (mod 4), (W, R) is a losing position.
1.2.2) Otherwise (W, R) is a winning position.
2) If W < R,
2.1) if W is odd, (W, R) is always a winning position.
2.2) if W is even,
1.2.1) if W – R = 0 or 3 (mod 4), (W, R) is a losing position.
1.2.2) Otherwise (W, R) is a winning position.
If the condition of "taking two candies from any box" means the player "takes two candies from any single box", the game is much simpler and the solution lies already in the previous comments.
7 September 2023, 5:12 am