The Carpenter’s Circular Table

The Riddler for September 23, 2016. The Express is a one-line counting argument; the Classic is a packing problem with a tidy pair of trigonometric conditions.

Riddler Express

Suppose the NCAA College Football Playoff, a single-elimination tournament, expanded to include not just four but all 128 Division I teams. How many individual games would be played in that playoff?

The Riddler, FiveThirtyEight, September 23, 2016(original post)

Solution

You can add up the rounds, $64+32+16+8+4+2+1$, but there is a cleaner way to see it that needs no arithmetic at all. Single elimination means every game knocks exactly one team out, and the tournament ends with exactly one team never knocked out. So the number of games equals the number of teams eliminated, which is everyone but the champion: $$128 - 1 = \boxed{127}.$$ The same argument gives $n-1$ games for any $n$-team single-elimination bracket, no matter how the byes fall.

The computation

Simulate the bracket and count the games, for $128$ and for a few other sizes, to confirm the $n-1$ rule.

import random
def games_played(n):
    teams = list(range(n)); count = 0
    while len(teams) > 1:
        random.shuffle(teams)
        winners = []
        # pair them up; an odd one out gets a bye to the next round
        for i in range(0, len(teams) - 1, 2):
            winners.append(teams[i] if random.random() < .5 else teams[i+1])
            count += 1
        if len(teams) % 2: winners.append(teams[-1])
        teams = winners
    return count
for n in (128, 4, 100, 17):
    print(f"n={n:4d}: games={games_played(n)} (n-1={n-1})")
# n= 128: games=127 (n-1=127)
# n=   4: games=3 (n-1=3)
# n= 100: games=99 (n-1=99)
# n=  17: games=16 (n-1=16)

Riddler Classic

You want to build a circular dining table that can be split in half so leaves can be added. Trouble is, your one pristine piece of exotic wood is a $4$-by-$8$-foot rectangle. The plan: cut two congruent semicircles from it and reassemble them into the circular top. What is the radius of the largest possible circular table you can make?

Extra credit: what is the largest circular table you can make from $N$ congruent pieces?

The Riddler, FiveThirtyEight, September 23, 2016(original post)

Solution

Two semicircles of radius $r$ reassemble into a full circle of radius $r$, so the table is as big as the largest semicircle, a half-disk, that we can cut twice from the board without the two pieces overlapping. The naive ways are poor: lay each half-disk flat with its straight edge along an edge of the board and the radius is capped at $r=2$ feet, because the diameter $2r$ must fit the $4$-foot width. The trick is to tilt the two half-disks and let them interlock.

Set the board as $0 \le x \le 8$, $0 \le y \le 4$. Tilt each half-disk’s straight edge (its diameter) by an angle $\alpha$ from the long side, and place the two as $180^\circ$ rotations of each other about the board’s centre $(4,2)$: the lower one pushed into the bottom-left, the upper one into the top-right. Two conditions pin down $\alpha$ and $r$.

The height fixes $r$ in terms of $\alpha$. Take the lower half-disk with centre $C$, diameter along the unit vector $(\cos\alpha, \sin\alpha)$, and the arc bulging to the side of the inward normal $(-\sin\alpha, \cos\alpha)$. A point of the half-disk is $C + a(\cos\alpha,\sin\alpha) + b(-\sin\alpha,\cos\alpha)$ with $a^2+b^2 \le r^2$ and $b \ge 0$. Its height above $C$ ranges from a lowest point at $-r\sin\alpha$ (slide to the far end of the diameter, $a=-r$, $b=0$) up to a highest point at $+r$ (push out along the normal to the arc). So the half-disk spans a vertical distance $r(1+\sin\alpha)$. To use the full board height it touches top and bottom, giving $$r(1+\sin\alpha) = 4 .$$

Tangency fixes $\alpha$. Slide the lower half-disk left until its diameter’s far end meets the left wall, and by symmetry the upper one meets the right wall; this puts the lower centre at $C=(r,\, r\sin\alpha)$. The two pieces are largest when they just touch, and by the point symmetry they touch exactly at the board’s centre $(4,2)$, which must therefore lie on the lower half-disk’s straight edge, the line through $C$ along $(\cos\alpha,\sin\alpha)$. Collinearity of $(4,2)-C$ with that direction reads $$(4-r)\sin\alpha = (2 - r\sin\alpha)\cos\alpha ,$$ and substituting $r = 4/(1+\sin\alpha)$ and simplifying collapses it to the clean relation $$\cot\alpha = 2\sin\alpha + \cos\alpha .$$ This has a single root $\alpha \approx 0.498945$ in $(0, \tfrac\pi2)$, and then $$\boxed{\,r = \frac{4}{1+\sin\alpha} \approx 2.70545 \text{ feet}\,}.$$ The tilt buys a table more than a third again as wide as the flat-cut $r=2$, a little under $5.5$ feet across, out of a board only $4$ feet wide.

Extra Credit

What is the largest circular table from $N$ congruent pieces?

Solution

There is no known general answer; the puzzle’s own author called it “ridiculously hard, if not impossible,” and neither he nor his readers produced a formula. What we can pin down is the ceiling. The $N$ pieces are cut from the board, so the finished disk’s area cannot exceed the board’s: $$\pi r^2 \le 32 \quad\Longrightarrow\quad r \le \sqrt{\tfrac{32}{\pi}} \approx 3.192 \text{ feet}.$$ The two-piece table already reaches $\pi r^2 \approx 23.0$ square feet, about $72\%$ of the wood, so finer cuts have room to climb toward that $3.192$-foot bound. More pieces never hurt, since any $N$-piece cut is also achievable with $N+1$ by leaving one cut unused, so the best radius rises with $N$ toward the area limit. Pinning the exact optimum for each $N$ is the open part.

The computation

Encode the actual geometric constraint rather than the boxed formula: place the two tilted half-disks as derived, with $\alpha$ fixed by the height relation $r(1+\sin\alpha)=4$, and measure by Monte Carlo whether they overlap inside the $8\times4$ board. The largest $r$ with zero overlap is the table radius; beyond it the pieces collide.

import numpy as np, math
def overlap_area(r, n=4_000_000, seed=0):
    a = math.asin(4.0/r - 1.0)                 # height relation fixes alpha
    sa, ca = math.sin(a), math.cos(a)
    C  = np.array([r, r*sa]);     nrm  = np.array([-sa,  ca])   # lower half-disk
    Cp = np.array([8-r, 4-r*sa]); nrmp = np.array([ sa, -ca])   # upper half-disk
    P = np.random.default_rng(seed).uniform([0,0],[8,4], size=(n,2))
    inL = (((P-C )**2).sum(1) <= r*r) & (((P-C )*nrm ).sum(1) >= 0)
    inU = (((P-Cp)**2).sum(1) <= r*r) & (((P-Cp)*nrmp).sum(1) >= 0)
    return (inL & inU).mean() * 32.0           # overlapping area in sq ft

for r in (2.66, 2.70545, 2.71, 2.74):
    print(f"r={r:.5f}: overlap = {overlap_area(r):.4f} sq ft")
lo, hi = 2.60, 2.80                            # bisect the zero-overlap boundary
for _ in range(34):
    mid = (lo+hi)/2
    if overlap_area(mid, n=2_000_000) > 2e-3: hi = mid
    else: lo = mid
print("largest non-overlapping r:", round((lo+hi)/2, 4))
print("area ceiling sqrt(32/pi) :", round(math.sqrt(32/math.pi), 3))
# r=2.66000: overlap = 0.0000 sq ft
# r=2.70545: overlap = 0.0000 sq ft
# r=2.71000: overlap = 0.0505 sq ft
# r=2.74000: overlap = 0.3975 sq ft
# largest non-overlapping r: 2.7056
# area ceiling sqrt(32/pi) : 3.192