HMMT 二月 2011 · 冲刺赛 · 第 18 题

英文解析

18. [ 10 ] In how many ways can each square of a 4 × 2011 grid be colored red, blue, or yellow such that notwo squares that are diagonally adjacent are the same color?
    4020
    Answer: 64 · 3
    If we first color the board in a checkerboard pattern, it is clear that the white squares are independentof the black squares in diagonal coloring, so we calculate the number of ways to color the white squaresof a 4 × n board and then square it.
    Let a be the number of ways to color the white squares of a 4 × n board in this manner such that thentwo squares in the last column are the same color, and b the number of ways to color it such that theynare different. We want to find their sum x . We have a = 3, b = 6. Given any filled 4 × n − 1 gridn 1 1
    with the two white squares in the last column different, there is only 1 choice for the middle squarein the n th row, and two choices for the outside square, 1 choice makes them the same color, 1 makesthem different. If the two white squares are the same, there are 2 choices for the middle square andthe outer square, so 4 choices. Of these, in 2 choices, the two new squares are the same color, and inthe other 2, the two squares are different. It follows that a = 2 a + b and b = 2 a + b ,
    n n − 1 n − 1 n n − 1 n − 1
    n − 1 2010 4020
    so a = b for n ≥ 2. We have x = 8 · 3 and x = 8 · 3 . So the answer is 64 · 3 .
    n n n 2011