4. A $10 \times 10$ table is filled with numbers 1 and -1 such that the sum of the numbers in each row, except one, is equal to zero, and the sum of the numbers in each column, except one, is also equal to zero. Determine the maximum possible sum of all the numbers in the table.

(Patrik Bak)
SOLUTION. If we add up all the numbers in the considered table row by row, we will conclude that the total sum is equal to the sum of the numbers in the exceptional row where it is not zero. This sum is at most 10, and it equals 10 if all the numbers in the given row are ones. (We reach the same conclusion if we add up all the numbers in the table column by column.)

If we now provide an example of a filled $10 \times 10$ table that meets the conditions and where the sum of all the numbers is indeed 10, we will be done with solving the problem. We know that in such a table, there must be a row and a column filled entirely with ones. We place them in the first column from the left and the last row from the top. Then our task is to fill the remaining $9 \times 9$ square (in the top right corner of the table) with the numbers 1 and -1 so that in each of its rows and columns, there are exactly $5k$ times the number -1 (and thus 4 times the number 1).

The following images show three of the possible ways to accomplish the described task. For clarity, the numbers are not listed in the $10 \times 10$ tables. Instead, the cells with the number 1 are white (as is the case, for example, in the entire first column and the entire last row), and the cells with the number -1 are colored.
![](https://cdn.mathpix.com/cropped/2024_04_17_29a3dddc7a9db375e695g-09.jpg?height=462&width=1434&top_left_y=1231&top_left_x=310)

In the left image, a traditional construction with "cyclic shifting" of the colored group of cells along the rows of the "remaining" $9 \times 9$ table is used. The middle and right images are also not constructed randomly but by using a general method called mathematical induction. The way of coloring the cells on both images can be understood when we look at the parts $1 \times 1, 3 \times 3, 5 \times 5$, and $7 \times 7$ in the top left corner of the relevant $9 \times 9$ table.

Conclusion. The largest possible sum of all the numbers in the table is 10.

## GUIDING AND ADDITIONAL PROBLEMS:

N1. In one row, 71 numbers are written. Each of them is 1 or -1, and the sum of any ten consecutive numbers is 0. Prove that the first number is equal to the last number, and determine the largest possible sum of all the numbers. [The first 70 numbers can be divided into 7 tens with a sum of zero. The sum of all the numbers is therefore equal to the last number. Similarly, we find that the sum of all the numbers is equal to the first number when we consider the division into 7 tens of the last 70 numbers. The first and last numbers are therefore equal, and that is the sum of all the numbers, which is at most 1. The example of 71 numbers $1, -1, 1, \ldots, -1, 1$ satisfies the condition of the problem and their total sum is 1, which is the sought maximum possible sum.][^0]

N2. A $5 \times 4$ table is filled with the numbers 1 and -1 such that the sum of the numbers in each $2 \times 2$ square is 0. Determine the largest possible sum of all the numbers in the table. [The largest possible sum is 4. The given $5 \times 4$ table (with five rows and four columns) can be divided into the top row $1 \times 4$ and four $2 \times 2$ squares with zero sums of the written numbers. The sum of all the numbers in the table is therefore equal to the sum of the numbers in the first row, so it is at most 4. A sum of 4 can be achieved if the table is filled such that the first, third, and fifth rows contain only 1, while the second and fourth rows contain only -1.]

N3. For which $d \in \{0,1,2,3,4,5,6\}$ is it possible to color some cells of a $6 \times 6$ table so that in each row and each column there are exactly $d$ colored cells? [For each such $d$: For a given $d$, for example, the cells can be colored that contain numbers no greater than $d$ on the image.

| 1 | 2 | 3 | 4 | 5 | 6 |
| :--- | :--- | :--- | :--- | :--- | :--- |
| 6 | 1 | 2 | 3 | 4 | 5 |
| 5 | 6 | 1 | 2 | 3 | 4 |
| 4 | 5 | 6 | 1 | 2 | 3 |
| 3 | 4 | 5 | 6 | 1 | 2 |
| 2 | 3 | 4 | 5 | 6 | 1 |

D1. Is it possible to fill a square table with the numbers 1 and -1 so that the sum of the numbers in some column is even and in another column is odd? [No. In a square table $n \times n$, there are $n$ numbers in each column. If $a$ of them are 1, the others are $n-a$ and equal to -1, so the sum of the numbers in that column is $a - (n-a) = 2a - n$. This number is even, respectively odd, precisely when the number $n$ is. Thus, all the sums of the numbers in the individual columns have the same parity. Another explanation: The parity of the sum of the numbers in a given column does not change if each -1 in it is replaced by 1.]

D2. Is it possible to fill a $10 \times 10$ table with the numbers 1 and -1 so that the sum of the numbers in each row is the same and in each column is different? [Yes, see the image, where the cells with the number 1 are colored.

![](https://cdn.mathpix.com/cropped/2024_04_17_29a3dddc7a9db375e695g-10.jpg?height=474&width=468&top_left_y=1808&top_left_x=794)

D3. A $10 \times 10$ table is filled with the numbers 1 and -1 such that the sum of the numbers is positive in at least 9 rows. a) Prove that the sum of the numbers is positive in at least one column. b) Does the same conclusion hold under the weaker assumption that the sum of the numbers is positive in at least 8 rows? [a) The smallest possible positive sum in a row is 2. The sum of all the numbers in the table is therefore at least $9 \times 2 - 10$, which is a positive number. Therefore, it is impossible for the sum of the numbers in each column to be non-positive. b) The conclusion does not hold in general, see the example in the image, where the cells with the number 1 are colored.

![](https://cdn.mathpix.com/cropped/2024_04_17_29a3dddc7a9db375e695g-11.jpg?height=463&width=466&top_left_y=337&top_left_x=795)

D4. Determine for which natural numbers $n$ it is possible to fill a $n \times n$ table with the numbers 