Here’s a puzzle I found in “The Moscow Puzzles”, by Boris Kordemsky and Martin Gardner:
Person 1 can call any number from 1 to 10. Person 2 can then increment the last called number by any whole number from 1 to 10, then it’s Person 1’s turn again, and so on. The first person to call 100 wins. Give a strategy that allows Person 1 to win this game every time
Take a minute to try and solve it!
A hint here is that it’s useful to think about problems like this in terms of invariants. What invariants can Person 1 preserve that allow him to win? One example might be that Person 1 wants to call 100, which is congruent to 0 mod 10. Can we preserve the invariant that Person 1 always calls a number congruent to 0 mod 10?
Yes, but it’s not useful! For instance, Person 1 might call 90, and then Person 2 would get to call 100 and win. In fact, we were on the right track, but we chose a number that doesn’t adequately take Person 2’s moves into account. Let’s formalize this a bit: Person 1 needs to find a mod base \(b\) and a number \( n \) such that \(100 \equiv n\ (\mod b)\) and Person 1 can ensure that he will always call number congruent to \(n\) mod \(b\) and Person 2 can never call a congruent number. Person 1 can then call \(n\) as his first move and ensure that all subsequent moves are congruent to \(n\) mod \(b\). We can simplify by asking ourselves an easier, equivalent question: can Person 1 find a number \(b\) such that his move and Person 2’s last move always sum to \(b\)?
Clearly, the only possible such number is 11. Using 11 for \(b\), we can see that we must use 1 for \(n\), because \(100 \equiv 1\ (\mod 11)\). Person 1 calls 1, and after 9 pairs of moves which sum to 11, Person 1 will also call 100.
Kordemsky phrases the answer differently:
To call 100, first call 89. To call 89, first call 78, 67, 56… starting with 1.
This is more concise, but it also doesn’t scale so well. For instance, it takes me just a moment to tell you that if the first person to call 500 wins (instead of 100), then Person 1 can always win by starting on 5, because 500 is congruent to 5 mod 11.