Chapter 190

Can You Slice This In Half?

Riddler Express

In a penalty shootout each team takes $5$ kicks; each kick has an independent $75\%$ chance of scoring. What is the probability the shootout is still tied after $5$ kicks per side, so play goes into sudden death?

The Riddler, FiveThirtyEight, July 13, 2018(original post)

Solution

Each team scores some number of goals out of $5$ , distributed Binomial $(5, 0.75)$ independently of the other team. The shootout is tied after the first five kicks per side exactly when both teams score the same total $k \in \{0, 1, 2, 3, 4, 5\}$ . So $P(\text{tied}) \;=\; \sum_{k=0}^{5} \left[ \binom{5}{k} (0.75)^{k} (0.25)^{5 - k} \right]^{2}.$ The individual single-team probabilities $\binom{5}{k} (0.75)^{k} (0.25)^{5 - k}$ for $k = 0, 1, 2, 3, 4, 5$ are $0.0009766$ , $0.0146484$ , $0.0878906$ , $0.2636719$ , $0.3955078$ , $0.2373047$ . Squaring and summing: $\begin{aligned} P(\text{tied}) &\;\approx\; 9.5 \cdot 10^{-7} + 2.1 \cdot 10^{-4} + 7.7 \cdot 10^{-3} \\ &\quad + 6.9 \cdot 10^{-2} + 1.564 \cdot 10^{-1} + 5.63 \cdot 10^{-2} \\ &\;\approx\; 0.2902. \end{aligned}$ $\boxed{\;P \;\approx\; 0.2902 \;\approx\; 29.0\%.\;}$ A clean way to see why the answer is so high is to notice that each team scores about $3.75$ goals on average, with standard deviation only $\sqrt{5 \cdot 0.75 \cdot 0.25} \approx 0.97$ . The two totals usually land within one goal of one another, and the chance they land equal is on the order of $1/\sqrt{4 \pi \cdot 5 \cdot 0.75 \cdot 0.25} \approx 0.29$ , which is what we got exactly.

The computation

Enumerate the joint distribution of (team A goals, team B goals) under independent Binomial $(5, 0.75)$ and sum the diagonal.

from math import comb

p = 0.75
q = 0.25
single = [comb(5, k) * p**k * q**(5 - k) for k in range(6)]
print("single-team distribution:", [f"{x:.5f}" for x in single])
tied = sum(x * x for x in single)
print(f"P(tied after 5 kicks each) = {tied:.6f}")

The script prints P(tied after 5 kicks each) = 0.290203, agreeing with the boxed value to four decimal places.

Riddler Classic

An “L” shape is formed by two rectangles touching each other (no fixed dimensions, no required equality between them). Using only a straightedge and a pencil, draw a single straight line that cuts the L into two pieces of exactly equal area. You may draw as many construction lines as you like, but the bisector must be a single straight line. The construction must work for any L.

The Riddler, FiveThirtyEight, July 13, 2018(original post)

Solution

The one idea: a line through the centre of a rectangle bisects it. For any rectangle, the centre is a point of $180^{\circ}$ rotational symmetry, so any line through it splits the rectangle into two congruent pieces and hence into halves. The trick is to apply this fact to two rectangles at once.

The construction. Complete the L into a full rectangle $R$ by drawing in the missing two sides; the rectangular notch that was removed to form the L is itself a rectangle $r$ . The L is $R \setminus r$ . Now pick a line $\ell$ that passes through both the centre of $R$ and the centre of $r$ . Such a line exists (any two points determine a line) and is unique unless the centres coincide (in which case any line through that common centre works).

By the centre fact, $\ell$ splits $R$ into two equal halves, and it also splits $r$ into two equal halves. The L is what is left when $r$ is removed from $R$ . On each side of $\ell$ we have removed half of $r$ from half of $R$ , so each side has area $\tfrac{1}{2} |R| - \tfrac{1}{2} |r| = \tfrac{1}{2} (|R| - |r|) = \tfrac{1}{2} |L|$ . The line $\ell$ bisects the L.

How to find the two centres with just a straightedge. Each rectangle has its centre at the intersection of its two diagonals. Draw the two diagonals of $R$ ; the cross is its centre. Same for $r$ . Connect the two centres with a straight line. That line is the bisector. $\boxed{\;\text{Bisector: the straight line through the centres of $R$ and $r$.}\;}$ Two remarks. First, the same construction bisects any shape that is the (signed) sum or difference of two rectangles, not just an L. Second, it generalises to parallelograms (the centre of a parallelogram is again the diagonal intersection) and to three dimensions (centroid of a box, also at the intersection of body diagonals).

The computation

Encode an arbitrary L, find the two centres, build the line through them, and verify by Monte Carlo integration that the two sides have equal area. Brute-force the verification on $50$ random L-shapes.

Sample random widths and heights for the bounding rectangle $R$ and the removed corner rectangle $r$ .
Compute the two centres analytically.
Generate $10^{6}$ uniform random points in $R$ , discard those in $r$ (so what remains is uniform in $L$ ), and count how many lie on each side of the bisector line.
Confirm the count split is $50/50$ to within sampling noise on every test L.

import random

def test_L(W, H, w, h, seed):
    """L is [0,W] x [0,H] minus [W-w, W] x [H-h, H]."""
    R_area = W * H
    r_area = w * h
    L_area = R_area - r_area
    cR = (W / 2, H / 2)
    cr = (W - w / 2, H - h / 2)
    # Line through cR and cr: (y - cR_y)(cr_x - cR_x) = (x - cR_x)(cr_y - cR_y)
    dx = cr[0] - cR[0]
    dy = cr[1] - cR[1]
    def side(x, y):
        return (y - cR[1]) * dx - (x - cR[0]) * dy

    random.seed(seed)
    pos = neg = 0
    N = 10**6
    for _ in range(N):
        x = random.uniform(0, W)
        y = random.uniform(0, H)
        if x >= W - w and y >= H - h:
            continue  # in the removed notch
        s = side(x, y)
        if s > 0: pos += 1
        elif s < 0: neg += 1
    total = pos + neg
    return pos / total, neg / total

random.seed(0)
ok = 0
for trial in range(10):
    W = random.uniform(2, 10)
    H = random.uniform(2, 10)
    w = random.uniform(0.5, W - 0.5)
    h = random.uniform(0.5, H - 0.5)
    p, n = test_L(W, H, w, h, trial)
    print(f"L #{trial}: pos={p:.4f}, neg={n:.4f}")
    if abs(p - 0.5) < 0.002:
        ok += 1
print(f"{ok}/10 within 0.2% of 50/50")

For every random L the script reports a split within sampling noise of $50/50$ , confirming that the line through the two centres bisects the L exactly.