Difference between revisions of "2008 Mock ARML 1 Problems/Problem 2"
(solution) |
(No difference)
|
Revision as of 17: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 |