imc

Question

Let (a_1, a_2, ... a_10) be a list of the first 10 positive integers such that for each 2 i 10 either a_i + 1 or a_i-1 or both appear somewhere before a_i in the list. How many such lists are there?

Accepted Answer

If we have 1 as the first number, then the only possible list is (1,2,3,4,5,6,7,8,9,10). If we have 2 as the first number, then we have 9 ways to choose where the 1 goes, and the numbers ascend from the first number, 2, with the exception of the 1. For example, (2,3,1,4,5,6,7,8,9,10), or (2,3,4,1,5,6,7,8,9,10). There are 91 ways to do so. If we use 3 as the first number, we need to choose 2 spaces to be 2 and 1, respectively. There are 92 ways to do this. In the same way, the total number of lists is: 90 +91 + 92 + 93 + 94.....99 By the binomial theorem, this is 2^9 = 512, or 512