Paper 4, Section II, 7E7 \mathrm{E}

Numbers and Sets | Part IA, 2016

State the inclusion-exclusion principle.

Let A=(a1,a2,…,an)A=\left(a_{1}, a_{2}, \ldots, a_{n}\right) be a string of nn digits, where ai∈{0,1,…,9}a_{i} \in\{0,1, \ldots, 9\}. We say that the string AA has a run of length kk if there is some j⩽n−k+1j \leqslant n-k+1 such that either aj+i≡aj+i( mod 10)a_{j+i} \equiv a_{j}+i(\bmod 10) for all 0⩽i<k0 \leqslant i<k or aj+i≡aj−i( mod 10)a_{j+i} \equiv a_{j}-i(\bmod 10) for all 0⩽i<k0 \leqslant i<k. For example, the strings

(0,1,2‾,8,4,9),(3,9,8,7‾,4,8) and (3,1,0,9‾,4,5)(\underline{0,1,2}, 8,4,9),(3, \underline{9,8,7}, 4,8) \text { and }(3, \underline{1,0,9}, 4,5)

all have runs of length 3 (underlined), but no run in (3,1,2,1,1,2)(3,1,2,1,1,2) has length >2>2. How many strings of length 6 have a run of length ⩾3\geqslant 3 ?

Typos? Please submit corrections to this page on GitHub.