Can You Plug The White House Leak?

Riddler Express

You are the president, and exactly one of your $100$ staffers is a leaker. You can fabricate distinct stories and give each staffer a different subset; any staffer with a story will leak it. What is the smallest number of distinct stories you need to identify the leaker for sure?

The Riddler, FiveThirtyEight, August 11, 2017(original post)

Solution

Encode the identity of the leaker as a binary string: each story is one bit, with the bit equal to $1$ if the leaker was given that story and $0$ otherwise. The president picks a labelling of the $100$ staffers by distinct binary strings, then assigns each story to the subset of staffers whose bit-string has a $1$ in that position. After watching which stories leak, the president reads off the bit-string and recovers the leaker.

The number of distinguishable bit-strings on $k$ stories is $2^k$, so we need $2^k \ge 100$, that is $$k \ge \log_2 100 = 6.6438\ldots$$ The smallest integer satisfying this is $k = 7$, giving $2^7 = 128 \ge 100$ distinguishable codes.

The classical phrasing of this construction is a sequential binary search: split the staff in half, give one story to the first $50$, see whether it leaks, then split the surviving $50$ in half, and so on. Worst-case the suspect set shrinks $100 \to 50 \to 25 \to 13 \to 7 \to 4 \to 2 \to 1$, which is again seven steps; the cleanest description is the simultaneous one above (no waiting between stories), but both reach the same $7$.

The lower bound is information-theoretic: each story is a yes/no observation, so $k$ stories produce only $2^k$ possible outcome vectors. To distinguish $100$ candidate leakers the president must have $2^k \ge 100$, that is $k \ge 7$. Seven is therefore both achievable and necessary.

$$\boxed{\,k = 7 \text{ stories.}\,}$$

The computation

Encode the problem as a binary-labelling enumeration: for any number of stories $k$, the president identifies the leaker if and only if the labelling assigns distinct binary strings to the $100$ staffers. The smallest $k$ for which this is possible is the answer.

import math
N = 100
k = math.ceil(math.log2(N))
print(f"stories needed for {N} staffers = {k}")  # 7
# explicit binary labelling: staffer i gets the binary string of i,
# story j is given to all staffers whose j-th bit is 1.
labels = [format(i, f"0{k}b") for i in range(N)]
print(len(set(labels)) == N)                     # True (all distinct)
# minimal k is forced: 2**(k-1) < N
print(2 ** (k - 1) < N <= 2 ** k)                # True

The labelling assigns $100$ distinct binary strings, and $2^{k-1} = 64 < 100 \le 128 = 2^k$ confirms $k = 7$ is the smallest feasible value.

Riddler Classic

Five regular tetrahedral dice are placed around a common edge, each sharing a triangular face with its neighbours. They almost close up into a closed pentagonal ring, but a small angular gap remains. What is the size of that gap?

The Riddler, FiveThirtyEight, August 11, 2017(original post)

Solution

The gap is $360^\circ$ minus five copies of the regular tetrahedron’s dihedral angle.

The dihedral angle of a regular tetrahedron (the angle between any two of its faces meeting along an edge) is $$\gamma = \arccos\!\Big(\tfrac{1}{3}\Big) \approx 70.5288^\circ.$$ Take a tetrahedron with side $1$ and look at it across one of its edges. The two adjacent faces meet at that edge; their inward-pointing perpendiculars from the edge to the opposite vertices have length equal to the height of an equilateral triangle of side $1$, that is $h = \sqrt{3}/2$. The vertex-to-vertex distance across the dihedral is the edge length of the opposite edge, which is also $1$. Apply the law of cosines to the isoceles triangle with two sides $h$ and apex angle $\gamma$: $$1^2 = h^2 + h^2 - 2 h^2 \cos\gamma = 2 h^2 (1 - \cos\gamma),$$ giving $$\cos\gamma = 1 - \frac{1}{2 h^2} = 1 - \frac{1}{2 \cdot 3/4} = \frac{1}{3}.$$ Now stack five tetrahedra around a common edge. Each contributes a dihedral angle $\gamma$ to the total angle swept around that edge, and the gap is whatever is left of $360^\circ$: $$\alpha = 360^\circ - 5\gamma = 360^\circ - 5 \arccos\!\Big(\tfrac{1}{3}\Big).$$ Numerically, $$\alpha \approx 360^\circ - 5 \cdot 70.5288^\circ = 360^\circ - 352.6439^\circ = 7.3561^\circ.$$

$$\boxed{\,\alpha = 360^\circ - 5\arccos(1/3) \approx 7.356^\circ.\,}$$

The five tetrahedra cannot close into a ring: the dihedral $\arccos(1/3)$ is irrational in degrees and not a divisor of $360^\circ$, so no finite number of identical regular tetrahedra can perfectly tile a ring around a common edge. The gap is intrinsic to the geometry, not a measurement error.

The computation

Encode the problem with explicit unit vectors for the two faces meeting at the shared edge of a single regular tetrahedron, compute the dihedral angle from their normals, and multiply by five. As a separate check, build the five tetrahedra explicitly in $3$D and measure the wedge angle that remains.

1. Place one regular tetrahedron with vertices at known coordinates; pick an edge and identify the two adjacent faces.

2. Compute the outward normals of those two faces; the dihedral is the angle between the inward normals.

3. Multiply by $5$ and subtract from $360^\circ$.

import numpy as np
v = np.array([
    [1, 1, 1],
    [1, -1, -1],
    [-1, 1, -1],
    [-1, -1, 1],
], dtype=float)
centroid = v.mean(axis=0)
def outward_normal(a, b, c, inside):
    n = np.cross(b - a, c - a)
    n /= np.linalg.norm(n)
    if np.dot(n, (a + b + c) / 3 - inside) < 0:
        n = -n
    return n
# edge: v[0]-v[1]. Faces sharing it: (0,1,2) and (0,1,3).
n1 = outward_normal(v[0], v[1], v[2], centroid)
n2 = outward_normal(v[0], v[1], v[3], centroid)
# dihedral = pi minus angle between outward normals
gamma = np.pi - np.arccos(np.dot(n1, n2))
print(round(np.degrees(gamma), 4))               # 70.5288
gap = 360 - 5 * np.degrees(gamma)
print(round(gap, 4))                             # 7.3561

The dihedral angle prints as $70.5288^\circ$ (matching $\arccos(1/3)$), and the gap prints as $7.3561^\circ$, in agreement with the boxed value.