Mock AIME I 2015 Problems/Problem 6

Problem

Find the number of digit numbers using only the digits such that every pair of adjacent digits is no more than apart. For instance, and are acceptable numbers, while and are not.

Solution

Do casework on the center digit. If it is a 3, 4, 5, or 6, there are 3^4=81 combinations for the rest of the digits, since they can't go "out of bounds." 81*4=324, so these cases give us 324 possibilities. If it is a 1, the last two digits can be (1,1), (1,2), (2,1), (2,2), or (2,3). Reverse each of these pairs to find the possibilities for the digits proceeding the 1, so there are 5^2=25 total valid numbers with 1 as the center digit. By symmetry, this is also the number of valid number for the center digit being 8, so these cases yield 25*2=50 possibilities. If the center digit is a 2, there are 8 pairs of potential last two digits: The same 5 as mentioned above, plus (3,2), (3,3), and (3,4). 8^2=64, and 64*2=128. 324+50+128=502, which is our answer.