HMMT 二月 2008 · 冲刺赛 · 第 3 题

HMMT February 2008 — Guts Round — Problem 3

[ 5 ] How many ways can you color the squares of a 2 × 2008 grid in 3 colors such that no two squares of the same color share an edge? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 11 HARVARD-MIT MATHEMATICS TOURNAMENT, 23 FEBRUARY 2008 — GUTS ROUND 2

解析

[ 5 ] How many ways can you color the squares of a 2 × 2008 grid in 3 colors such that no two squares of the same color share an edge? 2008 Answer: 2 · 3 Denote the colors A, B, C . The left-most column can be colored in 6 ways. For each subsequent column, if the k th column is colored with AB , then the ( k + 1)th column can only be colored with one of BA, BC, CA . That is, if we have colored the first k columns, then there are 3 ways 2007 to color the ( k + 1)th column. It follows that the number of ways of coloring the board is 6 × 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 11 HARVARD-MIT MATHEMATICS TOURNAMENT, 23 FEBRUARY 2008 — GUTS ROUND 2