2008 Mock ARML 1 Problems/Problem 2
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,
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 |