59th Ukrainian National Mathematical Olympiad

We proceed by induction on $n$. One can verify that if the field is $2\times 2$ Olesya wins (by cutting entire $2\times 2$ square), and if the field is $2\times 4$ then Andrew wins (casework). If $n=2m+1$, then Olesya can cut $2\times 2$ square from the end of a strip and place herself in the position of a second player for even $n$. Hence, it remains to prove only that second player wins for even $n$.

Prior to and including the first $1\times 1$ square cut by the first player in the bordering column (i.e. the first or the last column of the “active” (see fig. 36) part of the playing field if we assume that the playing strip is placed horizontally) second player can follow the symmetric strategy. Clearly, he will be able to do so. Also, note that the first $1\times 1$ square will be cut when active playing field has dimensions $2\times k$, where $k$ is even (fig. 37).

After that point, the only thing he has to do is to prevent the cutting of $2\times 2$ square, because it will mean that the game will end after the even number of moves (because both players can cut only $1\times 1$).

Moreover, it is clear that the only places from which the $2\times 2$ square can be cut are the ends of the playing strip. It means that the second player does not have much to do at all: he cuts a unit square from one of the bordering (for the active part of the field) $2\times 2$ squares that has no unit squares already cut out ("free" ends).

Clearly, there is no greater than one free end, because Olesya cannot create two free ends in one move, and we "start" (after the first two bordering $1\times 1$ squares are cut) with zero free ends.

If, however, there are no free ends, then one of the following holds: 1. bordering column has no squares cut out, then Andrew can simply cut one unit square from it; 2. bordering column has one square cut out, a) and the second to border column has a square cut out, then Andrew can simply cut the second unit square from the bordering column; b) and the second to border column has no squares cut out, i. and the third to border column has no squares cut out, or it has a square cut out in the same row as for the bordering column, then Andrew can cut a unit square from the second to border column in the same row; ii. and the third to border column has a square cut out in the different row from that of the bordering column, then Andrew can cut a unit square from the bordering column, effectively decreasing the "active" playing field, but without creating free ends.