A real number is written on each square of a $2024 \times 2024$ chessboard. It is given that the sum of all real numbers on the board is $2024$. Then, the board is covered by $1 \times 2$ or $2\times 1$ dominos such that there isn't any square that is covered by two different dominoes. For each domino, Aslı deletes $2$ numbers covered by it and writes $0$ on one of the squares and the sum of the two numbers on the other square. Find the maximum number $k$ such that after Aslı finishes her moves, there exists a column or row where the sum of all the numbers on it is at least $k$ regardless of how dominos were replaced and the real numbers were written initially.
Problem
Source: Turkey JBMO TST 2024 P2
Tags: combinatorics
16.05.2024 13:45
We will prove that $k$ is $\frac{3}{2}$. For every row and column, sum up all the numbers in that row or column. Then, if any domino shares only $1$ common square with that row or column, add the number on the non-common square to the sum. Let's call the final sums $S_1, S_2,...., S_{4048}$. Claim: Every number is in $3$ sums. If a number is on a $\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline &\\\hline \end{array}$, then this number is in $2$ column sums and $1$ row sum. Similarly, if it is on the other type of domino, then it is in $2$ row sums and $1$ column sum. $\square$ Thus $\sum_{i=1}^{4048} S_i = 3.2024=6072$ Then there exists a $S_n \ge \frac{6072}{4048}=\frac{3}{2}$. For dominos $\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline a&b\\\hline \end{array}$ that share $1$ common square with this row or column, Aslı writes $a+b$ on the common square. Then, the final sum of this row or column is $S_n$. Thus, $k \ge \frac{3}{2}$. Now, let's give an example where Aslı can guarantee at most $\frac{3}{2}$. Let $\frac{1}{2024}$ be written on every square. Divide the square into $4\times4$ squares. For every $4\times4$ square, let dominos be placed like this where the same numbers represent the same dominos: $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1&1&2&3\\\hline 4&4&2&3\\\hline 5&6&7&7\\\hline 5&6&8&8\\\hline \end{array} $$ For this example, $k \le 1012.\frac{1}{1012}+506.\frac{1}{1012}=\frac{3}{2}$. Thus, $k=\frac{3}{2}$. $\blacksquare$