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{tabular}{|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{tabular}\] (Error compiling LaTeX. Unknown error_msg)

The answer is $353 + 2(283 + 157) = \boxed{1233}$ .

2008 Mock ARML 1 (Problems, Source)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8

Page

Toolbox

Search

2008 Mock ARML 1 Problems/Problem 2

Problem

Solution

See also