Difference between revisions of "2008 Mock ARML 1 Problems/Problem 2"
(solution) |
(No difference)
|
Revision as of 16:16, 29 May 2008
Problem
A positive integer 
is a yo-yo if the absolute value of the difference between any two consecutive digits of is at least 
. Compute the number of 
-digit yo-yos.
Solution
Note that all of the digits must be 
. Let 
be the number of yo-yos with digits and with a leftmost digit of 
if is odd ( being a placeholder) or 
if is even, let 
those with a leftmost digit of 
if is odd or if is even, and let 
those with a leftmost digit of 
if is odd or if is even. By symmetry, the desired answer is 
, to exclude the integers with leftmost digit .
Note that a yo-yo of digits with leftmost digit of can be formed from a yo-yo of 
digits with leftmost digits of 
; those with a leftmost digit of can be formed by those ending in 
; and those with a leftmost digit of can be formed only by those ending in . The same holds true for the leftmost digits of 
, respectively. Thus, we have the recursions
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 
.
See also
| 2008 Mock ARML 1 (Problems, Source) | ||
| Preceded by Problem 1 |
Followed by Problem 3 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | ||
