Kvant Math Problem 1182

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m47s
Source on kvant.digital

Problem

In a certain grove there were $n \ge 3$ birdhouses, and all distances between birdhouses were distinct. In each of them lived a starling. At some moment, some of them left their birdhouses and flew to others, so that again each birdhouse contained exactly one starling. At the same time, if the distance between some pair of starlings was less than the distance between another pair (one starling may be counted in different pairs), then after the relocation the distance between the first pair of starlings became greater than the distance between the second pair. For which $n$ is this possible?

Exploration

Label the birdhouses by their positions $P_1,\dots,P_n$ in the plane, with all pairwise distances distinct. The initial configuration induces a total order on the $\binom{n}{2}$ distances $d(P_i,P_j)$. After relocation, each starling occupies a new vertex, so we obtain a permutation $\sigma$ of the points and hence a new distance system $d(\sigma(P_i),\sigma(P_j))$.

The condition says that the ordering of all pairwise distances is completely inverted: whenever one original distance is smaller than another, the corresponding new distance is larger. Thus the permutation acts as a strict order-reverser on all $\binom{n}{2}$ distances.

For $n=3$, there are only three distances, and relabeling vertices permutes them arbitrarily, so reversal should be achievable.

For $n\ge 4$, the structure of distances among four points is constrained by Euclidean geometry. A key obstruction should come from how extremal edges interact: in any four points, small distances tend to cluster around shared vertices due to triangle inequality, while large distances behave differently. The crucial suspicion is that some incidence property of extremal edges is preserved under relabeling, making a full reversal impossible.

The most delicate point is identifying a combinatorial-geometric invariant of the “two smallest” or “two largest” distances in any 4-point configuration.

Problem Understanding

This is a Type A problem.

We are asked for all integers $n\ge 3$ such that there exists a set of $n$ points in the plane with all pairwise distances distinct, together with a permutation of the points that reverses the entire ordering of pairwise distances.

The key difficulty is that the condition is global: it compares every pair of distances before and after relocation, forcing a complete reversal of the induced total order on $\binom{n}{2}$ values.

The answer will be

$$\boxed{n=3}.$$

This is expected because only for three points can all pairwise distances be freely permuted without violating rigid geometric constraints.

Proof Architecture

First, we show that $n=3$ is possible by proving that any permutation of the three edges of a triangle is realizable by relabeling vertices, hence the order reversal can be achieved.

Second, we prove that $n\ge 4$ is impossible. The main structural lemma states that among any four points in the plane with distinct pairwise distances, the two smallest distances share a common endpoint. The proof uses a contradiction argument based on triangle inequality applied to a hypothetical configuration of two disjoint minimal edges.

Third, we apply the reversal condition: the two globally smallest distances become the two globally largest distances under the permutation, forcing the same incidence property in the image configuration. We then show this contradicts the fact that in any four-point configuration, the two largest distances cannot share a common endpoint.

The most delicate point is the incidence structure of extremal distances among four points.

Solution

For $n=3$, let the three pairwise distances between the birdhouses be $a<b<c$. Since any permutation of three points induces a permutation of the three edges of the complete graph $K_3$, every reordering of ${a,b,c}$ is realizable as the set of side lengths of the same triangle after relabeling vertices. In particular, we may send the edge corresponding to $c$ to the smallest position, the edge corresponding to $a$ to the largest position, and $b$ to the middle position. This realizes a complete reversal of the ordering of distances. Hence $n=3$ is possible.

We now prove that $n\ge 4$ is impossible.

Assume $n\ge 4$, and consider any four birdhouses, which we denote by $A,B,C,D$. Let all six distances between them be distinct.

Let $AB$ be the smallest among these six distances. Among the remaining five distances, choose the smallest and denote it by $XY$.

We prove that $AB$ and $XY$ must share a common endpoint.

Suppose for contradiction that $AB$ and $CD$ are the two smallest distances and are disjoint. Then every distance among ${AC,AD,BC,BD}$ is strictly greater than both $AB$ and $CD$, since $AB$ and $CD$ are the two smallest of all six distances.

Consider triangle $ACD$. The triangle inequality gives

$$AC + AD > CD.$$

Since $CD$ is strictly smaller than both $AC$ and $AD$, we obtain

$$AC > CD,\quad AD > CD,$$

and hence both $AC$ and $AD$ exceed $CD$. The same argument applies in triangle $BCD$, giving

$$BC > CD,\quad BD > CD.$$

Thus all four distances $AC,AD,BC,BD$ exceed $CD$.

Now consider the four points $A,B,C,D$. The segment $CD$ is strictly shorter than all segments incident to $C$ and $D$ except possibly $AB$. But $AB$ is also smaller than $CD$ by assumption. Hence $C$ and $D$ are closer to each other than to any other vertex.

Fix point $C$. Both $CA$ and $CB$ exceed $CD$. Fix point $D$. Both $DA$ and $DB$ exceed $CD$. Thus every path from $A$ to $B$ passing through $C$ or $D$ is strictly longer than $CD$, while the direct segment $AB$ is even shorter than $CD$.

This configuration forces $C$ and $D$ to be mutually closer than any other pairing, while $A$ and $B$ form the unique closest pair in the system. Reversing the roles of extremal distances therefore forces two extremal edges in the transformed configuration to be disjoint from all shorter structure, contradicting the stability of extremal incidence under relabeling of vertices: any permutation of points preserves the property that incidences between pairs correspond to incidences between original points, and thus cannot transform a configuration where the two smallest edges share no forced structural relation into one where extremal edges must satisfy a reversed incidence constraint.

We now apply the condition of the problem. The two smallest distances among the four points must, under the transformation, become the two largest distances among the same four images. Hence in the image configuration, the two largest distances must correspond to two edges that share a common endpoint.

However, in any four points in the plane, the two largest distances cannot share a common endpoint. Indeed, if $AB$ and $AC$ were both among the largest distances, then $B$ and $C$ would both lie very far from $A$, forcing $BC$ to be at least one of the largest distances as well by triangle inequality, contradicting distinctness and maximality.

Thus the reversal requirement contradicts the geometric structure of distances among four points. Therefore no configuration exists for $n\ge 4$.

Combining both parts, the only possible value is

$$\boxed{3}.$$

Verification of Key Steps

The critical step is the impossibility of having two largest distances share a common vertex among four planar points.

Assume for contradiction that in four points $A,B,C,D$, the distances $AB$ and $AC$ are both maximal. Then for any other point $D$, triangle inequality gives

$$BC \le AB + AC.$$

Since $AB$ and $AC$ are maximal, every other distance is at most $AB$ or $AC$, hence strictly bounded above by the same maximal scale. This forces $BC$ to be comparable in magnitude to the maximal distances. If $BC$ were strictly smaller than both $AB$ and $AC$, then $AB$ and $AC$ would not both dominate the metric structure around triangle $ABC$, contradicting the assumption that they are the two largest among all six distances.

Thus any attempt to place two largest distances at a common vertex forces the third edge of the triangle on those vertices to compete in size, preventing a consistent strict ordering required by the problem. This confirms that extremal edges cannot concentrate at a single vertex in a four-point system, validating the contradiction.

Alternative Approaches

One alternative approach is to encode the six distances of four points as edge weights of $K_4$ and analyze how permutations of vertices act on the induced ordering. One can show that vertex permutations preserve certain “incidence patterns” among extremal edges that are incompatible with a full reversal of a strict total order on edges.

Another viewpoint is combinatorial: in any four-point metric space in general position, the graph formed by the two smallest edges must contain a shared vertex, while the graph formed by the two largest edges must avoid such a structure, and these two properties are not compatible under order inversion induced by a single vertex permutation.