HMMT 二月 2015 · COMB 赛 · 第 6 题

HMMT February 2015 — COMB Round — Problem 6

Count the number of functions f : Z → { ‘green’ , ‘blue’ } such that f ( x ) = f ( x + 22) for all integers x and there does not exist an integer y with f ( y ) = f ( y + 2) = ‘green’. 1

解析

Count the number of functions f : Z → { ‘green’ , ‘blue’ } such that f ( x ) = f ( x + 22) for all integers x and 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 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 (indexed according to F = 0, F = 1, F = F + F ), n +2 0 1 n +2 n +1 n which can be proven by recursion. Therefore, the number of colorings of even integers in this case is F = 55. 10 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 = 144. The total number of colorings 12 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 2 the integers is 199 = 39601. 1