Work A Shift In The Riddler Gift Shop

Riddler Express

A bottle starts with $100$ whole vitamin tablets. Each morning you pull one item out at random: a whole tablet you cut in half, take one half, and return the other; a half-tablet you simply take. How many days, on average, until you first pull out a half-tablet? Extra credit: what if half-tablets are less likely to be drawn (being smaller)?

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

Solution

Every whole tablet you draw turns into one returned half, so the bottle always holds exactly $100$ pieces until the first half is pulled. On the day after you have drawn $m$ wholes, the bottle holds $m$ halves among those $100$ pieces, so the chance of pulling a half that day is $m/100$. You reach day $m + 1$ only by having drawn a whole on each earlier day, which happens with probability $\prod_{k=0}^{m-1}\big(1 - \tfrac{k}{100}\big)$. Summing the survival probabilities gives the expected number of days, $$\mathbb{E}[\text{days}] = \sum_{m=0}^{100}\ \prod_{k=0}^{m-1}\frac{100 - k}{100} = \sum_{m=0}^{100}\frac{100!}{(100-m)!\,100^{m}} \approx \boxed{13.2}.$$ This is a Ramanujan-style sum, close to $\sqrt{50\pi} \approx 12.5$ plus a small correction. If halves were less likely to be drawn (being smaller), each would linger longer in the bottle, so it would take even longer to pull the first one.

The computation

Sum the survival probabilities exactly, the product form of each term built up factor by factor.

from fractions import Fraction as F
n = 100
expected, term = F(0), F(1)
for m in range(n + 1):
    expected += term
    term *= F(n - m, n)
print(float(expected))                         # 13.21

Riddler Classic

In the Riddler gift shop, we want to package four unit spheres in a regular tetrahedron. What is the smallest tetrahedron that holds all four spheres?

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

Solution

By symmetry, the optimal packing places each sphere snugly in one corner of the tetrahedron, with each sphere touching the three faces meeting at its corner. As we shrink the tetrahedron, all four spheres slide inward along their corner axes until they touch each other; the smallest tetrahedron is the one for which neighbouring spheres just touch.

Where does a corner sphere sit? A sphere of radius $1$ tangent to the three faces meeting at vertex $A$ sits on the line $\ell_A$ from $A$ to the centroid of the opposite face (the axis of three-fold symmetry of those three faces). Let $\alpha$ be the angle between $\ell_A$ and any one of those three adjacent faces. The sphere’s center $S$ lies on $\ell_A$ at the distance $d$ from $A$ for which the perpendicular distance from $S$ to each adjacent face is $1$, so $$d \sin\alpha = 1, \qquad d = \frac{1}{\sin\alpha}.$$

Computing $\sin\alpha$. The angle $\alpha$ is the angle between the axis $\ell_A$ and any adjacent face. Place the regular tetrahedron with vertices $$\begin{aligned} A &= (1, 1, 1), & B &= (1, -1, -1), \\ C &= (-1, 1, -1), & D &= (-1, -1, 1). \end{aligned}$$ The side length is $\lvert AB \rvert = 2\sqrt{2}$, the centroid is at the origin, and the axis $\ell_A$ points from $A$ in direction $-A/\lvert A \rvert = -(1,1,1)/\sqrt{3}$. The outward unit normal of face $BCD$ is $-A/\sqrt{3}$ as well (by symmetry, since the centroid is at the origin), and the outward unit normal of one of the three faces adjacent to $A$, say $ABC$, points roughly opposite to $D$, specifically $-D/\sqrt{3} = (1,1,-1)/\sqrt{3}$. The cosine of the angle between $\ell_A$ and this normal is $$\cos(\pi/2 - \alpha) = \sin\alpha = \Big|\,\frac{-A}{\sqrt{3}} \cdot \frac{-D}{\sqrt{3}}\,\Big| = \frac{|A \cdot D|}{3} = \frac{|1 - 1 + 1|}{3} = \frac{1}{3}.$$ So $\sin\alpha = 1/3$, and a unit sphere tucked in a corner of this scaled tetrahedron has its center at distance $d = 3$ from the vertex along the axis.

Edge length. In the tetrahedron of side $a$, the axis-distance scales by $a / (2\sqrt{2})$, so the corner sphere sits at distance $$d(a) = 3 \cdot \frac{a}{2\sqrt{2}} = \frac{3a}{2\sqrt{2}}$$ from the vertex. But we need $d \sin\alpha = 1$ for the sphere to have radius $1$, where now $\sin\alpha$ is the same $1/3$ in any regular tetrahedron (the angle is scale-invariant). So in fact for a unit sphere we need $$d = 3,$$ measured in the sphere’s own scale. Place coordinates so that each vertex sits at distance $D_v = a\sqrt{3}/(2\sqrt{2})$ from the centroid (the centroid-to-vertex distance for a tetrahedron of side $a$). A corner sphere’s center lies on the vertex axis at distance $d = 3$ from the vertex, so at distance $D_v - 3$ from the centroid along the same axis.

The four sphere centers thus form a smaller regular tetrahedron, similar to the original and centered at the same point, with centroid-to-vertex distance $D_v - 3$. Its side length $s$ satisfies $s / a = (D_v - 3) / D_v$, that is, $$s = a \cdot \frac{D_v - 3}{D_v} = a - \frac{3a}{D_v} = a - 3 \cdot \frac{2\sqrt{2}}{\sqrt{3}} = a - 2\sqrt{6}.$$ For the spheres to just touch, the sphere centers must be exactly $2$ apart, that is $s = 2$. Setting $a - 2\sqrt{6} = 2$ gives $$a = 2 + 2\sqrt{6} \approx 6.899.$$

$$\boxed{\,a = 2 + 2\sqrt{6}.\,}$$

The tetrahedron has side roughly $6.9$ times the radius of one of the four spheres, volume $a^3/(6\sqrt{2}) \approx 38.7$, against a total sphere volume of $4 \cdot \tfrac{4}{3}\pi \approx 16.8$. The packing density is about $43\%$, which is poor as packings go: tetrahedra are not friendly containers for spheres.

The computation

Place a regular tetrahedron of side $a = 2 + 2\sqrt{6}$ in coordinates, compute the corner-sphere centers explicitly, verify each sphere has perpendicular distance $1$ to each of the three faces meeting at its corner, and confirm that all six pairs of sphere centers are exactly $2$ apart.

1. Set $a = 2 + 2\sqrt{6}$, vertices $A,B,C,D$ scaled accordingly.

2. For each vertex, walk along the axis toward the centroid until the perpendicular distance to an adjacent face is $1$.

3. Check perpendicular distance to all three adjacent faces is $1$ at that point.

4. Check every pair of sphere centers is at distance $2$.

import numpy as np
a = 2 + 2 * np.sqrt(6)
scale = a / (2 * np.sqrt(2))
v = scale * np.array([
    [1, 1, 1], [1, -1, -1], [-1, 1, -1], [-1, -1, 1],
], dtype=float)
centroid = v.mean(axis=0)

def out_normal(p, q, r, inside):
    n = np.cross(q - p, r - p); n /= np.linalg.norm(n)
    if np.dot(n, (p + q + r) / 3 - inside) < 0:
        n = -n
    return n

faces = [(0,1,2),(0,1,3),(0,2,3),(1,2,3)]
def corner_sphere(i):
    axis = centroid - v[i]; axis /= np.linalg.norm(axis)
    adj = [f for f in faces if i in f][0]
    n = out_normal(v[adj[0]], v[adj[1]], v[adj[2]], centroid)
    d = -1 / np.dot(axis, n)  # perp dist to face = 1
    return v[i] + d * axis

centers = [corner_sphere(i) for i in range(4)]
# distances between centers
for i in range(4):
    for j in range(i + 1, 4):
        print(f"|S{i}S{j}| =", round(np.linalg.norm(centers[i] - centers[j]), 6))
# all should print 2.0

All six pairs of sphere centers come out at distance exactly $2$, confirming the spheres are mutually tangent at the boxed edge length.