HMMT 十一月 2011 · 冲刺赛 · 第 31 题
HMMT November 2011 — Guts Round — Problem 31
题目详情
- [ 17 ] Each square in a 3 × 10 grid is colored black or white. Let N be the number of ways this can be done in such a way that no five squares in an ‘X’ configuration (as shown by the black squares below) √ are all white or all black. Determine N .
解析
- [ 17 ] Each square in a 3 × 10 grid is colored black or white. Let N be the number of ways this can be done in such a way that no five squares in an ‘X’ configuration (as shown by the black squares below) √ are all white or all black. Determine N . Guts Round Answer: 25636 Note that we may label half of the cells in our board the number 0 and the other half 1, in such a way that squares labeled 0 are adjacent only to squares labeled 1 and vice versa. In other words, we make this labeling in a ’checkerboard’ pattern. Since cells in an ’X’ formation are all √ labeled with the same number, the number of ways to color the cells labeled 0 is N , and the same is true of coloring the cells labeled 1. Let a be the number of ways to color the squares labeled 0 in a 3 by 2 n grid without a monochromatic 2 n ’X’ formation; we want to find a . Without loss of generality, let the rightmost column of our grid 10 have two cells labeled 0. Let b be the number of such colorings on a 3 by 2 n grid which do not have 2 n two black squares in the rightmost column and do not contain a monochromatic ’X’, which we note is also the number of such colorings which do not have two white squares in the rightmost column. Now, we will establish a recursion on a and b .We have two cases: 2 n 2 n • Case 1: All three squares in the last two columns are the same color. For a , there are 2 ways to 2 n color these last three squares, and for b there is 1 way to color them. Then, we see that there 2 n are b ways to color the remaining 2 n − 2 columns. 2 n − 2 • Case 2: The last three squares are not all the same color. For a , there are 6 ways to color the 2 n last three squares, and for b there are 5 ways to color them. Then, there are a ways to 2 n 2 n − 2 color the remaining 2 n − 2 columns. Consequently, we get the recursions a = 6 a + 2 b and b = 5 a + b . From the first 2 n 2 n − 2 2 n − 2 2 n 2 n − 2 2 n − 2 1 equation, we get that b = a − 3 a . Plugging this in to the second equations results in the 2 n 2 n +2 2 n 2 recurion 1 1 a − 3 a = 5 a + a − 3 a ⇒ a = 7 a + 4 a . 2 n +2 2 n 2 n − 2 2 n 2 n − 2 2 n +2 2 n 2 n − 2 2 2 3 Now, we can easily see that a = 1 and a = 2 = 8, so we compute a = 25636 . 0 2 10