Games as Numbers
The Game of Hackenstrings
Hackenstrings is a two-player game about capturing tokens. To play, you need a collection of tokens in two colors, which we will assume are Black and White. One player owns the black tokens, the other owns white. Begin by arranging the tokens in rows; there can be any number of rows, any number of tokens in each row, and any mix of black and white tokens in each row that you like. You do not need to use the same number of black and white tokens.
The goal of Hackenstrings is to make it so that your opponent has no legal move. A move consists of choosing a token of your own color and removing it from the board, along with all tokens to the right of it.
Puzzles
- If black moves first, who wins each of these games? What if white moves first?
- Draw the game tree for a few of these games and evaluate the corresponding trees to verify your solutions to each game. For each game you will need to make two trees, one for when black goes first and one for when white goes first.
Hackenstrings Arithmetic
Let us call a Hackenstrings position positive if black wins no matter who goes first, negative if white wins no matter who goes first, and zero if the first player to move loses.
- What is the value of the empty position? (that is, the position with no rows at all)
- Which of the games above are positive? Negative? Zero?
- Does a single-row game of Hackenstrings starting with a black token have to be positive?
- Is it ever advantageous to take a token which is not as far to the right as possible?
If we are given two Hackenstrings positions, we can add them together by stacking the rows. Let us give the Hackenstrings position with a single row of n black tokens the value +n.
- What is the value of a single row of n white tokens? Show your answer makes sense by proving that the game with two rows of equal length, one all white and one all black, has value zero.
- Generalize your proof to show that swapping all the colors in a game of Hackenstrings multiplies the value by -1.
- Define an ordering for Hackenstrings games. That is, define what it means for one position to be greater than or equal to another. If A, B, and C are Hackenstrings games and A is greater than B, is A + C always greater than B + C?
- Find a game of Hackenstrings with a value of +1/2 (hint #1: two copies of the game along with a single white token must be a loss for the first player to move. hint #2: there is a game with value +1/2 that only involves one row of tokens.)
- What is the value of a black token followed by n white tokens?
Really Large and Really Small Games
We have seen how Hackenstrings games can have integer values and certain fractional values. If we allow our rows of tokens to become infinitely long, we can find even more exotic numbers.
- Is the first game above positive or negative? Use the values of games you know to approximate its value. Once you have a guess, verify that your guess is correct.
- The second game has an infinitessimal (infinitely small) positive value. Prove this by showing that it is positive but less than 1/(2n) for every n.
- The third game has an infinite positive value which we call omega. Prove this by showing that no matter how large n is, adding a row of n white stones still gives a positive game.
- What is the value of the fourth game compared to the third game?
Using the Hackenstrings rules, try to find even more infinite or even more infinitessimal games!
Further Reading
Back to index
