At BEAM, we love sharing math! So, as a new feature of our quarterly newsletter, we’re introducing a math problem.
Our first problem comes from one of BEAM’s Saturdays classes for 8th graders and high school students this past semester. In this class, on combinatorial game theory, students learned about different kinds of games, that it is possible to add games together and treat them (sort of) like numbers, and how all of a certain kind of games are equivalent to one particular game called Nim. If you want a taste of this, here’s a classic problem students considered at the beginning of class.
Suppose there are 25 tokens in a pile. On each turn, players alternate removing either 1 or 2 tokens, and they keep going until the pile runs out. The last person who takes a token wins. (It doesn't matter how many they took, just who gets to take the last one.) Which player has a strategy to guarantee that they win, and how do they do it?
The solution is below, so scroll down when you’re ready.
The solution …
The first player can win by moving to 24 tokens. Once they’re at a multiple of three tokens, they can always make sure that their next turn ends on the next lowest multiple of three. Here’s how: if their opponent takes 1 token, they take 2; if their opponent takes 2, they take 1. Then together, they take three tokens, so their next turn ends with 21 tokens.
They do this over and over to go down multiples of 3: 24, 21, 18, 15, 12, 9, 6, 3, and 0, and they win because they took the last token!
If you’re wondering how to figure this out, the trick is to think from the end. What happens with one token? Easy, the first player takes it and wins. Two tokens? The first player takes both and wins. Three tokens? Now the second player wins: the first player is forced to leave their opponent with 1 or 2 tokens, which their opponent can take and win.
That lets you build up. If you’re the first player with four tokens, take one piece and now it’s like you’re going second but with only three tokens. If you’re the first player with five tokens, take two, doing the same thing. But from six tokens, you’re stuck: you have to leave your opponent with four or five, which is a winning position for the next player to go.
If you want a challenge, try figuring out the same game, but instead of being able to take 1 or 2 tokens, you can take 1 or 4 tokens. Now what pattern emerges?
Want more math? If you are not yet receiving our quarterly newsletter, subscribe here.