Can You Flip Your Way To Freedom?

Riddler Express

Dakota Jones has found another highly symmetric crystal, and you must recreate it from her laser scanner, which records two-dimensional cross-sectional slices of a three-dimensional object along the third dimension. This time the looping animation shows the slices to be rectangles: a thin one that widens, becomes a square, then narrows back to a thin one at right angles to the first. What three-dimensional shape is the crystal?

The Riddler, FiveThirtyEight, May 1, 2020(original post)

Solution

A shape that is triangular from one direction but shows rectangular slices from another is the giveaway. Take a regular tetrahedron and pick two opposite edges (two edges that share no vertex). They are perpendicular to each other in space, and the segment joining their midpoints is perpendicular to both. Slice with planes perpendicular to that connecting segment.

Each such slice cuts all four of the slanted edges, and the four cut points form a rectangle whose two pairs of sides run parallel to the two opposite edges. As the plane travels from one edge to the other, one pair of sides grows from zero to full length while the other shrinks from full length to zero, in exact linear proportion. Halfway across, the two pairs are equal: the slice is a square. So the crystal is $$\boxed{\text{a regular tetrahedron}},$$ sliced between two opposite edges. (With unequal slice spacing the same picture fits any isosceles tetrahedron, or disphenoid; “highly symmetric” picks out the regular one.)

The computation

Take a regular tetrahedron, find two opposite edges, and slice with planes perpendicular to the segment joining their midpoints. Print the side lengths of each cross-section: they form rectangles, equal-sided (a square) exactly at the midpoint.

import numpy as np
V = np.array([[1, 1, 1], [1, -1, -1], [-1, 1, -1], [-1, -1, 1]], float)
m1, m2 = (V[0] + V[1]) / 2, (V[2] + V[3]) / 2          # midpoints, opposite edges
axis = (m2 - m1) / np.linalg.norm(m2 - m1)
e1 = np.array([0, 1, 0.0]); e1 -= (e1 @ axis) * axis; e1 /= np.linalg.norm(e1)
e2 = np.cross(axis, e1)                                 # in-plane basis
edges = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
def sides(t):
    P, pts = m1 + t * (m2 - m1), []
    for a, b in edges:
        da, db = (V[a] - P) @ axis, (V[b] - P) @ axis
        if da * db < 0:
            s = da / (da - db); pts.append(V[a] + s * (V[b] - V[a]))
    pts = np.array(pts); c = pts.mean(0); u = pts - c
    o = pts[np.argsort(np.arctan2(u @ e2, u @ e1))]
    d = [np.linalg.norm(o[i] - o[(i + 1) % len(o)]) for i in range(len(o))]
    return [round(float(x), 3) for x in d]
for t in (0.25, 0.5, 0.75):
    print(t, sides(t))
# 0.25 [0.707, 2.121, 0.707, 2.121]   rectangle
# 0.5  [1.414, 1.414, 1.414, 1.414]   square
# 0.75 [0.707, 2.121, 0.707, 2.121]   rectangle

Riddler Classic

You and three fellow prisoners (four in total) are in separate cells, unable to communicate. Each is given a fair coin, which may be flipped exactly once or handed back unflipped. If all coins that are flipped come up heads, everyone goes free; but if any flipped coin is tails, or if nobody flips at all, everyone stays imprisoned. Each prisoner also has a random number generator giving an independent uniform value between $0$ and $1$. What is your best chance of release? Extra credit: with $N$ prisoners instead of four?

The Riddler, FiveThirtyEight, May 1, 2020(original post)

Solution

The prisoners cannot talk, but they share a plan and they have private random numbers, so each can adopt the same rule: flip the coin if your random number is below a threshold $p$, otherwise return it. Then each prisoner independently flips with probability $p$, and every flipped coin is heads with probability $\tfrac12$. By symmetry the same $p$ is optimal for all.

The group wins when at least one prisoner flips and every flipped coin is heads. With each prisoner flipping-and-getting-heads with probability $\tfrac{p}{2}$ and not-flipping with probability $1-p$, summing over how many flip gives $$\Pr(\text{win}) = \Bigl(1 - \tfrac{p}{2}\Bigr)^{N} - (1-p)^{N},$$ the first term being “every flipped coin is heads” and the subtracted term removing the no-one-flips case. Setting the derivative to zero gives the optimal threshold through $$\frac{1-p}{1-\tfrac{p}{2}} = 2^{-1/(N-1)}.$$ For $N = 4$ this is $p \approx 0.342$, and the chance of release is $$\Bigl(1 - \tfrac{p}{2}\Bigr)^{4} - (1-p)^{4} \approx \boxed{28.5\%}.$$ For the extra credit the same formula applies. The optimal $p$ shrinks as the group grows (fewer should risk a flip), and the winning chance drifts down toward a limit: $N=2$ gives exactly $\tfrac13$, $N=3$ about $29.9\%$, $N=5$ about $27.7\%$, and $N=10$ about $26.3\%$.

The computation

Encode the actual scene: each prisoner flips when a uniform random draw falls below $p$, a flip is heads half the time, and the group wins on at least one flip with all flips heads. Sweep $p$ to find the best threshold for $N=4$.

import numpy as np
rng = np.random.default_rng(0)
def win_rate(N, p, trials=2_000_000):
    flip = rng.random((trials, N)) < p                 # who flips
    heads = rng.random((trials, N)) < 0.5
    flipped_any = flip.any(axis=1)
    all_heads = (~flip | heads).all(axis=1)            # every flipped coin is heads
    return (flipped_any & all_heads).mean()
best = max((round(0.001 * k, 3) for k in range(1, 1000)),
           key=lambda p: win_rate(4, p, 400_000))
print("best p ~", best, " win ~", round(win_rate(4, best), 4))   # ~0.342, ~0.285

The simulation peaks near $p = 0.342$ with a release probability of about $0.285$, matching the formula.