Past exam of the mathematics course of the University of Cambridge / 2016 / ia / Paper 4 / 7E / Solution

For finite sets $E_1,\dots ,E_s$, the inclusion-exclusion principle statesIt counts each element once: an element in exactly $q$ of the sets contributes ${\sum }_{j=1}^q(-1{)}^{j+1}(\genfrac{}{}{0ex}{}{q}{j})=1$, by the binomial theorem.

For the cyclic digit run problem, let $E_j$ mean that the three digits starting at position $j$ form a run, for $j=1,2,3,4$. Every run of length at least three contains one of these triples, so we need $|E_1\cup E_2\cup E_3\cup E_4|$. Introduce the five differencesA starting digit and these five residues determine a unique string, including runs that cross $9$ and $0$. In these coordinates $E_j$ requires $(d_j,d_{j+1})=(1,1)$ or $(-1,-1)$.

Each single event fixes two differences, with two choices of sign; the initial digit and the other three differences are free. Thus $|E_j|=10\cdot 2\cdot 10^3=20000$. For intersections of two events, adjacent starting positions force three consecutive differences to have the same sign, giving $10\cdot 2\cdot 10^2=2000$. There are three such pairs. The other three pairs have disjoint constrained difference positions, with independent signs and one free difference, giving $10\cdot 4\cdot 10=400$ each. Consequently the sum of pair-intersection sizes is $3\cdot 2000+3\cdot 400=7200$.

For triple intersections, $E_1\cap E_2\cap E_3$ and $E_2\cap E_3\cap E_4$ each force four consecutive differences to have the same sign, leaving one free difference, and each has size $10\cdot 2\cdot 10=200$. The other two triples, $E_1\cap E_2\cap E_4$ and $E_1\cap E_3\cap E_4$, divide the five differences into two blocks with independent signs; each has size $10\cdot 4=40$. The triple-intersection sum is therefore $480$. Finally, all four events force all five differences to have the same sign, giving $20$ strings.

The inclusion-exclusion principle now gives the number of stringsUsing differences makes the overlap conditions explicit and prevents double-counting long cyclic digit runs.