2008 Mock ARML 1 Problems/Problem 2
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.
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 .
|2008 Mock ARML 1 (Problems, Source)
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8