A matches game puzzle
Photo: aftermat(c)h by ankaatje – CC
This nifty little puzzle comes from an excercise sheet of our algorithms and data structures course at the university. Our task was to find a winning formula for a game and prove it.
Imagine 100 matches laying on the table. Alice and Bob take at most 10 matches from the table in turn. They can choose how many matches they want to take, but they have to take at least one match. Whoever gets the last match, wins the game. Suppose Alice starts, how should she play to win the game every time?
You should really try to solve this puzzle on your own before reading my explanation after the jump.
The explanation
Instead of reasoning from the very beginning, you should rather ask yourself how Alice can win in the end. Suppose there’s only one match left from the game and it’s Bob’s turn. He can snatch the last match and therefore wins the game, which is not what we want. The same is also true if there’s two to ten matches left.
The interesting part comes when there’s 11 matches left for Bob. Bob can’t snatch up the last match, because he can only remove ten matches at most. Then Alice can take all of the remaining matches, including the last one, which makes her the winner, because Bob has to remove at least one match, leaving at most ten matches behind.
If Alice can leave 11 matches to Bob, she’ll win. Now we can reduce the problem to the following: How can she ensure that Bob gets the last 11 matches?
Inception
Photo: Inception by Schjelderup – CC
Now, mathematicians are lazy people. Really! If they’ve already proven something, they would want to reduce other more complex problems to the already proven ones. Believe it or not, we’ve already shown the core of this puzzle.
Now back to our problem at hand. How does Alice ensure that Bob gets the last 11 matches? It’s very simple: She has to take the 12th match from last. How is that simple? Because we’ve already solved that problem.
Let’s imagine our 100 matches laying on our table. If we put 11 matches aside (we don’t actually put 11 matches aside; we do that in our minds.), we get 89 matches. How to get the last one of those 89 matches? Well, that’s solved: Alice has to leave 11 matches (of those 89) for Bob behind. If we put the 11 matches back on the table, we can see that Alice can snatch up the 12th match from last (and therefore win), if she can leave 22 matches for Bob.
This implies that she has to take the 23rd match from last. She does that by leaving 33 matches for Bob, etc…
If we do that over and over again, this becomes: Alice can win, if she can leave $11k,\ k\in\mathbb{N}$ matches for Bob behind at the beginning. Since Alice starts the game, she just have to take one match, leaving $100 – 1 = 99 = 11\cdot 9$ for Bob behind. And if she plays according to our strategy, she can also win.
More excercises
- Suppose there are $n\in\mathbb{N}$ matches on the table at the beginning and the players can remove at most $m\in\mathbb{N}$ matches. Can Alice still win?
- Consider the “inverted” game: Whoever gets the last match, loses. How can Alice win?
Just remember to reduce the problems to the ones we’ve already solved… Happy thinking!
