Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 4 / 5E (Numbers and Sets)

For finite sets $A_1,\dots ,A_s$, the inclusion-exclusion principle statesTo prove it, consider an element belonging to exactly $d$ of the sets. If $d=0$, it contributes zero to both sides. If $d>0$, its contribution on the right iswhich is its contribution to the union. Summing these contributions proves the formula.

For the keypad, a first digit zero cannot be entered. Define four families of valid codes: $A$ consists of all codes with no zero; $B$ consists of codes beginning with $2$; $C$ consists of $110b$ with $b\in \{1,\dots ,9\}$; and $D$ consists of $a110$ with $a\in \{1,\dots ,9\}$. They cover every valid code. Indeed, if the first digit is not $2$, a zero in the second position is impossible; a zero in the third requires the prefix $11$; a zero in the fourth requires the middle pair $11$. In the third-position case the last digit cannot also be zero. Hence the only remaining zero-containing possibilities are exactly $C$ and $D$.

Their cardinalities areThe only nonempty pairwise intersections are $A\cap B$, with $9^3=729$ codes, and $B\cap D=\{2110\}$, with one code. All triple and fourfold intersections are empty. Applying inclusion-exclusion therefore givesThe restriction concerns actual preceding keypresses. It cannot license two successive zeros unless the first-key condition is already satisfied.