Bogdanov I.I.

In the cells of a $100 \times 100$ square, the numbers $1,2, \ldots, 10000$ are placed, each exactly once; at the same time, numbers differing by 1 are placed in cells that share a side. After this, the distances between the centers of each pair of cells, the numbers in which differ by exactly 5000, were calculated. Let $S$ be the minimum of these distances. What is the largest value that $S$ can take?
We will number the rows (from bottom to top) and columns (from left to right) of the square with numbers from 1 to 100; we will denote a cell by a pair of the numbers of its row and column. We will call the distance between cells the distance between their centers. Cells will be called paired if the numbers in them differ by 5000. Note that the distance from the cell \((50,50)\) to any other cell (in particular, to a paired one) does not exceed \(\sqrt{50^{2}+50^{2}}=50 \sqrt{2}\). Therefore, the minimum distance between paired cells also does not exceed \(50 \sqrt{2}\). It remains to provide an example where this minimum is achieved.

We will divide our square into four \(50 \times 50\) squares. We will place the numbers from 1 to 2500 according to the rules in the lower left square so that the number 1 is in the cell \((1,1)\), and the number 2500 is in the cell \((50,1)\) (this is possible; for example, the first 50 numbers in the first column, the next 50 in the second column, and so on). Next, if the number \(a \in [1,2500]\) is in the cell \((i, k)\), then we will place the numbers \(a+2500\), \(a+5000\), and \(a+7500\) respectively in the cells \((k+50, i)\), \((k+50, i+50)\), and \((51-i, 101-k)\). It is easy to see that the numbers are still arranged according to the rules (for adjacent numbers in one square, this is obvious; for numbers 2500-2501, 5000-5001, and 7500-7501, it is verified directly).

It remains to check that the distances between paired cells are not less than \(50 \sqrt{2}\). Consider the segment between any paired cells. The sum of its horizontal and vertical projections is either \((50+k-i)+(50+i-k)=100\) or \((k+50-51+i)+(101-k-i)=100\), that is, it is always 100. Therefore, the square of the length of this segment is \(x^{2}+(100-x)^{2}=2(x-50)^{2}+5000 > 5000 = (50 \sqrt{2})^{2}\), which is what we needed.

Below is an example of a similar arrangement in an \(8 \times 8\) square.

![](https://cdn.mathpix.com/cropped/2024_05_06_98b9f094130a137f64e2g-38.jpg?height=752&width=746&top_left_y=1322&top_left_x=656)

Submit a comment