Hrramcovd

Find the largest natural number $N$, for which in any arrangement of different natural numbers from 1 to 400 in the cells of a $20 \times 20$ square table, there will be two numbers in the same row or column whose difference is at least $N$.

#
Example. Let's divide the table into two $20 \times 10$ rectangles vertically. In the first rectangle, we will place numbers from 1 to 200 in increasing order by rows (from 1 to 10 in the first row, from 11 to 20 in the second row, and so on). In the second rectangle, we will place numbers from 201 to 400 in the same manner. Then the maximum difference between numbers in each row is $210-1=209$, and in each column $191-190$. Therefore, $N \leq 209$.

We will mark all rows and columns that contain numbers from 1 to 91 in red, and all rows and columns that contain numbers from 300 to 400 in the second rectangle in blue.

Let $i$ be the number of red-marked rows and $j$ be the number of red-marked columns. Then all numbers from 1 to 91 are located in the cells at their intersections, so $i j \geq 91$. Therefore,

$i+j \geq 2 \sqrt{i j} \geq 2 \sqrt{91}>19$. Thus, at least 20 lines (rows or columns) are marked in red.

Similarly, for $k$ blue-marked rows and $l$ blue-marked columns, the sum $k+l \geq 2 \sqrt{101}>20$, meaning at least 21 lines are marked in blue.

From this, it follows that some line will be marked both in red and in blue, and in this line, the maximum difference between numbers will be at least $300-91=209$.

## Answer

$N=209$.

Submit a comment