Olympiad Maths Prep

Library / /54 of 55

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Ukraine

Given a white 6×20196 \times 2019 table. Andrii and Arsenii are playing the following game: one after another (starting with Andrii) a player colors one of the 1×11 \times 1 cells in black. Moreover, one's turn cannot create a 3×33 \times 3 square that contains two black cells. Whoever doesn't have a turn loses. Who will win if both want to win the game? And what is the strategy?

Figure 1

Fig. 3

Solution

We will show that there exists a strategy such that Arsenii always has a turn after Andrii's turn. We will split all the cells into *friendly pairs*. Two 1×11 \times 1 cells make a friendly pair, if they are in the same column and there are exactly two 1×11 \times 1 cells in-between. Then Arsenii colors the cell that makes a friendly pair with a cell that Andrii colored during his last turn.

We want to show that Arsenii always has such a turn. If Andrii colored some cell PP, then a cell VV, that makes a friendly pair with PP is white. Moreover, suppose the cell VV cannot be colored in black because there already is another black cell YY in some 3×33 \times 3 square that is located either in the very top or the very bottom of the table. Then there also exists another similar 3×33 \times 3 square either in the very top or the very bottom that contains cells PP and YY, both of which are black, where YY is a friendly pair of VV (Fig. 3). This completes the proof.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.