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