Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(solution)
 
m (→‎Solution)
 
Line 15: Line 15:
 
Setting up a table,
 
Setting up a table,
 
<cmath>
 
<cmath>
−
\begin{tabular}{|r||r|r|r|}
+
\begin{array}{|r||r|r|r|}
 
\hline
 
\hline
 
n & a_n & b_n & c_n \\
 
n & a_n & b_n & c_n \\
Line 28: Line 28:
 
8 & 353 & 283 & 157 \\
 
8 & 353 & 283 & 157 \\
 
\hline
 
\hline
−
\end{tabular}
+
\end{array}
 
</cmath>
 
</cmath>
 
The answer is <math>353 + 2(283 + 157) = \boxed{1233}</math>.
 
The answer is <math>353 + 2(283 + 157) = \boxed{1233}</math>.

Latest revision as of 18:28, 10 March 2015

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}$.

See also

2008 Mock ARML 1 (Problems, Source)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_Mock_ARML_1_Problems/Problem_2&oldid=68685"