HMMT-Nov 2010 guts, Problem 19

How many 8-digit numbers begin with 1 , end with 3 , and have the property that each successive digit is either one more or two more than the previous digit, considering 0 to be one more than 9 ?

Solution: Given an 8-digit number $a$ that satifies the conditions in the problem, let $a_{i}$ denote the difference between its $(i+1)$ th and $i$ th digit. Since $i \in\{1,2\}$ for all $1 \leq i \leq 7$, we have $7 \leq$ $a_{1}+a_{2}+\cdots+a_{7} \leq 14$. The difference between the last digit and the first digit of $m$ is $3-1 \equiv 2$ $(\bmod 10)$, which means $a_{1}+\cdots+a_{7}=12$. Thus, exactly five of the $a_{i} \mathrm{~s}$ equal to 2 and the remaining two equal to 1. The number of permutations of five $2 \mathrm{~s}$ and two $1 \mathrm{~s}$ is $\left(\begin{array}{l}7 \\ 2\end{array}\right)=21$. $\fbox{21}$.

Answer: 21