Argentine National Olympiad 2016

We describe a winning strategy for the second player Lucas. It applies to any grid square $n\times n$ with odd $n\ge 3$. Call a row or column empty, incomplete or full at a certain moment of the game if it contain respectively 0, 1 or 2 marked cells. The strategy of Lucas has two stages.

Stage 1: The first move of Agustin has the following properties. It is in an empty row $R$ and an empty column $C$, and after it there are still empty rows left. Call such a move standard. The answer of Lucas to a standard move of Agustin is to choose an empty row $R^{\prime }\ne R$ and mark the intersection of $R^{\prime }$ and column $C$. Such a standard answer is allowed by the rules, and it makes $C$ a full column; thus $C$ cannot be used later on. Let Lucas give standard answers as long as Agustin makes standard moves (at least Agustin's first move is standard). Observe that each column either empty or full after every standard answer of Lucas, hence Agustin's next move is in an empty column. Since there is a standard answer to any standard move, Lucas cannot lose if all of Agustin's moves are standard. Suppose then that Agustin makes non-standard moves, and let $M$ be the first one of them. As explained above, $M$ is in an empty column $C$. There are two possibilities: (1) $M$ is in an incomplete row $R$; (2) $M$ is in the last empty row remaining. In case (1) there are still empty rows left. Indeed each previous combined move of the two leaves an odd number of empty rows because $n$ is odd. So Lucas gives a standard answer again: taking an empty row $R^{\prime }\ne R$ and marking the intersection of $R^{\prime }$ and column $C$. In case (2) all rows are incomplete after $M$. Here Lucas takes any row $R^{\prime }\ne R$ and marks the intersection of $R^{\prime }$ and column $C$, thus making $R^{\prime }$ full. This completes stage 1. As a result the table has the following properties: (i) The number $E$ of empty rows is even. (ii) The number $I$ of incomplete rows is even. (iii) There are no incomplete columns. Indeed $E$ is odd and $I$ is even after all moves before $M$, while the last combined move of the two decreases $E$ by 1 and does not change $I$, in both case 1 and 2. Hence (i) and (ii) hold. As for (iii), it holds after every move of Lucas so far.

Stage 2: Now Lucas makes sure that after each move of his properties (i) - (iii) are preserved. Let us justify that he can achieve this no matter how Agustin plays. Let Agustin make a move $M$ in row $R$ and column $C$, where $R$ is empty. Then $C$ was also empty before $M$. This is because by (iii) there were no incomplete columns before $M$, and one cannot move in a full column. So $M$ makes both $R$ and $C$ incomplete, in particular, by (i), $E$ is odd after $M$. Hence it is possible for Lucas to mark the intersection of one empty row $R^{\prime }\ne R$ and column $C$. This is a standard answer which makes $C$ full and $R^{\prime }$ incomplete. Thus the combined move of Agustin and Lucas decreases $E$ by 2 and increases $I$ by 2. Hence (i) - (iii) are preserved after the answer of Lucas.

Similarly let Agustin make a move $M$ in row $R$ and column $C$ where $R$ is incomplete. As in the previous case, $C$ was empty before $M$. So $M$ makes $R$ full and $C$ incomplete. Then by (ii) $I$ is odd after $M$. Hence Lucas can mark the intersection of one incomplete row $R^{\prime }\ne R$ and column $C$, making both $R^{\prime }$ and $C$ full. The combined move of Agustin and Lucas decreases $I$ by 2 and does not change $E$. Again, (i) - (iii) are maintained after the answer of Lucas.

In conclusion, Lucas is able to answer any move of Agustin at the second stage, hence he will not lose. The game is finite; there will be a loser, and it is not Lucas. Hence eventually Agustin loses and thus Lucas wins.