Crescents, Footballs, and the Squishyball Series

The Riddler for July 14, 2017. The Express is a simple lens-area question: two identical pizzas overlap with each crust passing through the other’s centre, and you must choose between one crescent and two footballs. The Classic is the National Squishyball League’s perverse postseason format: the winner’s prize shrinks with the series length, and you have to set the length to maximise your expected winnings.

Riddler Express

You and two siblings share two extra-large pizzas of the same size. The pizzas are placed so that the crust of one touches the centre of the other, and vice versa. You slice both pizzas around their region of overlap. Two pieces are the outer “crescents” (one per pizza), and the third piece is the union of the two “football”-shaped cutouts (one per pizza), which sit on top of each other in the overlap region. Two siblings each take a crescent; one takes both footballs. To eat the most pizza, do you want one crescent or both footballs?

The Riddler, FiveThirtyEight, July 14, 2017(original post)

Solution

Set the radius of each pizza to $r = 1$ and place the centres at $(0, 0)$ and $(1, 0)$. The two circular crusts intersect where each circle’s equation holds, giving intersection points $(1/2, \pm \sqrt{3}/2)$.

The one lens area. The overlap region (a single “vesica piscis” lens) is symmetric across both the $x$-axis and the line $x = 1/2$. Half of it lies in the unit disc centred at the origin and is bounded by the arc of that disc between $(1/2, \sqrt{3}/2)$ and $(1/2, -\sqrt{3}/2)$ and the chord $x = 1/2$. The arc subtends a central angle $2\pi/3$ at the origin (the angle between the two intersection points seen from $(0,0)$). The circular segment cut off by the chord $x = 1/2$ has area $$\text{(segment)} \;=\; \tfrac{1}{2} r^{2} (\alpha - \sin \alpha) \;=\; \tfrac{1}{2} \bigl(\tfrac{2\pi}{3} - \sin \tfrac{2\pi}{3}\bigr) \;=\; \tfrac{\pi}{3} - \tfrac{\sqrt{3}}{4}.$$ The lens is twice this segment (one segment from each disc), so $$A_{\text{lens}} \;=\; \frac{2\pi}{3} \;-\; \frac{\sqrt{3}}{2} \;\approx\; 1.2284.$$

Football pair versus one crescent. When each pizza is sliced along the boundary of the other, pizza $1$ separates into one crescent (its part outside pizza $2$) and one football (the lens, sitting where pizza $2$ overlaps it). Pizza $2$ does the same. So the third sibling takes both footballs, which together cover the same lens region twice; the total amount of pizza they get is twice the lens area: $$A_{\text{2 footballs}} \;=\; 2 A_{\text{lens}} \;=\; \frac{4\pi}{3} \;-\; \sqrt{3} \;\approx\; 2.4567.$$ One crescent is the area of one pizza ($\pi$) minus its football: $$A_{\text{1 crescent}} \;=\; \pi \;-\; A_{\text{lens}} \;=\; \frac{\pi}{3} \;+\; \frac{\sqrt{3}}{2} \;\approx\; 1.9132.$$

So two footballs beat one crescent comfortably: $$\boxed{\,A_{\text{2 footballs}} \;\approx\; 2.46 \;\;>\;\; A_{\text{1 crescent}} \;\approx\; 1.91.\,}$$ The three shares ($1.913 + 1.913 + 2.457 \approx 6.28 \approx 2\pi$) sum exactly to the two pizzas’ total area, as they must.

A sanity check on intuition. The lens is one-third of each pizza by central-angle weight, so the football area is exactly $\tfrac13 \pi + (\text{the two ``bulge'' triangles outside the cone})$, and the two bulges together push the football past the bare third. The crescent, by complement, is two-thirds of a pizza minus the same two bulges, putting it below two-thirds of a pizza. Two footballs total just over two-thirds of a pizza; one crescent is just under two-thirds.

The computation

Encode the regions as Monte-Carlo membership tests in the bounding box and integrate by counting. Pick uniform points in $[-1, 2] \times [-1, 1]$; for each, test which regions it sits in.

import random, math

def regions(N=2_000_000, seed=0):
    rng = random.Random(seed)
    box_area = 3.0 * 2.0          # [-1,2] x [-1,1]
    in_lens = in_cresc1 = in_cresc2 = 0
    for _ in range(N):
        x = rng.uniform(-1, 2)
        y = rng.uniform(-1, 1)
        in_p1 = x*x + y*y <= 1.0
        in_p2 = (x-1)**2 + y*y <= 1.0
        if in_p1 and in_p2:
            in_lens += 1
        elif in_p1:
            in_cresc1 += 1
        elif in_p2:
            in_cresc2 += 1
    f = box_area / N
    return f*in_lens, f*in_cresc1, f*in_cresc2

lens, c1, c2 = regions()
print(f"one lens (football)   = {lens:.4f}  exact 2pi/3 - sqrt3/2 "
      f"= {2*math.pi/3 - math.sqrt(3)/2:.4f}")
print(f"two footballs         = {2*lens:.4f}  exact 4pi/3 - sqrt3 "
      f"= {4*math.pi/3 - math.sqrt(3):.4f}")
print(f"one crescent (avg)    = {(c1+c2)/2:.4f}  exact pi/3 + sqrt3/2 "
      f"= {math.pi/3 + math.sqrt(3)/2:.4f}")
# one lens (football)   = 1.2280  exact 2pi/3 - sqrt3/2 = 1.2284
# two footballs         = 2.4560  exact 4pi/3 - sqrt3 = 2.4567
# one crescent (avg)    = 1.9136  exact pi/3 + sqrt3/2 = 1.9132

The Monte-Carlo areas match the exact values to four decimal places, confirming both the lens formula and the strict inequality.

Riddler Classic

You own the regular-season champions of the National Squishyball League. The championship is against the second seed. You pick the series length: a single game, best two of three, best three of five, all the way up to best $50$ of $99$. Your team wins each game with probability $0.6$, independently. If you win the title, you receive $$1{,}000{,}000$ minus $$10{,}000$ per win required (so a one-game series pays $$990{,}000$, a best-of-seven series pays $$960{,}000$, and so on). Losing pays zero. What length of series maximises your expected winnings, and how much do you expect?

The Riddler, FiveThirtyEight, July 14, 2017(original post)

Solution

Let the series be best $N$ of $2N - 1$, so you need $N$ wins. Let $p = 0.6$ be your per-game win probability. The probability $P_N$ that you win the series is the probability of at least $N$ heads in $2N - 1$ independent biased coin flips: $$P_N \;=\; \sum_{k = N}^{2N - 1} \binom{2N-1}{k} p^{k} (1 - p)^{2N-1-k}.$$ The prize for winning is $W_N = 1{,}000{,}000 - 10{,}000 N$, paid only on victory. Your expected winnings are $$\mathbb{E}[\text{winnings}](N) \;=\; P_N \cdot W_N.$$ You face two opposing forces. As $N$ grows, $P_N$ rises toward $1$ (with a $60/40$ edge, longer series favour the better team). But $W_N$ falls linearly. Maximising the product is a tradeoff.

Asymptotic intuition. For large $N$, the central limit theorem gives $P_N \to 1$ exponentially fast (the gap between expected wins $(2N-1)p = 1.2N - 0.6$ and the threshold $N$ grows linearly with $N$). The shortfall $1 - P_N$ behaves like $\exp(-c N)$ for some $c > 0$. So for large $N$, $$\mathbb{E}[\text{winnings}] \;\approx\; (1 - e^{-c N}) \cdot (10^6 - 10^4 N).$$ Differentiating in $N$ shows the optimum is at finite $N$: the linear penalty $10^4$ per added win eventually overwhelms the exponentially-shrinking gain in $P_N$.

Exact optimum. Compute $P_N \cdot W_N$ for each $N$ from $1$ to $50$ and pick the maximum. $$\begin{aligned} P_{12} &\approx 0.8364, & W_{12} &= 880{,}000, & P_{12} W_{12} &\approx 735{,}994,\\ P_{13} &\approx 0.8462, & W_{13} &= 870{,}000, & P_{13} W_{13} &\approx 736{,}222,\\ P_{14} &\approx 0.8553, & W_{14} &= 860{,}000, & P_{14} W_{14} &\approx 735{,}599. \end{aligned}$$ The maximum is at $N = 13$: $$\boxed{\,N \;=\; 13 \text{ (best of } 25\text{);} \quad \mathbb{E}[\text{winnings}] \;\approx\; \$736{,}222.\,}$$

The series is much longer than the canonical best-of-seven. The intuition is that the marginal cost of one more required win is only $$10{,}000$, while at this margin the probability gain from going from $12$ to $13$ wins required is about $0.0098$, worth roughly $0.0098 \cdot 870{,}000 \approx \$8{,}500$. Just past $N = 13$, the probability gain stops being worth $$10{,}000$, and that crossover defines the optimum.

The computation

Encode the binomial directly. Sum the probability of $N$-or-more wins in $2N - 1$ trials at $p = 0.6$, multiply by the prize, and tabulate.

from math import comb

def winprob(N, p=0.6):
    return sum(comb(2*N-1, k) * p**k * (1-p)**(2*N-1-k)
               for k in range(N, 2*N))

best_ev, best_N = 0.0, 0
for N in range(1, 51):
    ev = winprob(N) * (1_000_000 - 10_000 * N)
    if ev > best_ev:
        best_ev, best_N = ev, N

print(f"optimal N = {best_N}, series length 2N-1 = {2*best_N-1}")
print(f"expected winnings = ${best_ev:,.2f}")
for N in (11, 12, 13, 14, 15):
    p = winprob(N)
    ev = p * (1_000_000 - 10_000 * N)
    print(f"  N={N:2d}  P_win={p:.4f}  EV=${ev:,.2f}")
# optimal N = 13, series length 2N-1 = 25
# expected winnings = $736,222.04
#   N=11  P_win=0.8256  EV=$734,803.70
#   N=12  P_win=0.8364  EV=$735,993.77
#   N=13  P_win=0.8462  EV=$736,222.04
#   N=14  P_win=0.8553  EV=$735,599.48
#   N=15  P_win=0.8638  EV=$734,218.99

The optimum lands cleanly at $N = 13$ (a best-of-$25$ series) with an expected payday of $$736{,}222.04$. The neighbours $N \in \{12, 14\}$ both fall short by about $$200$-$\$600$, confirming the curvature of the tradeoff.