Game Theory Puzzles: Pirates, Nim and Backward Induction

In a finite two-player game with no chance, nothing hidden and no draws, every position is either a win or a loss for the player about to move. Backward induction labels positions starting from the end. A position is a win if some move leads to a loss for the opponent, and a loss if every move leads to a win for the opponent. Once every position is labelled, the strategy is to always move to a loss.

Take the race to 100. Two players take turns adding a number from 1 to 10 to a running total that starts at 0, and whoever says 100 wins. If you say 89, your opponent can reach anything from 90 to 99 but cannot reach 100, and you finish from wherever they land. So saying 89 guarantees the win. By the same argument saying 78 guarantees you can say 89, and stepping down by 11 each time gives the totals you want to say:

The first player opens with 1 and answers each opponent move $m$ with $11 - m$. In general, with moves from $1$ to $k$ and target $N$, you want to say the totals congruent to $N$ modulo $k+1$. If $N$ is a multiple of $k+1$, the opening total 0 is already one of them, and the second player wins.

The code does the labelling mechanically. In an interview, do the last few positions by hand, spot the period, then state the rule.

def losing_totals(target, k):
    # win[t]: the player to move at total t can force saying target
    win = [False] * (target + 1)
    for t in range(target - 1, -1, -1):
        win[t] = any(t + m == target or (t + m < target and not win[t + m])
                     for m in range(1, k + 1))
    return [t for t in range(target) if not win[t]]

print(losing_totals(100, 10))  # [1, 12, 23, 34, 45, 56, 67, 78, 89]