Can You Get The Paper Cut?

Riddler Express

A crystal is a polyhedron with exactly six edges, at least four of which are $1$ inch long. Among all such crystals, the key is the one of largest volume. What is that volume?

Solution

Six edges force the shape to be a tetrahedron. To make it as large as possible while keeping four unit edges, take three of them as a face: an equilateral triangle of side $1$, area $\tfrac{\sqrt3}{4}$. The fourth unit edge is one of the three edges rising to the apex; the volume is $$V = \frac13 \times (\text{base area}) \times (\text{height}) = \frac13 \cdot \frac{\sqrt3}{4} \cdot h,$$ so we want the height as large as possible. The apex is one unit edge away from a base vertex, and its height above the base is largest, equal to $1$, exactly when that unit edge stands vertical. Then $$V = \frac13 \cdot \frac{\sqrt3}{4} \cdot 1 = \frac{1}{4\sqrt3} = \frac{\sqrt3}{12} \approx \boxed{0.1443}.$$ The two remaining edges (from the apex to the other two base vertices) come out to $\sqrt2$, longer than $1$, so exactly four edges are unit length, as allowed.

The computation

Search all ways to fix four edges at $1$ and leave two free, computing each tetrahedron’s volume from the Cayley–Menger determinant, and maximise.

import numpy as np
from itertools import combinations
from scipy.optimize import minimize
edges = [frozenset(e) for e in combinations(range(4), 2)]   # 6 edges
def vol(d):
    M = np.ones((5, 5)); M[0, 0] = 0
    for i in range(4):
        for j in range(4):
            M[i + 1, j + 1] = 0 if i == j else d[frozenset((i, j))]**2
    return np.sqrt(max(np.linalg.det(M) / 288, 0))
best = 0
for free in combinations(range(6), 2):
    f = lambda p: -vol({**{e: 1.0 for e in edges},
                        edges[free[0]]: p[0], edges[free[1]]: p[1]})
    for x0 in [(1.4, 1.4), (0.8, 1.5)]:
        best = max(best, -minimize(f, x0, bounds=[(.01, 1.99)]*2).fun)
print(best, np.sqrt(3) / 12)                  # 0.14434, 0.14434

Riddler Classic

A child cuts $1$-inch-wide strips from a sheet of paper: she picks one of the four sides at random and trims a strip parallel to it, repeating until the sheet’s shorter side is at most $1$ inch (so the whole thing is a strip). Starting from $8.5 \times 11$ inches, how many cuts does she make on average? Extra credit: starting from $m \times n$?

Solution

Each cut shrinks one of the two dimensions by $1$ inch, and the two sides parallel to a given dimension make it equally likely to trim either way, so every cut is a fair coin: shrink the long side or the short side. The sheet becomes a strip once a dimension first falls to $1$ inch or below. The $11$-inch side reaches that after $10$ cuts ($11 \to 1$); the $8.5$-inch side reaches it after $8$ cuts ($8.5 \to 0.5$). So the process is just fair coin flips, stopping when we accumulate $10$ “long” cuts or $8$ “short” cuts, and we want the expected number of flips.

Writing $C(a, b)$ for the expected cuts still needed when $a$ long-cuts and $b$ short-cuts remain, each flip uses one or the other, $$C(a, b) = 1 + \tfrac12 C(a-1, b) + \tfrac12 C(a, b-1), \qquad C(0, \cdot) = C(\cdot, 0) = 0.$$ Unrolling from $C(10, 8)$ gives the exact value $$\frac{234137}{16384} \approx \boxed{14.29} \text{ cuts}.$$ In general the two targets are $\lceil m \rceil - 1$ and $\lceil n \rceil - 1$ cuts; for a square sheet the race is symmetric and the answer is a touch below the smaller target.

The computation

Solve the recurrence exactly with memoised fractions.

from fractions import Fraction as F
from functools import lru_cache
@lru_cache(None)
def C(a, b):
    if a == 0 or b == 0: return F(0)
    return 1 + (C(a - 1, b) + C(a, b - 1)) / 2
print(C(10, 8), float(C(10, 8)))              # 234137/16384, 14.29