State the inclusion-exclusion principle.
Let A=(a1,a2,…,an) be a string of n digits, where ai∈{0,1,…,9}. We say that the string A has a run of length k if there is some j⩽n−k+1 such that either aj+i≡aj+i(mod10) for all 0⩽i<k or aj+i≡aj−i(mod10) for all 0⩽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)
all have runs of length 3 (underlined), but no run in (3,1,2,1,1,2) has length >2. How many strings of length 6 have a run of length ⩾3 ?