, 2014

Solution:
Answer: $144$

For a natural number $n$, let $A_{n}$ be a set containing all sequences which satisfy the problem conditions but with $12$ replaced by $n$. Also, let $a_{n}$ be the size of $A_{n}$.

We first consider $a_{1}$ and $a_{2}$. We get $a_{1}=1$, as the only sequence satisfying the problem conditions is $0,1$. We also get $a_{2}=1$, as the only possible sequence is $0,1,2$.

Next, we show that $a_{n+2}=a_{n+1}+a_{n}$ for all natural numbers $n$. We consider the second-to-last terms of each sequence in $A_{n+2}$.

Case 1. The second-to-last term is $n+1$. When we leave out the last term, the remaining sequence will still satisfy the problem conditions, and hence is in $A_{n+1}$. Conversely, for a sequence in $A_{n+1}$, we could add $n+2$ at the end of that sequence, and since $n+1$ and $n+2$ have different parities, the resulting sequence will be in $A_{n+2}$. Therefore, there is a one-to-one correspondence between the sequences in this case and the sequences in $A_{n+1}$. So the number of sequences in this case is $a_{n+1}$.

Case 2. The second-to-last term is less than or equal to $n$. But $n$ and $n+2$ have the same parity, so the second-to-last term cannot exceed $n-1$. When we substitute the last term $(n+2)$ with $n$, the resulting sequence will satisfy the problem conditions and will be in $A_{n}$. Conversely, for a sequence in $A_{n}$, we could substitute its last term $n$ with $n+2$. As $n$ and $n+2$ have the same parity, the resulting sequence will be in $A_{n+2}$. Hence, in this case, the number of sequences is $a_{n}$.

Now, since $a_{n+2}=a_{n+1}+a_{n}$ for all natural numbers $n$, we can recursively compute that the number of all possible sequences having their last terms as $12$ is $a_{12}=144$. Note that the resulting sequence $(a_{n})$ is none other than the Fibonacci numbers.