Library / /21 of 22

, 2024

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Turkey

A real number is written on each square of a $2024 \times 2024$ board such that sum of all real numbers on the board is equal to $2024$ . The board is also entirely covered by $1 \times 2$ or $2 \times 1$ dominoes each consisting $2$ unit squares of the board such that no square is covered by two different dominoes. For each domino, Asli erases the two numbers it covers, writes $0$ on one of the squares and writes the sum of the two numbers on the other square. Find the maximal possible number $k$ such that regardless of how the real numbers were written and the dominos were placed initially Asli can guarantee that after her moves there exists a column or row such that the sum of all numbers on it is at least $k$ .

Solution

Answer: $\frac{3}{2}$ .

First, we will give an example showing that the answer is at most $\frac{3}{2}$ . Suppose that initially the number $\frac{1}{2024}$ is written on each unit square. Let us divide the whole board to $4$ equal pieces each of sizes $1012 \times 1012$ and cover the top-left and bottom-right pieces with horizontal dominoes and the remaining ones with vertical dominoes. Then, initially the sum of numbers on each row or column is equal to $1$ and for any given row or column Asli can increase this sum by at most $\frac{1}{2}$ .

Now, let us prove that in any initial case Asli can get a row or column with sum at least $\frac{3}{2}$ . We use the method of double counting. Consider the maximal possible sum of entries for any given row or column. Let $S$ be the sum of all these $4048$ sums. Each number $t$ written on any unit square contributes $3t$ to $S$ since it contributes to either two rows and one column or two columns and one row. Hence, $S = 3 \cdot 2024 = 6072$ . Therefore, by pigeonhole principle, there exists at least one row or column that can achieve the sum $\frac{6072}{4048} = \frac{3}{2}$ . We are done.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.