Skip to main content

Section 1.1 Nimble

Let's play a two-player game called Nimble. The board is a strip of squares. Place some coins on the board, however you like. We can have empty squares, as well as multiple coins on a single square. Figure 1.1.1 shows a game with seven coins.

Figure 1.1.1. A game of Nimble.

During the game, the two players take turns, moving a single coin to the left. There are no restrictions on how far you can move the coin. You can jump onto or over other coins. You can have any number of coins on a square. You can even jump all the way off the strip! Once a coin is moved off of the strip, it is out of play. The winner is the person who makes the last move.

Exploration 1.1.1. Nimble.
Play some games of Nimble. You can draw your own board and use whatever markers you like for your "coins." You can use pennies, stones, bits of paper, anything. Try playing various games with one coin, two coins and three coins. Can you find a winning strategy for one coin Nimble? two coin Nimble? three coin Nimble?

Now that you've played Nimble, let's try to analyze the game. We name our two players Alice and Bob, where Alice plays first. Who wins the Nimble positions in Figure 1.1.2, Alice or Bob? Try to determine the winner of these games before you continue reading. We encourage you to actually play the games against a real opponent!

Figure 1.1.2. Some quick games of Nimble.

Position 1. It is pretty obvious that Alice (who plays first) can win Position 1 by moving the coin off the board. This leaves an empty board, so Bob cannot move. Alice made the last move, and this means that she wins.

Note that Alice could make a mistake and lose the game by moving the coin to the first square, setting up Bob for the win. But since Alice has at least one winning strategy, we consider this game to be Alice-win. (In this game, Alice has exactly one winning strategy, but we will encounter more complicated games that have multiple winning moves.)

Position 2. Position 2 is a Bob-win game. Here is a winning strategy for Bob (who plays second): just copy whatever move Alice made! If Alice moves a coin off the board, then Bob does as well, which ends the game. If Alice moves to the first or second square, Bob copies this move with the other coin. Once again, we have a single pile of two coins, so Bob can repeat this strategy.

We have a special name for this copycat strategy. Whenever the second player can repeatedly copy the first player, then the second player will win (since the second player always has a valid move). This is called the Tweedledum & Tweedledee Principle. 1 

You probably know that Tweedledum and Tweedledee are characters from Lewis Caroll's Through the Looking Glass. This disparaging term is used more generally to describe two people who look and act in identical ways.

Position 3. Position 3 is an Alice-win game. Can you see why? She can move the coin on square 5 to square 2. This sets up the Tweedledum & Tweedledee Principle with the player roles reversed.

Position 4. Position 4 also belongs to Alice. She can create a Tweedledum-Tweedledee position by moving the coin on square 5 to square 1. This time, we have two different Tweedles (on squares 1 and 4), with Alice controlling each of them.

Position 5. Position 5 is the most complicated game of the bunch. This game is Bob-win. No matter how Alice plays, Bob can respond by making a Tweedledum-Tweedledee position. We leave the proof as an exercise.