Problem:
Antonio and Bernardo play the following game: two piles of tokens are given, one with tokens and the other with tokens. Each player in turn chooses one of the following moves:
- take one token from one of the piles;
- take one token from each of the piles;
- move one token from one pile to the other.
The player who can no longer move loses. Antonio starts. Determine, as a function of and , whether one of the two players has a winning strategy, and if so specify which player it is.
Solution:
If at least one of and is odd, Antonio wins; if they are both even, Bernardo wins.
Clearly the only configuration in which no more moves are possible is the one in which both piles are empty. In particular, at that moment both piles will have an even number of tokens. The idea is therefore to try to leave, after one's own move, an even number of tokens in both piles.
If in the initial state exactly one pile has an odd number of tokens, Antonio takes a token from that pile. If both piles have an odd number of tokens, he takes a token from each pile. In both cases he leaves Bernardo with an even number of tokens in both piles; on the other hand, every subsequent move by Bernardo leaves at least one pile with an odd number of tokens, allowing Antonio to repeat his strategy. Since finally every move by Antonio removes some token, the game will end in a finite number of steps with Antonio's victory.
If instead both piles have an even number of tokens, the situation is symmetric to the previous one: after any move by Antonio there will be an odd number of tokens in at least one of the piles, and so Bernardo will be able to apply the same strategy as Antonio in the previous case.