Maths Olympiad Prep

Library / HMMT November /642 of 672

HMMT November, 2018

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

At lunch, Abby, Bart, Carl, Dana, and Evan share a pizza divided radially into 1616 slices. Each one takes one slice of pizza uniformly at random, leaving 1111 slices. The remaining slices of pizza form "sectors" broken up by the taken slices, e.g. if they take five consecutive slices then there is one sector, but if none of them take adjacent slices then there will be five sectors. What is the expected number of sectors formed?

Solution

Solution:

Consider the more general case where there are NN slices and M>0M>0 slices are taken. Let SS denote the number of adjacent pairs of slices of pizza which still remain. There are N−MN-M slices and a sector of kk slices contributes k−1k-1 pairs to SS. Hence the number of sectors is N−M−SN-M-S. We compute the expected value of SS by looking at each adjacent pair in the original pizza:

E(S)=N(N−2M)(NM)=N(N−M)(N−M−1)N(N−1)=(N−M)(N−M−1)N−1 \mathbb{E}(S)=N \frac{\binom{N-2}{M}}{\binom{N}{M}}=N \frac{(N-M)(N-M-1)}{N(N-1)}=\frac{(N-M)(N-M-1)}{N-1}

The expected number of sectors is then
N−M−(N−M)(N−M−1)N−1=(N−M)MN−1. N-M-\frac{(N-M)(N-M-1)}{N-1}=\frac{(N-M) M}{N-1} .
For N=16,M=5N=16, M=5 this yields 113\frac{11}{3}.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.