LI OM - III - Task 5

For a given natural number $ n \geq 2 $, find the smallest number $ k $ with the following property. From any $ k $-element set of fields of the $ n \times n $ chessboard, one can select a non-empty subset such that the number of fields of this subset in each row and each column of the chessboard is even.
We will prove the following two statements:

From any set composed of $ m + n $ squares of a chessboard with dimensions $ m \times n $ ($ m,n \geq 2 $), one can select a non-empty subset having an even number of squares in each row and each column of the chessboard.

There exists a set of $ m+n-1 $ squares of a chessboard with dimensions $ m \times n $, from which it is not possible to select a non-empty subset having an even number of squares in each row and each column of the chessboard.

From the above statements applied for $ m = n $, we conclude that the smallest number satisfying the conditions of the problem is $ k = 2n $.
Proof of statement 1.
We will conduct an inductive proof with respect to $ m + n $. For $ m = 2 $, $ n = 2 $, the statement 1 is true.
Let us fix two natural numbers $ m $, $ n $ with a sum greater than $ 4 $ and assume that statement 1 is true for any chessboard with a sum of dimensions less than $ m + n $. Consider any set $ A $ composed of $ m + n $ squares of a chessboard $ S $ with dimensions $ m \times n $. The following three cases are possible:

there exists a row or column of the chessboard $ S $ that does not contain any square from the set $ A $;
there exists a row or column of the chessboard $ S $ that contains exactly one square from the set $ A $;
in each row and each column, there are at least two squares from the set $ A $.

om51_3r_img_4.jpg
In case (a), we remove from the chessboard $ S $ that column (or row) which does not contain any square from the set $ A $. We then remove any square from the set $ A $ (in the figure, the squares of set $ A $ are marked with circles). In this way, we obtain a new chessboard that contains a certain set $ A $ composed of $ m + n - 1 $ squares and whose sum of dimensions is equal to $ m + n - 1 $ (fig. 2). Hence, each of the dimensions of the obtained chessboard is not less than $ 2 $. Therefore, by the inductive assumption, one can select from the set $ A $ a non-empty subset having an even number of squares in each row and each column. By reinserting the removed column or removed row back into its place (fig. 3), we obtain the desired subset of the set $ A $.
om51_3r_img_5.jpg
We proceed similarly in case (b): we first find a column (or row) that contains exactly one square from the set $ A $, and then remove that column from the chessboard $ S $ (fig. 4). As a result, we obtain a new chessboard that contains a certain set $ A' $ composed of $ m + n - 1 $ squares and whose sum of dimensions is equal to $ m + n - 1 $ (fig. 5). As above, we apply the inductive assumption, and then reinsert the removed column or removed row (fig. 6).
Consider case (c). Let $ k_1,k_2,\ldots,k_n, w_1,w_2,\ldots,w_m $ denote, respectively, the numbers of squares of the set $ A $ in the individual columns and rows. Then

Moreover, $ k_i,w_j \geq 2 $ for all $ i $, $ j $. Hence, $ k_i = w_j = 2 $. This means that the set $ A $ has exactly two squares in each column and each row. This implies that the number of squares of the set $ A $ in each row and each column is even.
The inductive proof, and thus the proof of statement 1, is complete.
Proof of statement 2.
om51_3r_img_6.jpg
Consider the set $ A $ composed of all $ m + n - 1 $ squares of a chessboard with dimensions $ m \times n $ located in the bottom row and the first column (fig. 7). To obtain an even number of squares in the columns from the second to the last, we must remove from the set $ A $ the squares that are in those columns. After their removal, we see that for the same reason, we must remove the remaining squares of the set $ A $. This completes the proof of statement 2.