Problem

Source: Ukrainian Mathematical Olympiad 2023. Day 1, Problem 10.2

Tags: combinatorics, games, colorings



On a rectangular board $100 \times 300$, two people take turns coloring the cells that have not yet been colored. The first one colors cells in yellow, and the second one in blue. Coloring is completed when every cell of the board is colored. A connected sequence of cells is a sequence of cells in which every two consecutive cells share a common side (and all cells in the sequence are different). Consider all possible connected sequences of yellow cells. The result of the first player is the number of cells in the connected 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 tries to achieve his goal, the result of the first player will be no more than $200$. Proposed by Mykhailo Shtandenko and Fedir Yudin