The numbers $1, 2,. . . , 10000, $ were placed in the cells of a $100 \times 100$ square, each once; in this case, numbers differing by $1$ are written in cells adjacent to each side. After that we calculated distances between the centers of every two cells whose numbers differ by exactly $5000$. Let $S$ be the minimum of these distances What is the largest value $S$ can take?
Problem
Source: Russian Regional Olympiad 2010 11.8
Tags: combinatorics
rms
25.08.2024 17:45
parmenides51 wrote: The numbers $1, 2,. . . , 10000, $ were placed in the cells of a $100 \times 100$ square, each once; in this case, numbers differing by $1$ are written in cells adjacent to each side. After that we calculated distances between the centers of every two cells whose numbers differ by exactly $5000$. Let $S$ be the minimum of these distances What is the largest value $S$ can take? Translated from here.
**Answer:** \( 50\sqrt{2} \).
**Solution** We will number the rows (from bottom to top) and columns (from left to right) in the square with numbers from 1 to 100; let’s denote a cell by the pair of numbers of its row and column. We will call the distance between cells the distance between their centers. We will call cells *paired* if the numbers in them differ by 5000.
Notice that the distance from cell \( (50, 50) \) to any other (in particular, to its paired cell) 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.
Let’s divide our square into four squares of \(50 \times 50\). We will arrange the numbers 1–2500 according to the rule in the lower left square such that the number 1 is in cell \((1, 1)\), and the number 2500 is in cell \((50, 1)\) (this is possible; for example, the first 50 numbers are in the first column, the next 50 are in the second column, and so on). Next, if the number \(a \in [1, 2500]\) is in cell \((i, k)\), then we place the numbers \(a + 2500\), \(a + 5000\), and \(a + 7500\) in cells \((k + 50, i)\), \((k + 50, 51 - i)\), and \((51 - i, 101 - k)\), respectively. It’s easy to see that with this arrangement, the numbers are still placed according to the rules (for neighboring numbers in one square, this is obvious; for the numbers 2500–2501, 5000–5001, and 7500–7501, it can be checked directly).
It remains to check that the distance between paired cells is not less than \(50\sqrt{2}\). Let’s 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 equal to 100. Thus, the square of the length of the segment is equal to \(x^2 + (100 - x)^2 = 2(x - 50)^2 + 5000 \geq 5000 = (50\sqrt{2})^2\), which is what was required to prove.
Figure 5 shows an example of a similar arrangement in an \(8 \times 8\) square.
**Note.** The proposed example is not unique. A similar example can be constructed in any square \(4n \times 4n\). In a square \((4n + 2) \times (4n + 2)\), a similar arrangement is also possible.
Attachments:
