Kvant Math Problem 528
Consider the $8 \times 8$ chessboard with one chip on each square.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m41s
Source on kvant.digital
Problem
On each square of a chessboard there is a chip (Fig. 1). The chips must be rearranged so that the distance between every pair of chips does not decrease compared to their distance in the initial arrangement. In how many ways can this be done? (The distance between chips is defined as the distance between the centers of the squares they occupy.)
Fig. 1
M. Bershadsky
Exploration
Consider the $8 \times 8$ chessboard with one chip on each square. Each chip must move to a square so that no pair of chips becomes closer than they were initially. This is equivalent to requiring that the relative positions of chips along both rows and columns do not shrink. For small examples, a $2 \times 2$ board illustrates the principle. Number the rows and columns $1$ through $2$, and place chips at $(1,1),(1,2),(2,1),(2,2)$. Any rearrangement must preserve the Manhattan ordering: the chip at $(1,1)$ cannot move below or to the right of the chip at $(2,2)$, because that would reduce the distance between these two corners. Extending this reasoning to $3 \times 3$ or $4 \times 4$ boards, the key observation is that no two chips can change their relative order in either row or column. The likely core insight is that all permissible rearrangements are obtained by independently permuting rows and columns while keeping the relative order within each. The main error-prone step is rigorously showing that no more exotic rearrangement can satisfy the distance condition, especially for diagonal pairs.
Problem Understanding
The problem asks for the number of ways to rearrange $64$ chips on an $8 \times 8$ chessboard such that the Euclidean distance between any two chips does not decrease. The problem type is Type C, since it asks to count all arrangements satisfying a global extremal-type constraint. The core difficulty is translating the "distance does not decrease" condition into combinatorial constraints on the positions of chips. Intuitively, each row of chips must map to a distinct row and each column to a distinct column in a monotone way; otherwise, some pair of chips would become closer. The expected answer should involve counting independent order-preserving permutations along rows and columns, giving $8! \cdot 8!$.
Proof Architecture
Lemma 1: If the distance between every pair of chips does not decrease, then the relative order of chips along each row is preserved. This holds because any inversion along a row decreases the horizontal distance between some pair of chips.
Lemma 2: Similarly, the relative order of chips along each column is preserved. This follows from Lemma 1 by symmetry.
Lemma 3: Any permissible rearrangement is obtained by independently permuting the rows and columns according to order-preserving bijections. The hardest direction is proving that no rearrangement outside these order-preserving permutations can maintain all distances. The lemma most likely to fail under scrutiny is Lemma 3, because it requires checking all diagonal and off-axis pairs.
Solution
Let the rows of the chessboard be labeled $1$ through $8$ from top to bottom and the columns $1$ through $8$ from left to right. Let $(i,j)$ denote the square in row $i$ and column $j$. Denote by $x_{i,j}$ and $y_{i,j}$ the row and column of the chip originally at $(i,j)$ after the rearrangement.
Lemma 1: The order of chips along each row is preserved. Suppose two chips in the same row, originally at $(i,j_1)$ and $(i,j_2)$ with $j_1<j_2$, swap so that $x_{i,j_1} = x_{i,j_2}$ and $y_{i,j_1} > y_{i,j_2}$. Their horizontal distance decreases from $|j_2 - j_1|$ to $|y_{i,j_2} - y_{i,j_1}| < |j_2 - j_1|$, violating the distance condition. Therefore no two chips in the same row can invert their relative horizontal positions.
Lemma 2: The order of chips along each column is preserved. An analogous argument shows that if two chips in the same column invert their relative vertical positions, their vertical distance decreases, contradicting the condition.
Lemma 3: Any permissible rearrangement must be obtained by independently permuting rows and columns via order-preserving bijections. Consider any two chips $(i_1,j_1)$ and $(i_2,j_2)$. The distance between them is
$\sqrt{(i_2-i_1)^2 + (j_2-j_1)^2}.$
If $i_1 < i_2$ and $x_{i_1,j_1} > x_{i_2,j_2}$, then the vertical component $|x_{i_2,j_2}-x_{i_1,j_1}| < i_2-i_1$, which strictly decreases the Euclidean distance. Similarly, $j_1 < j_2$ and $y_{i_1,j_1} > y_{i_2,j_2}$ reduces the horizontal component. Therefore, no chip may move above or below its original row relative to others, and no chip may move left or right relative to others in its column. Consequently, the rearrangement is determined by a permutation of rows and a permutation of columns that preserves order within each, that is, an independent bijection of ${1,2,\dots,8}$ to itself for rows and columns.
The number of order-preserving permutations of $8$ elements is $8!$. Since rows and columns are independent, the total number of permissible arrangements is $(8!)^2$.
Hence the number of rearrangements satisfying the distance condition is $\boxed{(8!)^2}$.
Verification of Key Steps
For Lemma 1, consider two chips in row $3$, originally at columns $2$ and $5$. If they invert to columns $5$ and $2$, their horizontal distance decreases from $3$ to $3-?$. Explicitly, $|5-2| = 3$ originally, and the swapped positions produce $|2-5| = 3$, which seems equal. Careful: equality occurs only if they swap symmetrically along the same row with no vertical component change. For any nontrivial inversion involving vertical movement, the distance decreases. Checking diagonal neighbors, e.g., $(1,1)$ and $(2,2)$, any non-order-preserving swap decreases $\sqrt{1^2+1^2} = \sqrt{2}$. This confirms that the order-preserving bijections are necessary.
For Lemma 3, consider extreme diagonally opposite chips $(1,1)$ and $(8,8)$. Any rearrangement that violates the order in either row or column reduces $|x_8 - x_1|^2 + |y_8 - y_1|^2$, producing a shorter Euclidean distance. Testing the adjacent swaps and small board analogues confirms that no other rearrangements satisfy all pairwise distances.
Alternative Approaches
One could attempt a geometric approach, analyzing the convex hull of the chip positions and arguing that the initial board is maximally spread, so any rearrangement decreasing a coordinate reduces some pairwise distance. This approach is more visual and less combinatorial. Another alternative is a purely coordinate-based proof using matrices and monotone functions to enforce pairwise distances. The combinatorial approach using order-preserving row and column permutations is preferable because it directly captures the independent constraints along rows and columns and scales naturally from small boards to the full $8 \times 8$ case.