Pick Up Sticks And Help A Frogger Out

Riddler Express

You and a friend play Marienbad. Matchsticks are arranged in four rows of $1$, $3$, $5$, $7$. You alternate turns; on your turn you pick any single row and remove between $1$ and all of its remaining sticks. The player who picks up the last stick loses. You go first. Do you win? If so, what is your strategy?

The Riddler, FiveThirtyEight, November 3, 2017(original post)

Solution

You lose against perfect play. The game is the misère version of Nim (the loser takes the last stick), and the starting position $(1, 3, 5, 7)$ is a Player-2 win.

Ordinary Nim. The XOR of pile sizes, called the nim-sum, is the central invariant of Nim. Write each pile in binary, add column-by-column without carries (i.e. XOR), and read the result. With $1 = 001, 3 = 011, 5 = 101, 7 = 111$, $$1 \oplus 3 \oplus 5 \oplus 7 = (001) \oplus (011) \oplus (101) \oplus (111) = 000 = 0.$$ A position with nim-sum $0$ is called a P-position (previous-player wins). The Bouton theorem says: in ordinary Nim (last stick wins) the P-positions are exactly the zero-XOR positions, and any non-zero position can be moved to a zero one in a single legal move.

Misère Nim. The loser takes the last stick. The strategy is the same as ordinary Nim while at least two piles have at least two sticks; once the position consists entirely of singleton piles, the parity rule flips. Specifically: if exactly one pile has $\ge 2$ sticks, play it so the resulting position is an odd number of singleton piles, so the opponent takes a stick (no choice) and you keep parity. With one pile of $\ge 2$ sticks the choice between leaving (k singletons) or (k singletons + 1) is yours. A short induction confirms: $(1,3,5,7)$ has XOR zero, so the first player to move from it always faces a non-zero XOR, and as long as multiple multi-stick piles remain, every Player-2 reply returns the position to XOR zero; once at most one multi-stick pile remains, Player $2$’s singleton parity flip wins.

The losing prognosis for you. You start at $(1, 3, 5, 7)$. Whatever you do, the resulting nim-sum is non-zero (any move changes exactly one pile’s binary digits, hence changes the XOR). Player $2$ has a move to a zero-XOR position; she can keep doing this throughout the multi-multi-pile phase. By the time only one multi-stick pile remains she switches to the misère parity rule and forces you to take the last stick.

$$\boxed{\,\text{You lose against perfect play.}\,}$$

The computation

Compute the game value of every position by backward induction. A position is a P-position (current player to move loses) iff every legal move leads to an N-position (next-player-wins); an N-position has at least one move to a P-position. Search the whole game tree from $(0,0,0,0)$ upward.

1. State: a sorted tuple of pile sizes.

2. Base: the all-zero position. Whoever’s turn it is cannot move because no sticks remain; but by the rules, the loser took the last stick, so the current player wins (the previous player took the last stick). So $(0,0,0,0)$ is a win-now (the previous mover lost).

3. Recursion: a position is N (current player wins) iff some legal move yields a P (current-to-move loses for the opponent).

4. Evaluate $(1,3,5,7)$.

from functools import lru_cache

@lru_cache(None)
def current_player_wins(state):
    # state: sorted tuple of pile sizes. Last stick LOSES.
    if sum(state) == 0:
        return True                                  # opponent took last stick
    for i, p in enumerate(state):
        for k in range(1, p + 1):                    # take k from pile i
            new = list(state); new[i] -= k
            new = tuple(sorted(new))
            if not current_player_wins(new):
                return True                          # move to opp-losing position
    return False

print(current_player_wins((1, 3, 5, 7)))             # False -> you lose

The recursion declares $(1,3,5,7)$ a loss for the player to move, matching the Nim analysis.

Riddler Classic

A frog needs to jump across $20$ lily pads. He starts on the shore (number $0$) and ends precisely on the last lily pad (number $20$). He can jump one or two lily pads at a time. How many different ways can he reach his destination? What if he can jump one, two, or three at a time? Or four? Five? Six?

The Riddler, FiveThirtyEight, November 3, 2017(original post)

Solution

Let $W_n$ be the number of distinct ways to reach pad $n$. With jumps of one or two pads, the frog’s final hop onto pad $n$ comes either from pad $n-1$ or from pad $n-2$, and those two families of routes are disjoint, so $$W_n = W_{n-1} + W_{n-2}, \qquad W_1 = 1,\ W_2 = 2.$$ This is the Fibonacci sequence shifted by one, $W_n = F_{n+1}$, giving $$W_{20} = F_{21} = \boxed{10946}.$$

If the frog can jump up to $k$ pads at a time, the same disjoint-last-jump argument gives the $k$-term recurrence $W_n = W_{n-1} + W_{n-2} + \cdots + W_{n-k}$, with $W_0 = 1$ and $W_m = 0$ for $m < 0$. Counting routes to pad $20$:

Once $k \ge 20$ every jump pattern is allowed, and the total is the number of compositions of $20$, namely $2^{19} = 524288$.

The computation

Rather than trust the recurrence, enumerate the frog’s routes outright: from the current pad try every legal jump and recurse, counting each sequence of hops that lands exactly on pad $20$. The brute-force totals reproduce the table.

def count_routes(n, k):                              # every jump sequence summing to n
    if n == 0:
        return 1                                     # arrived exactly on the far pad
    return sum(count_routes(n - j, k) for j in range(1, min(k, n) + 1))
print(count_routes(20, 2))                           # 10946
print([count_routes(20, k) for k in (3, 4, 5, 6)])
print(count_routes(20, 20), 2 ** 19)                 # 524288, 524288