What If Robots Cut Your Pizza?

At RoboPizza, each cut is made by a robot that picks two points uniformly at random on the pizza’s circular edge and slices along the chord between them. If you ask for exactly three random cuts, how many pieces should you expect? Extra credit: what about $k$ cuts?

The Riddler, FiveThirtyEight (Zach Wissner-Gross)(original post)

Solution

Three random chords give, on average, $$\boxed{5 \text{ pieces}}.$$

The one idea is how a new cut creates pieces. Drop a chord across a region already carved by others: it adds one piece for the slice itself, plus one more each time it crosses an existing chord, since every crossing splits the new chord into a segment that divides one further piece. So the count is $$\text{pieces}=1+(\text{cuts})+(\text{interior crossings}),$$ and all that remains is the expected number of crossings.

Two random chords cross exactly when their four endpoints alternate around the circle. Four points in random order around the circle fall into three equally likely pairings into two chords, and only one of the three interleaves, so any two chords cross with probability $\tfrac13$. With three cuts there are $\binom32=3$ pairs of chords, so the expected number of crossings is $3\cdot\tfrac13=1$, and $$\mathbb{E}[\text{pieces}]=1+3+1=5.$$

Extra credit. For $k$ cuts the slice contributes $1+k$, and the $\binom{k}{2}$ pairs each cross with probability $\tfrac13$, so $$\mathbb{E}[\text{pieces}]=1+k+\frac13\binom{k}{2} =\frac{(k+2)(k+3)}{6}.$$ At $k=3$ this is $\tfrac{5\cdot6}{6}=5$, and it grows quadratically as the robot gets carried away.

The computation

Encode the rule directly: each chord adds one piece, and a pair of chords adds another whenever their endpoints interleave around the circle. Average over many random pizzas.

import numpy as np
rng = np.random.default_rng(0)

def expected_pieces(k, trials=2_000_000):
    ends = np.sort(rng.uniform(0, 2 * np.pi, (trials, k, 2)), axis=2)
    count = np.ones(trials) + k                  # one piece per slice, plus the start
    for i in range(k):
        for j in range(i + 1, k):
            a0, a1 = ends[:, i, 0], ends[:, i, 1]
            b0, b1 = ends[:, j, 0], ends[:, j, 1]
            interleave = ((a0 < b0) & (b0 < a1) & (a1 < b1)) | \
                         ((b0 < a0) & (a0 < b1) & (b1 < a1))
            count += interleave                  # crossing chords add a piece
    return count.mean()

print(round(expected_pieces(3), 4))              # 5.0