Can You Flip Your Way To Victory?

The Riddler for February 21, 2020. The Express hunts for the temperature whose Fahrenheit and Celsius readings are digit-reversals of each other. The Classic is a coin-flipping game where you pick, flip by flip, between a low-stakes and a high-stakes coin and try to end with a positive score.

Riddler Express

Toggling a thermometer between Fahrenheit and Celsius, you notice the rounded reading’s two digits have simply swapped: $61^\circ$F is $16^\circ$C, for instance. But the temperature that warm, sunny day was not $61^\circ$F. What was it?

The Riddler, FiveThirtyEight, February 21, 2020(original post)

Solution

A warm day means a two-digit Fahrenheit reading $F = 10A + B$, with tens digit $A$ and ones digit $B$. Its Celsius value is $C = \tfrac59(F - 32)$, and we want $C$, rounded, to read $10B + A$ (the digits swapped). Ignoring the rounding for a moment, $$\begin{aligned} \tfrac59(10A + B - 32) = 10B + A &\;\Longrightarrow\; 50A + 5B - 160 = 90B + 9A\\ &\;\Longrightarrow\; A = \frac{85B + 160}{41}. \end{aligned}$$ Step $B$ through the digits $0$ to $9$ and round the resulting $A$:

• $B = 0$ gives $A \approx 3.9 \to 4$: that is $40^\circ$F $= 4^\circ$C, written “$04$,” a leading zero rather than a genuine swap (and hardly a warm day).

• $B = 1$ gives $A = 6$: that is $61^\circ$F $= 16^\circ$C, the example we are told to exclude.

• $B = 2$ gives $A \approx 7.95 \to 8$: that is $82^\circ$F, and $\tfrac59(82 - 32) = 27.\overline{7} \to 28^\circ$C. The digits swap, and it is genuinely warm.

• $B \ge 3$ gives $A > 10$, impossible for a single digit.

So the temperature was $$\boxed{82^\circ\text{F} = 28^\circ\text{C}}.$$

The computation

Encode the condition directly: for every two-digit Fahrenheit reading, round its Celsius value and keep those whose digits are the reverse.

def rev(n): return (n % 10)*10 + n // 10
matches = [F for F in range(10, 100) if round((F - 32)*5/9) == rev(F)]
print(matches)                                   # [40, 61, 82]

The three matches are $40$ (the degenerate “$04$” with a leading zero), $61$ (the excluded example) and $82$, leaving $82^\circ$F as the answer.

Riddler Classic

You have two fair coins. Coin A is worth $\pm 1$ point (heads $+1$, tails $-1$); coin B is worth $\pm 2$. You make $100$ flips, choosing which coin to flip each time knowing all earlier outcomes, and you win if your final score is strictly positive (any positive total is as good as any other). Optimising your strategy, what percentage of games do you win? Extra credit: what if coin A comes up heads with probability $p$ (coin B still fair)?

The Riddler, FiveThirtyEight, February 21, 2020(original post)

Solution

Work backwards. Let $W(s, k)$ be your best winning probability with score $s$ and $k$ flips left. With no flips left you win exactly when $s > 0$. With $k$ left you pick whichever coin gives the larger chance: $$W(s, k) = \max\bigl(\text{coin A},\ \text{coin B}\bigr),$$ where the two options are $$\begin{aligned} \text{coin A} &= \tfrac12 W(s{+}1, k{-}1) + \tfrac12 W(s{-}1, k{-}1),\\ \text{coin B} &= \tfrac12 W(s{+}2, k{-}1) + \tfrac12 W(s{-}2, k{-}1). \end{aligned}$$ Solving this from $k = 0$ up to $k = 100$ and reading off $W(0, 100)$ gives $$\boxed{\approx 64\%}$$ (precisely $0.6403$). It can exceed $50\%$ even though each coin is fair, because the policy is asymmetric: when your score is positive you flip the low-variance coin A to protect the lead, and when it is zero or negative you flip the high-variance coin B to give yourself a chance. Like running out the clock with a lead but speeding up when behind, this skews you toward small positive finishes and away from large negative ones, while keeping the average score at $0$. As the number of flips grows the winning probability rises toward $2/3$.

For the extra credit, the same recursion works with coin A landing heads with probability $p$ (only the coin-A line changes to $p\,W(s{+}1,k{-}1) + (1{-}p)\,W(s{-}1,k{-}1)$). The winning probability is then a nonlinear, S-shaped function of $p$: near $p = \tfrac12$ it sits close to the $\approx 64\%$ value, it climbs to a guaranteed win as $p \to 1$ (just keep flipping A), and it falls away as $p \to 0$ (you lean on B and cash in coin A only once its near-certain tails can no longer hurt you).

The computation

Encode the dynamic program: $W$ as an array over scores, stepped back $100$ times, taking the better coin at each score. The same routine, parameterised by $p$, answers the extra credit.

def win_prob(pA, N=100):
    off = 2*N
    V = [1.0 if s - off > 0 else 0.0 for s in range(4*N + 1)]   # k = 0
    for _ in range(N):
        nV = [0.0]*(4*N + 1)
        for s in range(4*N + 1):
            a = pA*V[min(4*N, s+1)] + (1 - pA)*V[max(0, s-1)]   # coin A
            b = 0.5*V[min(4*N, s+2)] + 0.5*V[max(0, s-2)]       # coin B
            nV[s] = a if a > b else b
        V = nV
    return V[off]
print(round(win_prob(0.5), 4))                   # 0.6403
for p in (0.4, 0.5, 0.6):
    print(p, round(win_prob(p), 4))              # 0.4 0.5357 / 0.5 0.6403 / 0.6 0.9797

The fair-coin game is won about $64\%$ of the time, and the extra-credit values trace the S-shaped rise in $p$.