HMMT 十一月 2015 · 冲刺赛 · 第 19 题

英文解析

19. [ 11 ] Each cell of a 2 × 5 grid of unit squares is to be colored white or black. Compute the number ofsuch colorings for which no 2 × 2 square is a single color.
    Proposed by: Alexander Katz
    Answer: 634
    Let a denote the number of ways to color a 2 × n grid subject only to the given constraint, and bn ndenote the number of ways to color a 2 × n grid subject to the given constraint, but with the addedrestriction that the first column cannot be colored black-black.
    Consider the first column of a 2 × n grid that is not subject to the additional constraint. It can be colored black-white or white-black, in which case the leftmost 2 x 2 square is guaranteed not to bemonochromatic, and so the remaining 2 × ( n − 1) subgrid can be colored in a ways. Otherwise, it isn − 1
    colored white-white or black-black; WLOG, assume that it’s colored black-black. Then the remaining
    2 × ( n − 1) subgrid is subject to both constraints, so there are b ways to color the remaining subgrid.
    n − 1
    Hence a = 2 a + 2 b .
    n n − 1 n − 1
    Now consider the first column of a 2 × n grid that is subject to the additional constraint. The firstcolumn cannot be colored black-black, and if it is colored white-black or black-white, there are an − 1
    ways to color the remaining subgrid by similar logic to the previous case. If it is colored white-white,
    then there are b ways to color the remaining subgrid, again by similar logic to the previous case.
    n − 1
    Hence b = 2 a + b .
    n n − 1 n − 1
    Therefore, we have b = 2 a + ( a − 2 a ), and so a = 2 a + 2 b = 2 a + 2(2 a +1
    n n − 1 n n − 1 n n − 1 n − 1 n − 1 n − 2
    ( a − 2 a )) = 3 a + 2 a . Finally, we have a = 1 (as the only possibility is to, well, do 12
    n − 1 n − 2 n − 1 n − 2 0
    nothing) and a = 4 (as any 2 × 1 coloring is admissible), so a = 14 , a = 50 , a = 178 , a = 634 .2
    1 2 3 4 5