62nd Ukrainian National Mathematical Olympiad

Question

On a rectangular board 100 300 two people take turns coloring the uncolored cells. The first one paints yellow, the second one paints blue. The coloring is completed when every cell on the board is colored. A *sequence of* cells is a set of cells in which two consecutive cells share a common side (all cells in the sequence are different). Consider all possible sequences of yellow cells. The *result* of the first player is the number of cells in the sequence of yellow cells of maximum length. The first player's goal is to maximize the result, and the second player's goal is to make the first player's result as small as possible. Prove that if each player strives to achieve his goal, the first player's result will be no more than 200.

Accepted Answer

Let's divide the entire board into vertical dominoes, whose larger sides are parallel to the larger side of the board. Let's consider the second player's strategy: he paints the second square of the domino whose first square was painted by the first player in the previous move. Then it is clear that no sequence of yellow cells crosses the horizontal grid lines of the rectangular board, which divide the dominoes in half. So under such conditions, the sequence with the maximum number of yellow cells can contain only the adjacent two rows of our board, that is, its result will not exceed 200, which is what we needed to prove.