HMMT February, 2015

Solution:

Answer: $39601$

It is clear that $f$ is determined by $f(0), \ldots, f(21)$. The colors of the 11 even integers are independent of those of the odd integers because evens and odds are never exactly 2 apart.

First, we count the number of ways to "color" the even integers. $f(0)$ can either be 'green' or 'blue'. If $f(0)$ is 'green', then $f(2)=f(20)=\text{'blue'}$. A valid coloring of the 8 other even integers corresponds bijectively to a string of 8 bits such that no two consecutive bits are 1. In general, the number of such length $n$ strings is well known to be $F_{n+2}$ (indexed according to $F_{0}=0, F_{1}=1, F_{n+2}=F_{n+1}+F_{n}$), which can be proven by recursion. Therefore, the number of colorings of even integers in this case is $F_{10}=55$.

If $f(0)$ is 'blue', then a valid coloring of the 10 other even integers corresponds bijectively to a string as above, of 10 bits. The number of colorings for this case is $F_{12}=144$. The total number of colorings of even integers is $55+144=199$.

Using the same reasoning for coloring the odd integers, we see that the number of colorings of all of the integers is $199^{2}=39601$.