HMMT 二月 2015 · COMB 赛 · 第 6 题

英文解析

6. Count the number of functions f : Z → { ‘green’ , ‘blue’ } such that f ( x ) = f ( x + 22) for all integers xand there does not exist an integer y with f ( y ) = f ( y + 2) = ‘green’.
   Answer: 39601 It is clear that f is determined by f (0) , . . . , f (21). The colors of the 11 evenintegers 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 correspondsbijectively to a string of 8 bits such that no two consecutive bits are 1. In general, the number of suchlength n strings is well known to be F (indexed according to F = 0, F = 1, F = F + F ),
   n +2 0 1 n +2 n +1 nwhich can be proven by recursion. Therefore, the number of colorings of even integers in this case is
   F = 55.
   If f (0) is ‘blue’, then a valid coloring of the 10 other even integers corresponds bijectively to a string 10
   as above, of 10 bits. The number of colorings for this case is F = 144. The total number of coloringsof even integers is 55 + 144 = 199.12
   Using the same reasoning for coloring the odd integers, we see that the number of colorings of all ofthe integers is 199 = 39601.2 1