4. Nela and Jana choose a natural number $k$ and then play a game with a $9 \times 9$ table. Starting with Nela, each player, on their turn, selects an empty cell and writes a zero in it. Jana, on her turn, writes a one in some empty cell. Additionally, after each of Nela's moves, Jana makes $k$ moves. If at any point during the game, the sum of the numbers in each row and each column is odd, Jana wins. If the girls fill the entire table without this happening, Nela wins. Find the smallest value of $k$ for which Jana has a winning strategy.
SOLUTION. Let's first show that in the case $k=3$, Jana wins. We will work with squares $A_{1}, A_{2}$, and $A_{3}$ of size $3 \times 3$ (Fig. 3). A $3 \times 3$ square is considered covered if there is exactly one one in each of its rows and columns. If Jana covers the squares $A_{1}, A_{2}$, and $A_{3}$ without playing into other squares, she ensures her victory, as all row and column sums will be equal to the odd number 1.

![](https://cdn.mathpix.com/cropped/2024_04_17_ef3d84e533bc09b28859g-06.jpg?height=532&width=531&top_left_y=682&top_left_x=768)

Fig. 3

It is clear that if after Nela's move there is at most one zero (and no one) in some $3 \times 3$ square, Jana can cover this square with a triplet of her moves thanks to the value $k=3$. Jana's strategy is therefore as follows: If Nela plays into one of the uncovered squares $A_{1}, A_{2}$, or $A_{3}$, Jana will immediately cover this square. Otherwise, Jana will cover any of the still uncovered squares $A_{1}, A_{2}$, and $A_{3}$. After the first three triplets of moves, Jana will always win this way.

We claim that in the cases $k \in \{1,2\}$, Nela has a winning strategy. First, note that if a move offers Jana a win (let's call it a winning move), it means that before it is played, the sum is odd in exactly eight columns and eight rows, and that winning move is Jana's move at the intersection of the single "even" row and the single "even" column. This implies that if Jana ever has a winning move, there is exactly one such move.

Now it is clear how Nela can achieve victory in the case $k=1$. If Jana has a winning move after her turn, Nela writes a zero on that cell, and Jana thus loses her (only) chance to win in the next turn. If, on the other hand, Jana does not have a winning move after her turn, Nela writes a zero anywhere. This does not change the sums in the rows or columns, so Jana will not win with the next move. This way, Nela will achieve the filling of the entire table without allowing Jana to win.

In the case $k=2$, Nela will play according to the same strategy as for $k=1$, thus preventing Jana from ever winning after the first move of her pair. In the second move, however, Jana can never win, because after it is played, there will be an even number of ones in the table, and it will be impossible for an odd number of ones to be in each of the (odd number of) nine rows.

Answer. The smallest value of $k$ for which Jana has a winning strategy is $k=3$.

GUIDING AND ADDITIONAL PROBLEMS:

N1. Solve the given game first in a $3 \times 3$ table.

N2. On a magic tree, 25 lemons and 30 oranges grew. The gardener picks two fruits every day, and overnight, one new fruit grows on the tree, an orange (respectively, a lemon) if the picked fruits were the same (respectively, different). What fruit will grow on the tree last? [Lemon — their number is odd after each night.]

D1. Simona and Lenka play a game. For a given integer $k$ such that $0 \leq k \leq 64$, Simona selects $k$ cells of an $8 \times 8$ chessboard and marks each with a cross. Lenka then fills the chessboard with thirty-two domino tiles in some way. If the number of tiles covering two crosses is odd, Lenka wins; otherwise, Simona wins. Determine, depending on $k$, which of the girls has a winning strategy. [64-C-I-3]

D2. In the top-left corner of an $8 \times 8$ chessboard stands a king figure. Two players take turns making moves, each moving the figure (with a legal chess move) to a place where it has not stood before. The player who cannot make a move loses. Show that the player who moves first has a winning strategy. [Divide the chessboard into $2 \times 1$ rectangles and find a strategy for the first player in which they do not move into any rectangle first.]

D3. In the top-left corner of an $8 \times 8$ chessboard stands a knight figure. Two players take turns making moves, each moving the figure (with a legal chess move) to a place where it has not stood before. The player who cannot make a move loses. Show that the starting player has a winning strategy. [Divide the chessboard into $2 \times 4$ rectangles and divide the cells within them into pairs with the same intention as in problem D2.]