How to Be a Player: Impartial Combinatorial Games

1.

Create the game tree for single nim heap nim with three beans.

2.

Create the game tree for the Nim position \(\{2, 1 \}\text{.}\) Indicate whether each position in the game tree is an \(\cN\)-position or a \(\cP\)-position.

3.

Find the decimal representation of the following binary numbers:

1. 1101

2. 110110

3. 10101

4.

Find the binary representations of the following decimal numbers:

1. 25

2. 100

3. 800

5.

Convert the numbers in equation (2.2.1) to decimal representations. Check that you get the same answer when you sum these decimal numbers.

6.

Calculate the following in binary

1. \(\displaystyle 1011 + 1110\)

2. \(\displaystyle 1011 \oplus 1110\)

7.

Here is a cool magician's trick. The magician gives these six cards to an audience member.

The magician asks her to pick a number that appears on at least one of the cards, and then sort the cards into two piles: those that contain her number and those that do not. After some deep concentration, the magician reads her mind, and correctly guesses her number!

Here are some examples:

1. Explain how the magician's trick works. (Hint: look at the number in the upper left hand corner of each card.)

2. Explain why the magician's trick works. What do all of the numbers on a given card have in common? Why does a subset of cards uniquely determine a single number?

3. What number am I thinking of if...

   1. the number appears on cards 2, 3 and 4?

   2. the number appears on cards 2, 4, and 6?

   3. the number appears on cards 1, 2, 3, and 5?

8.

In grade school, you had to create addition tables and times tables so that you could learn how these operations worked. We need to do the same with Nim addition. Here is the Nim addition table for the numbers 0 through 3.

Create a nim sum addition table for the numbers 0 through 7. Comment on any patterns that you see.

9.

Extend the nim sum addition table from the previous problem to include the numbers 0 through 15. Comment on the remarkable patterns that you see.

10.

In this problem, you will prove . For any integers \(a,b,c\text{,}\) prove that the following hold.

1. Additive inverse law: \(a \oplus a = 0\text{,}\)

2. Commutative law: \(a \oplus b = b \oplus a\text{,}\)

3. Associative law: \((a \oplus b) \oplus c = a \oplus (b \oplus c)\text{.}\)

11.

Typically, the sum of two numbers \(n + m\) is not equal to their nim sum \(n \nimsum m\text{.}\) Under what conditions on \(n\) and \(m\) do we have the equality \(n+m = n \nimsum m\text{?}\) Explain.

12.

This problem fills in some details about powers of 2.

1. Use induction to prove that

   \begin{equation*} \sum_{i=0}^{n-1} 2^i = 2^{n} -1. \end{equation*}

2. Use part (a) to prove that if \(k_1 > k_2 > \cdots k_r \geq 0\) then

   \begin{equation*} 2^{k_1} > \sum_{i=2}^{r} 2^{k_i}. \end{equation*}

13.

Determine whether each of these games of Nim is in an \(\cN\)-position or a \(\cP\)-position. If it is an \(\cN\)-position, then list every winning move for the Next player.

1. \(\displaystyle \{ 1, 3, 5, 7 \}\)

2. \(\displaystyle \{ 12, 7, 15 \}\)

3. \(\displaystyle \{ 20, 55, 12, 40 \}\)

14.

Determine whether each of these games of Nim is in an \(\cN\)-position or a \(\cP\)-position. If it is an \(\cN\)-position, then list every winning move for the Next player.

1. \(\displaystyle \{ 13, 6, 21, 7 \}\)

2. \(\displaystyle \{ 8, 10, 12 \}\)

3. \(\displaystyle \{ 26, 15, 38, 21, 37 \}\)

15.

Explain why there are always an odd number of winning moves from an \(\cN\)-position.

16.

Prove that the \(\cN\)-positions and \(\cP\)-positions of Poker Nim are exactly the same as the \(\cN\)-positions and \(\cP\)-positions of Nim. In particular, be sure to explain how the winning player can prevent the game from going on forever.

17.

Explain how two players of Poker Nim could work together to make the game last forever. What is the minimum number of beans that these players need to pull this off?

18.

Let's add a third kind of move to Poker Nim: you can create a brand new nim heap on the board using beans in your personal cache. Does this change who wins the game?

19.

Discover the secret to playing Northcott's Game.

1. Play Northcott's Game with one Blue checker and one Red checker on a single row. Who wins?

2. Play Northcott's Game using two rows. Who wins this game?

3. Prove that Northcott's Game is actually Nim in disguise (with bogus heaps). Be sure to explain what the heap sizes are, why they are bogus heaps, and how you can determine who the winner will be.

20.

In the previous question, you explained how to map a position in Northcott's Game to a position in Nim. Use nim sums to decide whether the positions of Northcott's Game in Figure 2.5.1 are \(\cN\)-positions or \(\cP\)-positions.