HMMT 十一月 2015 · 冲刺赛 · 第 19 题
HMMT November 2015 — Guts Round — Problem 19
题目详情
- [ 11 ] Each cell of a 2 × 5 grid of unit squares is to be colored white or black. Compute the number of such colorings for which no 2 × 2 square is a single color.
解析
- [ 11 ] Each cell of a 2 × 5 grid of unit squares is to be colored white or black. Compute the number of such 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 b n n denote the number of ways to color a 2 × n grid subject to the given constraint, but with the added restriction 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 2x2 square is guaranteed not to be monochromatic, and so the remaining 2 × ( n − 1) subgrid can be colored in a ways. Otherwise, it is n − 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 first column cannot be colored black-black, and if it is colored white-black or black-white, there are a n − 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 1 Therefore, we have b = 2 a + ( a − 2 a ), and so a = 2 a + 2 b = 2 a + 2(2 a + n n − 1 n n − 1 n n − 1 n − 1 n − 1 n − 2 2 1 ( a − 2 a )) = 3 a + 2 a . Finally, we have a = 1 (as the only possibility is to, well, do n − 1 n − 2 n − 1 n − 2 0 2 nothing) and a = 4 (as any 2 × 1 coloring is admissible), so a = 14 , a = 50 , a = 178 , a = 634 . 1 2 3 4 5