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

HMMT February 2011 — Guts Round — Problem 18

[ 10 ] In how many ways can each square of a 4 × 2011 grid be colored red, blue, or yellow such that no two squares that are diagonally adjacent are the same color?

解析

[ 10 ] In how many ways can each square of a 4 × 2011 grid be colored red, blue, or yellow such that no two 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 independent of the black squares in diagonal coloring, so we calculate the number of ways to color the white squares of 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 the n two squares in the last column are the same color, and b the number of ways to color it such that they n are different. We want to find their sum x . We have a = 3, b = 6. Given any filled 4 × n − 1 grid n 1 1 with the two white squares in the last column different, there is only 1 choice for the middle square in the n th row, and two choices for the outside square, 1 choice makes them the same color, 1 makes them different. If the two white squares are the same, there are 2 choices for the middle square and the outer square, so 4 choices. Of these, in 2 choices, the two new squares are the same color, and in the 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