Bogdanov I.I.

A $100 \times 100$ square is cut into dominoes. Two players play a game. On each turn, a player glues together two adjacent cells along a cut. A player loses if, after their move, the figure becomes connected, meaning the entire square can be lifted from the table by holding one cell. Who will win with correct play - the first player or their opponent?

#
Let's present a winning strategy for the second player. The first few moves will glue each cell adjacent to the boundary of the square to all its neighbors. This will take no more than 8.99 moves, meaning that after this, a total of $16 \cdot 99$ pairs of sides will be glued, and as a result, no more than

$2 \cdot 16 \cdot 99 < 5000$ dominoes will be glued to something else. Consequently, after this, there will still be separate dominoes, and the figure will not be connected.

Next, the second player will act arbitrarily, only ensuring not to lose on the next move.

Suppose at some point he cannot do this. Then all dominoes will split into two connected figures, and all unglued segments will be the boundary between these figures, since any other segment can be glued. At the same time, one of these figures will contain all the boundary cells of the square.

The boundary of the inner figure contains an even number of segments (see problem 30932). Let's calculate the initial number of cut segments. It is equal to the total perimeter of all dominoes, reduced by the perimeter of the square and divided by 2 (since each of the other segments was counted twice), that is, $(6 \cdot 5000 - 400) : 2$ - an even number. Thus, by this moment, an even number of sides have been glued, and it is the first player's turn to move. Contradiction.

## Answer

Opponent.

Submit a comment