HMMT 二月 2003 · GEN2 赛 · 第 5 题

英文解析

5. You are given a 10 × 2 grid of unit squares. Two different squares are adjacent if theyshare a side. How many ways can one mark exactly nine of the squares so that no twomarked squares are adjacent?
   Solution: 36
   Since each row has only two squares, it is impossible for two marked squares to bein the same row. Therefore, exactly nine of the ten rows contain marked squares.
   Consider two cases:
   Case 1: The first or last row is empty. These two cases are symmetrical, so assumewithout loss of generality that the first row is empty. There are two possibilities for the second row: either the first square is marked, or the second square is marked. Sincethe third row must contain a marked square, and it cannot be in the same columnas the marked square in the second row, the third row is determined by the second.
   Similarly, all the remaining rows are determined. This leaves two possibilities if the first row is empty. Thus, there are four possibilities if the first or last row is empty.
   Case 2: The empty row is not the first or last. Then, there are two blocks of (one ofmore) consecutive rows of marked squares. As above, the configuration of the rows ineach of the two blocks is determined by the position of the marked square in the firstof its rows. That makes 2 × 2 = 4 possible configurations. There are eight possibilitiesfor the empty row, making a total of 32 possibilities in this case.
   Together, there are 36 possible configurations of marked squares.