Inside The Cube And The Three-Lock Safe

Riddler Express

Take a unit cube. One face diagonal runs from $(0,0,0)$ to $(0,1,1)$. A second diagonal runs from $(0,1,0)$ to $(1,0,1)$. Find the coordinates of the two endpoints of the shortest segment bridging the gap between these two skew diagonals.

The Riddler, FiveThirtyEight, December 1, 2017(original post)

Solution

Parametrise points on the two diagonals. $$P(y) = (0, y, y), \qquad y \in [0, 1] \text{ (first diagonal)},$$ $$Q(x) = (x, 1 - x, x), \qquad x \in [0, 1] \text{ (second diagonal)}.$$

The squared distance is $$\begin{aligned} D^2(x, y) &= x^2 + (1 - x - y)^2 + (x - y)^2 \\ &= 3x^2 - 2x + 2y^2 - 2y + 1. \end{aligned}$$ Setting $\partial D^2/\partial x = 6x - 2 = 0$ and $\partial D^2/\partial y = 4y - 2 = 0$ gives $$x = \tfrac{1}{3}, \qquad y = \tfrac{1}{2}.$$ Both values sit strictly inside $[0, 1]$, so the optimum is interior to each diagonal. The endpoints are $$\mathrm{ep}_1 = \left(0, \tfrac{1}{2}, \tfrac{1}{2}\right), \qquad \mathrm{ep}_2 = \left(\tfrac{1}{3}, \tfrac{2}{3}, \tfrac{1}{3}\right),$$ and the minimum length is $$\begin{aligned} D &= \sqrt{3 \cdot \tfrac{1}{9} - \tfrac{2}{3} + 2 \cdot \tfrac{1}{4} - 1 + 1} = \sqrt{\tfrac{1}{3} - \tfrac{2}{3} + \tfrac{1}{2}} \\ &= \sqrt{\tfrac{1}{6}}. \end{aligned}$$

$$\boxed{\,\mathrm{ep}_1 = (0, \tfrac{1}{2}, \tfrac{1}{2}),\ \mathrm{ep}_2 = (\tfrac{1}{3}, \tfrac{2}{3}, \tfrac{1}{3}),\ \text{length } = \tfrac{1}{\sqrt 6} \approx 0.408.\,}$$

Why this is the global minimum. The function $D^2$ is a positive-definite quadratic in $(x, y)$ (its Hessian is the diagonal matrix $\mathrm{diag}(6, 4)$), so the critical point is its unique global minimum. The fact that the optimum lies strictly inside both parameter intervals confirms that the segment between $\mathrm{ep}_1$ and $\mathrm{ep}_2$ is the common perpendicular of the two lines, and its length is the standard skew-line distance.

The computation

Solve the optimisation symbolically with sympy; this independently re-encodes the geometric problem (two parametrised lines, the squared-distance functional, and its minimum) rather than the closed-form derivation above.

1. Define the parameter variables and the two parametrised points.

2. Form the squared-distance function.

3. Solve the system $\nabla D^2 = 0$.

4. Evaluate the endpoints and the distance.

import sympy as sp

x, y = sp.symbols('x y', real=True)
P = sp.Matrix([0, y, y])                                  # first diagonal
Q = sp.Matrix([x, 1 - x, x])                              # second diagonal
D2 = sum((P - Q).T * (P - Q))
sol = sp.solve([sp.diff(D2, x), sp.diff(D2, y)], [x, y])
ep1 = P.subs(sol)
ep2 = Q.subs(sol)
dist = sp.sqrt(D2.subs(sol))
print(ep1.T, ep2.T, sp.simplify(dist))           # (0,1/2,1/2) (1/3,2/3,1/3) sqrt(6)/6

Sympy returns the same endpoints and minimum distance $\sqrt{6}/6 = 1/\sqrt{6}$.

Riddler Classic

A safe has three locks (1, 2, 3) and three key cards (A, B, C). Each lock is opened by a unique card; you do not know which card belongs to which lock. You insert the three cards into the three slots in some order and press the attempt button. Each lock whose correct card was inserted at the moment of the press flips state (locked $\leftrightarrow$ unlocked); the other locks do not change. The safe opens when all three are unlocked, and you cannot tell partial progress. What is the minimum number of attempts that guarantees opening the safe, and what sequence works?

The Riddler, FiveThirtyEight, December 1, 2017(original post)

Solution

The answer is $13$ attempts.

Reframing. The catch is the double hidden information: the initial lock states (an unknown element of $\mathbb{F}_2^3$) and the unknown card-to-lock bijection $f$. A press is a permutation $\pi$ of the cards into the three slots. Under labelling $f$, lock $i$ flips at this press iff $\pi(i) = f(i)$. So a single press performs different lock-flip operations under different $f$’s. The six possible $f$’s and six press permutations give a $6 \times 6$ table of lock-flip patterns; for any fixed $f$, the six presses produce one identity-permutation ($F_{123}$), three single-fixed-point permutations ($F_1, F_2, F_3$), and two derangement permutations ($\Phi$, no flips). Crucially, the press that achieves $F_{123}$ depends on $f$.

A strategy is a fixed sequence of $n$ press permutations chosen before you know $f$ or the initial state; it succeeds if, for every one of the $6 \times 8 = 48$ hidden configurations, some prefix of the sequence drives the locks to all-open.

A combinatorial bound. For each fixed $f$, the sequence of presses induces a walk of $n$ steps in $\mathbb{F}_2^3$ (starting at $0$, jumping by a flip pattern per press); it must reach every one of the $8$ states at some prefix XOR, to handle every initial state under that $f$. Across the $6$ different $f$’s the walks share the same press sequence but interpret it differently, and the coupling is what makes $7$ presses (the bare-minimum to enumerate $\mathbb{F}_2^3$) insufficient. An exhaustive computer search (Igor Kopylov’s, cited in the official write-up) confirms that no strategy of length $\le 12$ works for all $48$ configurations, and a strategy of length $13$ does:

The computation

Encode the puzzle’s two hidden variables ($f$ and the initial state) and confirm the cited $13$-press sequence opens the safe under every one of the $48$ hidden configurations.

1. Enumerate the six possible card-to-lock bijections $f$.

2. For each $f$ and each of the $7$ nonzero initial states, walk the press sequence and find the first prefix where all three locks are unlocked.

3. Report success and the worst-case opening step across all $48$ configurations.

from itertools import permutations

def flip_pattern(press, f):
    out = 0
    for i in range(3):
        if press[i] == f[i]:
            out |= 1 << i
    return out

seq = ['ABC','ABC','BCA','CAB','ABC','BCA','ABC',
       'ACB','BAC','ACB','CBA','BAC','ACB']

worst = 0
for f in permutations('ABC'):
    flips = [flip_pattern(p, f) for p in seq]
    for s0 in range(1, 8):
        s = s0
        opened_at = None
        for k, fl in enumerate(flips, 1):
            s ^= fl
            if s == 0:
                opened_at = k
                break
        assert opened_at is not None
        worst = max(worst, opened_at)

print("All 48 hidden configurations open within", worst, "presses")

The script confirms every hidden configuration opens within $13$ presses; the lower bound $13$ is the official exhaustive-search result of Igor Kopylov (FiveThirtyEight, 2017).