
4. Nela and Jane choose positive integer $k$ and then play a game with a $9 \times 9$ table. Nela selects in every of her moves one empty unit square and she writes 0 to it. Jane writes 1 to some empty (unit) square in every her move. Furthermore $k$ Jane's moves follows each Nela's move and Nela starts. If sum of numbers in each row and each column is odd anytime during the game, Jane wins. If girls fill out the whole table (without Jane's win), Nela wins. Find the least $k$ such that Jane has the winning strategy.

(Michal Rolínek)


Solution. Let us show at first that Jane wins for $k=3$. Let us assume $3 \times 3$ squares $A_{1}, A_{2}$ and $A_{3}$ (see the picture). We will call the $3 \times 3$ square covered if just one 1 is in each its row and column. If Jane covers squares $A_{1}, A_{2}$ and $A_{3}$ without writing to other squares, she wins, because sums in all rows and columns are odd number 1.

![](https://cdn.mathpix.com/cropped/2024_04_17_d252d571aa2423c54010g-06.jpg?height=383&width=392&top_left_y=602&top_left_x=561)

Fig. 3

It is obvious that if at most one 0 (and no 1 ) is written in any $3 \times 3$ square after Nela's move, Jane can cover this square because of $k=3$. Jane has the following strategy: If Nela writes 0 to any uncovered square $A_{1}, A_{2}$ or $A_{3}$, Jane covers it immediately. In the opposite case Jane covers any of the uncovered $3 \times 3$ squares. Jane thus wins after three her triples of moves.

We will show that Nela has winning strategy for $k \in\{1,2\}$. Let us realize that if Jane has some winning move, just 8 rows and 8 columns have odd sum before Jane's move, and the winning Jane's move is writing 1 to the intersection of the only one "even" row with the only one "even" column. This implies that if Jane has winning move, this move is unique.

Now it is obvious Nela's winning strategy for $k=1$. If Jane has winning move after her move, Nela writes 0 to this square and Jane looses her unique chance for win. In the opposite case Nela writes 0 to some empty square. This move doesn't change parity of sums in rows and columns and Jane still hasn't winning move. This strategy allows Nela to fill out whole table without giving Jane chance to win.

In the case $k=2$ Nela will use the same strategy as for $k=1$. This strategy doesn't give Jane chance to win in her first move. In the second move Jane can't win because after that move the table contains even number of 1 's which excludes possibility to be odd number 1's in every of (odd number) nine rows.

Conclusion. The least value $k$, for which Jane has winning strategy, is $k=3$.
