Flipping Coins and a Deadly Board Game

The Riddler for October 14, 2016. The Express is the classic factor-counting flip; the Classic is a survival game whose answer turns on where the random walk likes to land.

Riddler Express

You place 100 coins heads up in a row, numbered 1 to 100 from the left. Then, for every number $N$ from 1 to 100, you flip every coin whose position is a multiple of $N$. (First you flip all of them, then all the even ones, then 3, 6, 9, …, and so on.) When you are done, which coins are heads down?

The Riddler, FiveThirtyEight, October 14, 2016(original post)

Solution

A coin ends heads down exactly when it has been flipped an odd number of times, so the whole puzzle reduces to counting flips. Coin $k$ gets flipped once for each $N$ that divides $k$, because the pass for $N$ touches every multiple of $N$, and $k$ is a multiple of $N$ precisely when $N$ is a divisor of $k$. (Divisors of $k$ never exceed $k$, and we run $N$ up to 100, so every divisor gets its turn.) Coin $k$ is therefore flipped once per divisor of $k$, and it ends heads down when $k$ has an odd number of divisors.

Divisors come in pairs: if $d$ divides $k$, so does $k/d$, and the two are different numbers, contributing two divisors at once. The only way to break a pair is to have $d = k/d$, that is $k = d^2$. So the divisor count is odd exactly for the perfect squares, where one divisor (the square root) stands alone. The heads-down coins are $$\boxed{1,\ 4,\ 9,\ 16,\ 25,\ 36,\ 49,\ 64,\ 81,\ 100.}$$

The computation

Encode the flipping literally: keep 100 booleans, run the 100 passes, and read off the heads-down positions. They should be exactly the squares.

coins = [True] * 101                      # coins[1..100], True = heads up
for N in range(1, 101):
    for pos in range(N, 101, N):          # every multiple of N
        coins[pos] = not coins[pos]
down = [k for k in range(1, 101) if not coins[k]]
print("heads down:", down)
# heads down: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Riddler Classic

In the Kingdom of Arbitraria, guilt is decided by a board game. Your token starts on space 0 of a track numbered 0 to 1,000. You place three coins on three different nonzero spaces. Then you roll a fair die and move forward that many spaces, repeatedly. If you land exactly on a coin, you are freed; if you pass all three without landing on one, you are executed. Where should the three coins go to maximise your chance of survival?

Extra credit: if coins may not sit on adjacent spaces, where do they go? And where would you place them to minimise survival, with and without the no-adjacency rule?

The Riddler, FiveThirtyEight, October 14, 2016(original post)

Solution

The token does a forward random walk in steps of 1 to 6, and you want it to step exactly onto one of your coins. The right quantity to think about is the landing probability of a space: the chance the token ever sets down on it. Two facts about that probability decide everything.

Far from the start, every space is equally likely. Once the walk has run a while it forgets where it began, and since the average step is $3.5$, it lands on about one space in every $3.5$, a long-run landing probability of $\tfrac{1}{3.5} = \tfrac{2}{7} \approx 0.286$ for each space. Out in this plateau it barely matters where a coin sits, so the length of the board (1,000, or a million) is a red herring.

Near the start the walk lands more often, and the early spaces are not independent. Climbing out of space 0 the landing probability rises above the $\tfrac27$ plateau and peaks at space 6, the single best square: you can reach it in one roll of a 6, and if you undershoot you get more chances. Space 5 is next best, then 4. Crucially, two nearby spaces are positively correlated, landing on 6 makes you much more likely to also land on 11, so scattering coins across the plateau wastes them on correlated $\tfrac27$ chances. Bunching them on the three richest early spaces does better.

So the contest is really 4 versus 7 for the third coin alongside 5 and 6. Conditioning on the first roll settles it. With coins on $4,5,6$ you survive if you roll a $4$, $5$, or $6$ now (probability $\tfrac12$), and otherwise you get another go from a space that still has all the good squares ahead; carrying the recursion through gives $$P(4,5,6) = \tfrac12 + \tfrac16\bigl(0.5 + 0.083 + 0.097 + 0.113\bigr) \approx 0.794,$$ against $P(5,6,7) \approx 0.758$. The best placement is therefore $$\boxed{\{4,5,6\}, \quad \text{surviving about } 79.4\%}.$$

Extra Credit

No two coins adjacent; and the worst placements.

Solution

The same landing-probability picture answers all the variants, and a search over placements confirms each. Forbidding adjacency knocks out $4,5,6$, and the best spread-but-still-early choice is $$\boxed{\{6,8,10\}, \quad \text{about } 71.4\%}.$$ For a death wish, you want the spaces the walk reaches least. Space 1 can only be reached by a single opening roll of $1$ (probability $\tfrac16$) and never again, so it is the worst square, and stacking coins on low, mutually-reachable spaces compounds the waste: the minimum is $$\boxed{\{1,2,7\}, \quad \text{only } 47.5\%},$$ and under the no-adjacency rule the worst becomes $\{1,3,7\}$ at about $50.3\%$.

The computation

Encode the game exactly: push probability forward from space 0 in steps of $\tfrac16$, absorbing the mass that lands on a coin, and sum the absorbed mass for the survival chance. Then search all triples to confirm the best and worst placements (the answer is stable well before the board’s far end, so a short board suffices).

from itertools import combinations
def survival(coins):
    coins = set(coins); top = max(coins)
    reach = [0.0] * (top + 7); reach[0] = 1.0   # prob arriving at a space, still in play
    win = 0.0
    for n in range(top + 1):
        if n in coins:
            win += reach[n]                       # landed on a coin -> freed
            continue
        for k in range(1, 7):
            reach[n + k] += reach[n] / 6
    return win

print("4,5,6 :", round(survival([4,5,6]), 4), "  5,6,7 :", round(survival([5,6,7]), 4))
triples = list(combinations(range(1, 40), 3))
nonadj  = [c for c in triples if all(c[i+1]-c[i] >= 2 for i in range(2))]
print("best   :", max(triples, key=survival), round(survival(max(triples, key=survival)), 4))
print("worst  :", min(triples, key=survival), round(survival(min(triples, key=survival)), 4))
print("best  non-adjacent:", max(nonadj, key=survival), round(survival(max(nonadj, key=survival)), 4))
print("worst non-adjacent:", min(nonadj, key=survival), round(survival(min(nonadj, key=survival)), 4))
# 4,5,6 : 0.794   5,6,7 : 0.7596
# best   : (4, 5, 6) 0.794
# worst  : (1, 2, 7) 0.4754
# best  non-adjacent: (6, 8, 10) 0.7137
# worst non-adjacent: (1, 3, 7) 0.5032