HMMT 二月 2003 · COMB 赛 · 第 2 题

HMMT February 2003 — COMB Round — Problem 2

You are given a 10 × 2 grid of unit squares. Two different squares are adjacent if they share a side. How many ways can one mark exactly nine of the squares so that no two marked squares are adjacent?

解析

You are given a 10 × 2 grid of unit squares. Two different squares are adjacent if they share a side. How many ways can one mark exactly nine of the squares so that no two marked squares are adjacent? Solution: 36 Since each row has only two squares, it is impossible for two marked squares to be in 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 assume without 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. Since the third row must contain a marked square, and it cannot be in the same column as 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 of more) consecutive rows of marked squares. As above, the configuration of the rows in each of the two blocks is determined by the position of the marked square in the first of its rows. That makes 2 × 2 = 4 possible configurations. There are eight possibilities for the empty row, making a total of 32 possibilities in this case. Together, there are 36 possible configurations of marked squares.