Difference between revisions of "2008 Mock ARML 1 Problems/Problem 2"

Problem

A positive integer $n$ is a yo-yo if the absolute value of the difference between any two consecutive digits of $n$ is at least $7$ . Compute the number of $8$-digit yo-yos.

Solution

Note that all of the digits must be $\in \{0,1,2,7,8,9\}$. Let $a_n$ be the number of yo-yos with $n$ digits and with a leftmost digit of $0$ if $n$ is odd ($0$ being a placeholder) or $9$ if $n$ is even, let $b_n$ those with a leftmost digit of $1$ if $n$ is odd or $8$ if $n$ is even, and let $c_n$ those with a leftmost digit of $2$ if $n$ is odd or $7$ if $n$ is even. By symmetry, the desired answer is $2(a_8 + b_8 + c_8) - a_8$, to exclude the integers with leftmost digit $0$.

Note that a yo-yo of $n$ digits with leftmost digit of $0$ can be formed from a yo-yo of $n-1$ digits with leftmost digits of $7,8,9$; those with a leftmost digit of $1$ can be formed by those ending in $8,9$; and those with a leftmost digit of $2$ can be formed only by those ending in $9$. The same holds true for the leftmost digits of $9,8,7$, respectively. Thus, we have the recursions \begin{align*} a_{n+1} &= a_n + b_n + c_n\\ b_{n+1} &= a_n + b_n\\ c_{n+1} &= a_n \end{align*} Setting up a table, $$\begin{array}{|r||r|r|r|} \hline n & a_n & b_n & c_n \\ \hline 1 & 1 & 1 & 1 \\ 2 & 3 & 2 & 1 \\ 3 & 6 & 5 & 3 \\ 4 & 14 & 11 & 6 \\ 5 & 31 & 25 & 14 \\ 6 & 70 & 56 & 31 \\ 7 & 157 & 126 & 70 \\ 8 & 353 & 283 & 157 \\ \hline \end{array}$$ The answer is $353 + 2(283 + 157) = \boxed{1233}$.