Mock AIME I 2015 Problems/Problem 6


Find the number of $5$ digit numbers using only the digits $1,2,3,4,5,6,7,8$ such that every pair of adjacent digits is no more than $1$ apart. For instance, $12345$ and $33234$ are acceptable numbers, while $13333$ and $56789$ are not.


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.