# 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 Strategy

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!

## Have Fun!

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

## Comments

This game is suggested in my home school lesson plans as an alternative to subtraction drill sheets, but your explanation of the winning strategy is much clearer than the one given in my lesson book. My book only explains how to win for K = 3 and N = 30. The way you generalized the problem makes it easier to expand the game.

As I see it, the strategy is to make sure than on two sucessive turns, the number of matches take adds up to K. Starting with the 2nd and 3rd turns, then the 4th and 5th turns, then the 6th and 7th turns etcetera.

I think if you have more than one kid it's more fun to teach the strategy to the youngest so he can beat his older siblings!

Hi, may I ask if there is a strategy for different number of players but a fixed number for K and N? Or is there no possible strategy like this? Thank you. :)

Wow! Thank you so much for taking your time to answer my question! :)

I thought the matchstick game was everybody light a match at the same time and the last one to keep their match on fire in their hand is the winner. Your version sounds less painful, I will have to try it sometime.

6