Math Strategies and Game Theory: How to Win the Matchstick Game (Subtraction Game)
In elementary school you may have played a simple two-player math game called either "Matchsticks" or "Subtraction," and sometimes mistakenly called "Nim." (Nim is a different, though similar game.) At the start of the game you and your opponent are given a pile of N matches where the number N is known to both of you. On each of your turns, you can take up to K matches from the pile. The person who takes the last match loses, and the other is declared the winner.
Often N is set to 20 and K is set to 3. That is, the game starts with a pile of 20 matches and on each of your turns you can take 1, 2, or 3 matches from the pile.
If the number of matches N is of a certain form, and you start first, AND you know the secret winning strategy, then you can always force your opponent to grab the last match. This is a fun math trick to teach children and it shows how math can be applied in real life to their advantage. Your kids will also enjoy playing with other children who don't know the trick!
What conditions on the number N guarantee a win for the first player?
If K is fixed, then the first player has a 100% chance of winning so long as N is not of the form
(K + 1)*P + 1
where P is any non-negative integer. For example, suppose K = 3. Since K + 1 = 4, the first player can always win as long as N is not of the form 4P + 1. Explicitly, N cannot be equal to 1, 5, 9, 13, 17, 21, ... That means N can be equal to 2, 3, 4, 6, 7, 8, 10, 11, 12, 14, 14, 16, 18, 19, 20, ...
What happens if N is of the form (K + 1)*P + 1 but the second player doesn't know the strategy? In this case, the second player will probably eventually, unwittingly subtract a number of matches that reduces the pile to a number not of the form (K + 1)*P + 1. Then the first player can proceed with the strategy explained in the next section and win.
If N is of the form (K + 1)*P + 1 and the second player does know the strategy, then he or she can force the first player to grab the last match.
The game strategy is simple: Always subtract a number of matches that leaves the other player with a pile of size (K + 1)*P + 1. For example, if K = 3, then on each of her turns the first player must take away enough matches so that the number of remaining matches is 21, 17, 13, 9, 5, and eventually 1.
If K = 4, then the target numbers are of the form 5P + 1. Thus, the first player must always leave the second player with a pile whose size is 26, 21, 16, 11, 6, and eventually 1.
Example Game Play
Suppose N = 35 and K = 5. That is, the players start with 35 matches and on each of their turns they can subtract up to 5 matches from the pile. Since K + 1 = 6, and 35 is not of the form 6P + 1, Player 1 has a winning strategy so long as she subtracts enough matches to make the pile's size at a number of the form 6P + 1. Numbers of the form 6P + 1 are 31, 25, 19, 13, 7, and 1. Here is the game play:
Player 1: She subtracts 4 matches to leave 31 matches.
Player 2: No matter what he does, he cannot subtract enough matches to make the pile's size be 25 (because he can only take 1, 2, 3, 4 or 5 matches). So let's say he takes 3 matches, leaving 28 matches.
Player 1: She takes 3 matches, leaving 25.
Player 2: He takes 1 match, leaving 24.
Player 1: She takes 5 matches, leaving 19.
Player 2: He takes 4 matches, leaving 15.
Player 1: She takes 2 matches, leaving 13.
Player 2: He takes 5 matches, leaving 8.
Player 1: She takes 1 match, leaving 7.
Player 2: He takes 3 matches, leaving 4.
Player 1: She takes 3 matches, leaving 1.
Player 2: He is forced to take the last match, and therefore player 1 wins!
Now that you know the winning strategy, you can use this secret to play and win against people who haven't yet figured it out. The matchstick game is part of a broader class of games known as "Nim Games" in which the winning strategy depends on performing some modular arithmetic to keep the sum of the remaining objects at a number of a certain form. This is an excellent game to teach children the value of doing mental arithmetic quickly.
More Math Games and Activities
Here are more math puzzles, games, and problem solving tutorials to keep your mind sharp. Also great for homeschoolers to give their children extra math practice
- Mental Math Trick: Find the Cube Root of a Perfect Cube (up to 9 digits)
- How far do you need to walk with an ice cream cone to burn its calories?
- Number Puzzle 1 and Number Puzzle 2
- How to Solve Word Problems with Ages
More by this Author
Various polyhedral dice: cube, tetrahedron, dodecahedron, octahedron, icosahedron, pentagonal trapezohedron. When we think of "dice," what usually comes to mind is a small cube whose six faces are numbered...