Problem 678

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)=$ '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 $\left.F_{0}=0, F_{1}=1, F_{n+2}=F_{n+1}+F_{n}\right)$, 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$.