Pre-IMO 2017 Mock Exam

We claim that the smallest unnatural case is $n=6$. In the following, we use $(i,j)$ to mean the cell in the $i$th row and the $j$th column, and use $(i,j)-(i,k)$ to mean the consecutive cells from $(i,j)$ to $(i,k)$ inclusive (similar for $(i,j)-(k,j)$).

For $n=2$, X and Y can play in any way and the natural loser X will lose.

For $n=3$, Y is the natural loser and X has a winning strategy. In the first round, X marks $(2,2)$. WLOG Y has to mark $(1,1)-(1,2)$. Then X can take $(3,1)-(3,3)$.

For $n=4$, Y has a winning strategy. In round 1, we may assume X chooses a cell in the upper left $2\times 2$ corner. Then Y can mark 2 consecutive cells in the same $2\times 2$ corner. This leaves 2 unoccupied rows as well as 2 unoccupied columns. WLOG we may assume X chooses certain cells from a row in round 3. Then there is at least one unoccupied row left, which can be marked by Y in round 4.

For $n=5$, X has a winning strategy by first choosing $(3,3)$. WLOG, we may assume Y chooses 2 cells in the upper left $3\times 3$ corner in the next round. Then X can always choose 3 consecutive cells from the same $3\times 3$ corner. Again, there are at least 2 unoccupied rows and 2 unoccupied columns. For the same reason as the case $n=4$, X can win the game.

The same trick no longer works for $n=6$. The natural loser X can still win the game. We propose a winning strategy as follows. Firstly, X chooses $(1,1)$. WLOG assume Y chooses 2 cells $(i,j)-(i+1,j)$ in the $j$th column in the next round.

If $j=1$, X chooses $(3,3)-(3,5)$ in round 3. This blocks columns 3, 4, 5 and hence Y must mark at least one cell in column 2 or column 6 (but not both columns with obvious reason) in round 4. If some cells in column 2 (column 6 in the second case) is used, X can then take $(2,6)-(6,6)$ (correspondingly $(2,2)-(6,2)$) in round 5. Then all rows and columns have been used so that Y will lose.

A similar strategy works for cases $j=2,5,6$. Y loses in all following subcases. - For $j=2$, X chooses $(3,3)-(3,5)$. In round 5, X should take $(2,1)-(6,1)$ or $(2,6)-(6,6)$, depending on column 6 is used or not. - For $j=5$, X chooses $(3,2)-(3,4)$. In round 5, X should take $(2,1)-(6,1)$ or $(2,6)-(6,6)$, depending on column 6 is used or not. - For $j=6$, X chooses $(3,2)-(3,4)$. In round 5, X should take $(2,1)-(6,1)$ or $(2,5)-(6,5)$, depending on column 5 is used or not.

If $j=3,4$ and $i=1,4,5$, X can still choose $(3,3)-(3,5)$ in round 3. - If Y chooses at least one cell in column 2 in round 4, X can then take $(2,6)-(6,6)$ in round 5. Y loses. - If Y chooses at least one cell in column 6 in round 4, X can then take $(2,2)-(6,2)$ in round 5. Y loses. - Suppose Y chooses $(2,1)-(5,1)$ in round 4. Next, X should take $(6,2)-(6,6)$ if row 6 is not used in round 2, or take $(1,2)-(1,6)$ otherwise. Y loses. - Suppose Y chooses $(3,1)-(6,1)$ in round 4. Next, X should take $(2,2)-(2,6)$ if row 2 is not used in round 2, or take $(6,2)-(6,6)$ otherwise. Y loses.

If $j=3,4$ and $i=2,3$, X can take $(5,3)-(5,5)$ in round 3. - If Y chooses at least one cell in column 2 in round 4, X can then take $(2,6)-(6,6)$ in round 5. Y loses. - If Y chooses at least one cell in column 6 in round 4, X can then take $(2,2)-(6,2)$ in round 5. Y loses. - If Y chooses $(2,1)-(5,1)$ in round 4, X can take $(6,2)-(6,6)$ in round 5. Y loses. - Suppose Y chooses $(3,1)-(6,1)$ in round 4. Next, X should take $(2,2)-(2,6)$ if row 2 is not used in round 2, or take $(6,2)-(6,6)$ otherwise. Y loses. - If Y chooses 4 consecutive cells in column 3, 4 or 5 in round 4, then the first 5 rows are all occupied. X can then take $(6,2)-(6,6)$ in round 5. Y loses.

In all cases, X can win the game when $n=6$. This completes the proof. $\square$