Penny Pinching

This is a spin on the classical game called Nim, which dates back to the beginning of the 16th century, but it wasn’t until 1901 when Charles L. Bouton of Harvard came up with the name “Nim” and developed the complete mathematical theory surrounding the game. In classical Nim, there can be many piles of coins, but you can only remove coins from one of the piles during your turn. The “Penny Pinching” variant in this week’s Riddler Classic is known as Wythoff’s Game and the theory surrounding it is quite fascinating. I’ll try to explain it in my own words here.

Each position can be described by a pair $(a,b)$ (the number of pennies in each pile). A position is called “safe” if it’s safe for me to leave the coins in this particular arrangement; no matter what the other player does, they can never win the game. By default, $(0,0)$ is safe, since reaching this position means I won the game.

For example, $(1,2)$ is safe because my opponent’s only legal moves are:

1. Remove from the first pile to obtain $(0,2)$.
2. Remove from the second pile to obtain $(1,1)$ or $(1,0)$.
3. Remove from both piles to obtain $(0,1)$.

In all of these cases, we can win in one move, so $(1,2)$ is a safe position for us. There are two key properties of safe positions:

1. It is impossible to reach a safe position from another safe position in one move. If this were possible, then our opponent could move to a safe position and then they would be the safe ones!
2. From any unsafe position, it is possible to move to a safe position in one move. This is because if we start from a safe position, then by definition we must be able to return to a safe position whenever it’s our turn again.

One way to generate safe positions is to draw a lattice. Each cell $(a,b)$ corresponds to a position of the game. We can color each cell green if it is safe and red if it is unsafe. We can do this iteratively, starting by marking $(0,0)$ safe and then proceeding as described in the following diagram:

Here is Python snippet that generates a solution grid of any size:

import numpy as np
N = 51  # change this for a different number of points
A = np.zeros((2*N,2*N),int)
for i in range(2*N):
    for j in range(i+1):
        A[i-j,j] = ~( (A[:i-j,j]==1).any() |
                      (A[i-j,:j]==1).any() |
                      (np.diag(A[i-j-1::-1,j-1::-1])==1).any() )

We can then visualize the grid using the Python code below:

import matplotlib.pyplot as plt
import matplotlib.cm as cm

fig,ax = plt.subplots(figsize=(9,9))
ax.imshow(A[:N,:N], origin='lower', interpolation=None, cmap=cm.Blues)
ax.set_xticks(range(N), minor=True)
ax.set_yticks(range(N), minor=True)
ax.grid(which='minor', color='lightgray')
ax.grid(which='major', color='dimgray')
ax.plot([0,20],[20,0],'r--')
ax.plot([0,30],[30,0],'r--')
ax.set_xlabel('coins in first pile')
ax.set_ylabel('coins in second pile')
ax.set_title("Safe combinations in Pinching Pennies (Wythoff's game)")

The resulting figure (for $N=51$) is:

When the game begins, I get to split the coins any way they like. For example, if there are 20 pennies, then I get to pick any starting position along the lower red dashed diagonal (these are the positions for which the total number of coins in both piles is 20). Since there are no safe positions along this diagonal, I cannot play safe, so I will lose. However, if the initial number of pennies is: 3, 8, 11, 16, 21, 24, 29, 32, 37, 42, 45, 50, 55, 58, 63, 66, 71, 76, 79, 84, 87, 92, 97, 100,… (the diagonals that contain safe positions) then I can split the coins to reach a safe position and therefore win. This sequence of numbers is interesting enough that it got its own name: the Wythoff AB numbers.

The distribution of safe positions seems to form lines on the plot above, but upon closer inspection, there is no obvious pattern in how the points are distributed. However, Wythoff was able to prove that the slopes of these lines are $\varphi$ and $\varphi^{-1}$, where $\varphi= \tfrac{1}{2}(1+\sqrt{5}) \approx 1.618$ is the golden ratio! Not only that, we can generate all safe pairs using the formula:

$\displaystyle
\text{The set of all safe pairs }(a,b)\text{ with }a \le b\text{ is}\quad\left( \bigl\lfloor n \varphi\bigr\rfloor,\, \bigl\lfloor n \varphi^2 \bigr\rfloor \right)\quad\text{for }n=0,1,2,\dots
$

Where $\lfloor x \rfloor$ is the floor function, i.e. the integer you get by rounding down. This generates the steeper line on the plot above. We can get the other half of the points by swapping the two coordinates. This means that the starting player can always win the game when the starting number of pennies is of the form:

$\displaystyle
\bigl\lfloor n \varphi\bigr\rfloor + \bigl\lfloor n \varphi^2 \bigr\rfloor \quad\text{for }n=0,1,2,\dots
$

When we substitute the formula above using for example the Python code below, we obtain Wythoff’s sequence:

import numpy as np
phi = (1+np.sqrt(5))/2
np.array([ int(np.floor(n*phi) + np.floor(n*phi**2)) for n in range(1,118) ])

# OUTPUT:
array([  3,   8,  11,  16,  21,  24,  29,  32,  37,  42,  45,  50,  55,
        58,  63,  66,  71,  76,  79,  84,  87,  92,  97, 100, 105, 110,
       113, 118, 121, 126, 131, 134, 139, 144, 147, 152, 155, 160, 165,
       168, 173, 176, 181, 186, 189, 194, 199, 202, 207, 210, 215, 220,
       223, 228, 231, 236, 241, 244, 249, 254, 257, 262, 265, 270, 275,
       278, 283, 288, 291, 296, 299, 304, 309, 312, 317, 320, 325, 330,
       333, 338, 343, 346, 351, 354, 359, 364, 367, 372, 377, 380, 385,
       388, 393, 398, 401, 406, 409, 414, 419, 422, 427, 432, 435, 440,
       443, 448, 453, 456, 461, 464, 469, 474, 477, 482, 487, 490, 495])

If you’re interested in the original proof of this formula (or a fascinating glimpse into what written mathematics looked like in the early 20th century), here is Wythoff’s original paper from 1907.