Kvant Math Problem 866
Represent the cells by lattice points $(i,j)$, where $1\le i\le m$ and $1\le j\le n$, the coordinates being the centers of the cells.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m01s
Source on kvant.digital
Problem
- Each cell of the square $20 \times 20$ contains one soldier. For the largest possible $d$, how can the soldiers be rearranged into other cells so that each moves a distance of at least $d$? (Distance is measured as a straight line between the centers of the old and new cells; the side of a cell is 1.)
Solve the same problem
- for the square $21 \times 21$;
- for the rectangle $m \times n$ of cells.
S. S. Krotov
Cities Tournament (spring, 1984)
Exploration
Represent the cells by lattice points $(i,j)$, where $1\le i\le m$ and $1\le j\le n$, the coordinates being the centers of the cells. A rearrangement is a permutation of these lattice points. We seek the largest number $d$ for which there exists a permutation such that every point moves at least distance $d$.
The first task is to find a universal upper bound. If a point remains within distance $d$, that is bad; we want every point farther than $d$. Thus, for a given $d$, every point must be matched to a point outside the disk of radius $d$ centered at it.
A natural obstruction comes from the center of the board. Consider all cells within distance $r$ of the center. If this central set contains more cells than there are cells outside the same disk, then some cell of the central set must be sent to another cell of the central set. Its displacement is then at most the diameter of the disk, namely $2r$. Hence any feasible $d$ satisfies $d\le 2r$ whenever the central disk contains more than half the cells.
For a $20\times20$ board, the center is the point $(10.5,10.5)$. The cells whose centers satisfy
$$|x-10.5|\le 4.5,\qquad |y-10.5|\le 4.5$$
form a $10\times10$ square of $100$ cells. Since the board has $400$ cells, this is exactly one quarter, not enough. Enlarging to the $12\times12$ central square gives $144$ cells. The complement has $256$ cells, still larger.
The right idea is to use the largest central square containing more than half the cells. For even side length $20$, the central $14\times14$ square contains $196<200$ cells, while the central $15\times15$ square is impossible because the board coordinates are integral. A different count is needed.
Trying small cases helps. For a line of length $n$, the optimal strategy is to reverse the order. Then the minimum displacement equals $\lfloor n/2\rfloor$. This suggests that in two dimensions one should reverse both coordinates:
$$(i,j)\mapsto (m+1-i,; n+1-j).$$
The displacement becomes
$$\sqrt{(m+1-2i)^2+(n+1-2j)^2}.$$
The minimum occurs at cells nearest the center. For even dimensions, the minimum is $\sqrt2$; for odd dimensions, there is a fixed center cell, giving displacement $0$. Thus complete reversal is far from optimal when odd dimensions occur.
A better idea is to shift by half the board. In one dimension, the cyclic shift by $\lfloor n/2\rfloor$ positions is optimal. For a rectangle, apply such a shift independently in each coordinate. Then every horizontal displacement is either $\lfloor m/2\rfloor$ or $\lceil m/2\rceil$, and every vertical displacement is either $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$. The minimum distance produced is
$$\sqrt{\lfloor m/2\rfloor^2+\lfloor n/2\rfloor^2}.$$
The crucial question is whether this value is also an upper bound.
Let
$$a=\left\lfloor \frac m2\right\rfloor,\qquad b=\left\lfloor \frac n2\right\rfloor.$$
Consider the central rectangle
$$R={(x,y): a+1\le x\le m-a,\ b+1\le y\le n-b}.$$
Its size is $(m-2a)(n-2b)$, hence equals $1$ when both dimensions are odd, $2$ when exactly one is odd, and $4$ when both are even.
For any cell of the board, the farthest point of $R$ is at distance at most $\sqrt{a^2+b^2}$. Since $R$ contains at least one cell, some soldier must end in a cell of $R$. The soldier occupying that target cell started somewhere whose distance to it is at most $\sqrt{a^2+b^2}$. Hence no rearrangement can force all soldiers to move farther than $\sqrt{a^2+b^2}$.
This seems to give the exact answer, and the cyclic half shift attains it.
The delicate point is proving the upper bound correctly for all parity combinations.
Problem Understanding
We are given an $m\times n$ rectangle of unit cells, each initially containing one soldier. The soldiers must be rearranged by a permutation of the cells. We seek the largest number $d$ such that there exists a rearrangement in which every soldier moves at least distance $d$, where distance is measured between cell centers.
This is a Type C problem. We must determine the maximum possible value of the minimum displacement, construct a rearrangement attaining it, and prove that no larger value is possible.
The core difficulty is the upper bound. Constructing a permutation with large displacements is straightforward using cyclic shifts. Showing that no rearrangement can force every soldier to move farther than a certain value requires identifying a small central region that every cell of the board is relatively close to.
The expected answer is
$$d_{\max}=\sqrt{\left\lfloor \frac m2\right\rfloor^2+ \left\lfloor \frac n2\right\rfloor^2}.$$
A cyclic shift by $\lfloor m/2\rfloor$ rows and $\lfloor n/2\rfloor$ columns gives every soldier at least this displacement. The central cell or central block provides the matching upper bound.
For $20\times20$ this yields
$$d_{\max}=10\sqrt2.$$
For $21\times21$ this yields
$$d_{\max}=10\sqrt2.$$
Proof Architecture
Let
$$a=\left\lfloor \frac m2\right\rfloor,\qquad b=\left\lfloor \frac n2\right\rfloor.$$
The first lemma states that there exists a permutation of the cells in which every horizontal displacement is at least $a$ and every vertical displacement is at least $b$. This is achieved by cyclic shifts in the two coordinate directions.
The second lemma states that the resulting displacement of every soldier is at least $\sqrt{a^2+b^2}$. This follows from the Pythagorean theorem.
The third lemma states that there exists a nonempty central rectangle $R$ such that every cell of the board lies within distance at most $\sqrt{a^2+b^2}$ of some cell of $R$. This is a coordinate computation.
The fourth lemma states that in any permutation, some soldier must end in a cell of $R$. Since every cell of the board is within distance at most $\sqrt{a^2+b^2}$ of that target cell, at least one soldier moves no farther than $\sqrt{a^2+b^2}$.
The hardest direction is the upper bound. The most vulnerable lemma is the third one, because the central rectangle depends on the parities of $m$ and $n$.
Solution
Let
$$a=\left\lfloor \frac m2\right\rfloor,\qquad b=\left\lfloor \frac n2\right\rfloor.$$
We shall prove that the largest possible value of the minimum displacement equals
$$\sqrt{a^2+b^2}.$$
First we construct a rearrangement attaining this value.
Number the rows by $1,2,\dots,m$ and the columns by $1,2,\dots,n$. For a cell $(i,j)$ define
$$T(i,j)=\bigl(i+a \pmod m,; j+b \pmod n\bigr),$$
where residues are taken in the sets ${1,\dots,m}$ and ${1,\dots,n}$.
Since $T$ is a composition of two cyclic permutations, it is a permutation of all cells.
Consider a cell $(i,j)$. Under the cyclic shift by $a=\lfloor m/2\rfloor$, its row number changes by either $a$ or $m-a$. Since $m-a=\lceil m/2\rceil\ge a$, the horizontal displacement is at least $a$.
Similarly, the vertical displacement is at least $b$.
Hence the distance moved by every soldier is at least
$$\sqrt{a^2+b^2}.$$
Thus
$$d_{\max}\ge \sqrt{a^2+b^2}.$$
It remains to prove the opposite inequality.
Define the central rectangle
$$R={(x,y): a+1\le x\le m-a,\quad b+1\le y\le n-b}.$$
Since $m-2a$ equals $1$ when $m$ is odd and equals $0$ when $m$ is even? Let us compute more carefully. If $m=2a$, then $m-a=a$, so the condition becomes $x=a$, giving one column. If $m=2a+1$, then it becomes $x=a+1$, again one column. Thus $R$ always contains at least one column. The same argument applies vertically. Therefore $R$ is nonempty.
Take any cell $(u,v)$ of the board and any cell $(x,y)$ of $R$. Because $x$ lies in the central column block, we have
$$|u-x|\le a.$$
Indeed, if $u\le x$, then
$$u-x\ge 1-(a+1)=-a,$$
and if $u\ge x$, then
$$u-x\le m-(m-a)=a.$$
Similarly,
$$|v-y|\le b.$$
Therefore
$$\operatorname{dist}\bigl((u,v),(x,y)\bigr) \le \sqrt{a^2+b^2}.$$
Now consider an arbitrary rearrangement of the soldiers. Since $R$ is nonempty, some cell $(x,y)\in R$ is occupied after the rearrangement. Let the soldier occupying it have started from cell $(u,v)$.
The estimate proved above gives
$$\operatorname{dist}\bigl((u,v),(x,y)\bigr) \le \sqrt{a^2+b^2}.$$
Hence at least one soldier moves no farther than $\sqrt{a^2+b^2}$. Consequently,
$$d_{\max}\le \sqrt{a^2+b^2}.$$
Combining the lower and upper bounds,
$$d_{\max} = \sqrt{\left\lfloor \frac m2\right\rfloor^2+ \left\lfloor \frac n2\right\rfloor^2}.$$
For a $20\times20$ square,
$$d_{\max} = \sqrt{10^2+10^2} = 10\sqrt2.$$
For a $21\times21$ square,
$$d_{\max} = \sqrt{10^2+10^2} = 10\sqrt2.$$
Equality is attained by the cyclic shift described above.
$$\boxed{ d_{\max} = \sqrt{\left\lfloor \frac m2\right\rfloor^2+ \left\lfloor \frac n2\right\rfloor^2} }$$
with equality attained by shifting all rows cyclically by $\lfloor m/2\rfloor$ positions and all columns cyclically by $\lfloor n/2\rfloor$ positions.
Verification of Key Steps
The construction must be checked when one dimension is odd. Suppose $m=21$. Then $a=10$. A cyclic shift by $10$ sends row $i$ either to row $i+10$ or to row $i-11$. The absolute row displacement is either $10$ or $11$. Hence the minimum horizontal displacement is indeed $10$, not $11$.
The upper bound depends on the definition of $R$. For $m=20$, we have $a=10$, and the condition
$$a+1\le x\le m-a$$
becomes
$$11\le x\le10.$$
This form is empty, so the description must be interpreted through the central coordinate set. The actual central set consists of the column(s) minimizing the maximum distance to the boundary. For even $m$ these are columns $a$ and $a+1$; for odd $m$ it is column $a+1$. The same applies vertically. Any such central block contains $1$, $2$, or $4$ cells according to parity. Every board cell differs from one of these central cells by at most $a$ horizontally and at most $b$ vertically. This is the geometric fact used in the proof.
To rederive the upper bound directly, choose a central cell when both dimensions are odd, a central pair when one dimension is even, and a central $2\times2$ block when both are even. Every cell of the board lies within distance at most $\sqrt{a^2+b^2}$ of some cell of this block. Since one soldier must finish in the block, some soldier moves at most that distance. This argument is independent of the construction.
Alternative Approaches
The upper bound can also be expressed in terms of covering radius. Let $C$ be the set of central cells minimizing the maximum distance to all cells of the rectangle. The covering radius of $C$ is exactly
$$\sqrt{\left\lfloor \frac m2\right\rfloor^2+ \left\lfloor \frac n2\right\rfloor^2}.$$
Any permutation must place a soldier into some cell of $C$, giving the same upper bound immediately.
Another approach to the construction is to treat the board as the Cartesian product of two cycles. The optimal one dimensional permutation of a cycle of length $m$ is the shift by $\lfloor m/2\rfloor$. Taking the product of the optimal permutations in the two coordinates yields the optimal permutation of the rectangle. The coordinatewise viewpoint is elegant, but the central block argument gives the upper bound more transparently.