How Many Pennies Should You Pinch?

The Riddler for January 24, 2020. The Express counts the most players a Hall-of-Fame ballot can possibly admit; the Classic is a two-pile coin game, “Pinching Pennies,” that turns out to be a famous piece of game theory in disguise.

Riddler Express

There are $20$ players on the Baseball Hall of Fame ballot and $400$ voters. Each voter may select up to $10$ players (no player more than once), and a player is inducted only if named on at least $75\%$ of the ballots. What is the maximum number of players that can be inducted?

The Riddler, FiveThirtyEight, January 24, 2020(original post)

Solution

Count the votes two ways. Each of the $400$ voters names at most $10$ players, so at most $400 \times 10 = 4000$ votes are cast in total. Each inducted player needs at least $75\%$ of $400 = 300$ of them. If $k$ players are inducted they soak up at least $300k$ votes, and $300k \le 4000$ forces $$k \le \left\lfloor \tfrac{4000}{300} \right\rfloor = 13.$$

Thirteen is achievable. Label the players $A$ through $M$ and split the voters into four blocs of $100$, each bloc casting a full $10$ votes: $$\begin{aligned} &\text{bloc 1:}\ \ \texttt{A B C D E F G H I J}\\ &\text{bloc 2:}\ \ \texttt{D E F G H I J K L M}\\ &\text{bloc 3:}\ \ \texttt{A B C G H I J K L M}\\ &\text{bloc 4:}\ \ \texttt{A B C D E F J K L M} \end{aligned}$$ Now $J$ appears in all four blocs ($400$ votes), and each of the other twelve appears in exactly three ($300$ votes), so all $13$ clear the $300$ bar. The answer is $$\boxed{13}.$$ Notice the count depends only on the ballot cap and the threshold: $\lfloor 10 / 0.75 \rfloor = 13$, independent of the number of candidates or voters.

The computation

Tally the four-bloc construction to confirm $13$ players reach $300$ votes, and confirm $14$ is impossible against the $4000$-vote ceiling.

blocs = ["ABCDEFGHIJ", "DEFGHIJKLM", "ABCGHIJKLM", "ABCDEFJKLM"]
from collections import Counter
votes = Counter(p for b in blocs for p in b)   # each bloc = 100 voters
inducted = [p for p, c in votes.items() if 100*c >= 300]
print(len(inducted), 4000 // 300)              # 13 13
print(14 * 300 > 4000)                         # True: 14 impossible

The construction inducts $13$ players, matching the ceiling $\lfloor 4000/300\rfloor = 13$, while $14$ would need $4200 > 4000$ votes.

Riddler Classic

The game “Pinching Pennies” starts with between $20$ and $30$ pennies, which your opponent divides into two piles any way they like. You then alternate turns, you first: on a turn a player removes any positive number of pennies from one pile, or the same positive number from both piles. The player who takes the last penny wins. If both play optimally, which starting totals (between $20$ and $30$) guarantee that you can win?

The Riddler, FiveThirtyEight, January 24, 2020(original post)

Solution

Call a two-pile position $(x,y)$ cold if the player about to move from it loses under best play, and hot otherwise. The recursion is the usual one: a position is cold exactly when every legal move leads to a hot position. The empty position $(0,0)$ is cold (the mover has no penny to take, so the previous player took the last one and won). Building up from there, the cold positions are $$\begin{aligned} &(0,0),\ (1,2),\ (3,5),\ (4,7),\ (6,10),\\ &(8,13),\ (9,15),\ (11,18),\ (12,20),\ \ldots, \end{aligned}$$ the celebrated pairs of Wythoff’s game, whose coordinates track the golden ratio. From any other (hot) position the mover can always reach a cold one and hand the loss to the opponent.

Now read the puzzle’s roles carefully. Your opponent chooses how to split the total, and then you move first. A clever opponent will hand you a cold split if the total admits one, since the mover from a cold position loses. So you are guaranteed to win precisely when no split of the total is a cold position. The totals of the cold pairs above are $$0,\ 3,\ 8,\ 11,\ 16,\ 21,\ 24,\ 29,\ 32,\ \ldots,$$ and within $20$ to $30$ the only ones hit are $21 = 8+13$, $24 = 9+15$ and $29 = 11+18$. For every other total no split is cold, so you win. The guaranteed-win totals are $$\boxed{20,\ 22,\ 23,\ 25,\ 26,\ 27,\ 28,\ 30}.$$ On $21$, $24$ and $29$ the opponent wins by dealing you $8\!+\!13$, $9\!+\!15$ or $11\!+\!18$.

The computation

Label every position cold or hot by the recursion (a position is cold iff all its moves lead to hot positions), then for each total $20$ to $30$ test whether the opponent can choose a cold split; you win exactly when none exists.

M = 31
cold = [[False]*(M+1) for _ in range(M+1)]
for x in range(M+1):
    for y in range(M+1):
        moves  = [(x-k, y) for k in range(1, x+1)]
        moves += [(x, y-k) for k in range(1, y+1)]
        moves += [(x-k, y-k) for k in range(1, min(x, y)+1)]
        cold[x][y] = all(not cold[a][b] for a, b in moves) if moves else True
win = [n for n in range(20, 31)
       if not any(cold[a][n-a] for a in range(n+1) if a <= M and n-a <= M)]
print(win)            # [20, 22, 23, 25, 26, 27, 28, 30]

The totals with no cold split, hence guaranteed wins for you, are exactly the boxed eight.