HMMT 十一月 2011 · 冲刺赛 · 第 31 题

英文解析

31. [ 17 ] Each square in a 3 × 10 grid is colored black or white. Let N be the number of ways this can bedone 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 otherhalf 1, in such a way that squares labeled 0 are adjacent only to squares labeled 1 and vice versa. Inother 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 istrue 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 gridhave two cells labeled 0. Let b be the number of such colorings on a 3 by 2 n grid which do not have 10
    2 ntwo black squares in the rightmost column and do not contain a monochromatic ’X’, which we note isalso 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 ncolor these last three squares, and for b there is 1 way to color them. Then, we see that there
    2 nare 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 nlast 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
    equation, we get that b = a − 3 a . Plugging this in to the second equations results in the 1
    2 n 2 n +2 2 nrecurion 2
    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
    Now, we can easily see that a = 1 and a = 2 = 8, so we compute a = 25636 .3
    0 2 10