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 jnk+1j \leqslant n-k+1 such that either aj+iaj+i(mod10)a_{j+i} \equiv a_{j}+i(\bmod 10) for all 0i<k0 \leqslant i<k or aj+iaji(mod10)a_{j+i} \equiv a_{j}-i(\bmod 10) for all 0i<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 ?