HMMT February

We consider the integers from this process written in binary. The first operation truncates the rightmost digit, while the second operation appends 01 to the right. We cannot have a number with a substring 11. For simplicity, call a string valid if it has no consecutive $1^{\prime} s$. Note that any number generated by this process is valid, as truncating the rightmost digit and appending 01 to the right of the digits clearly preserve validity. Since we can effectively append a zero by applying the second operation and then the first operation, we see that we can achieve all valid strings. Note that 2014 has eleven digits when written in binary, and any valid binary string with eleven digits is at most $10111111111=1535$. Therefore, our problem reduces to finding the number of eleven-digit valid strings. Let $F_{n}$ denote the number of valid strings of length $n$. For any valid string of length $n$, we can create a valid string of length $n+1$ by appending a 0, or we can create a valid string of length $n+2$ by appending 01. This process is clearly reversible, so our recursion is given by $F_{n}=F_{n-1}+F_{n-2}$, with $F_{1}=2, F_{2}=3$. This yields a sequence of Fibonacci numbers starting from 2, and some computation shows that our answer is $F_{11}=233$.