Kvant Math Problem 1265

Verified: no
Verdicts: FAIL + FAIL
Solve time: 10m49s
Source on kvant.digital

Problem

Prove that among the 21 pairwise distances between 7 distinct points in the plane, the same number can occur no more than 12 times.
What is the maximum number of times the same number can occur among the 15 pairwise distances between 6 distinct points in the plane?

N. M. Sedrakyan

7 points

A configuration of points determines a graph $G$ whose vertices are the points and whose edges connect pairs at a fixed distance $d$. Let $E$ be the number of such edges.

Choose a vertex $A$ of maximum degree $k$. Since there are only six other points, $k \le 6$. Let $N(A)$ be the set of neighbors of $A$, so $|N(A)|=k$.

Every vertex in $N(A)$ lies on the circle centered at $A$ with radius $d$. For two distinct points $B,C \in N(A)$, the condition $BC=d$ is equivalent to $\triangle ABC$ being equilateral, hence the central angle condition

$BC=d \iff \angle BAC = 60^\circ.$

Thus, if we represent points of $N(A)$ by their polar angles around $A$, two vertices are adjacent exactly when their angular difference is $60^\circ$ or $300^\circ$.

Each vertex therefore has at most two neighbors inside $N(A)$, corresponding to angles $\pm 60^\circ$. The induced graph on $N(A)$ has maximum degree $2$, so it is a disjoint union of paths and cycles.

A cycle in this graph would require repeatedly stepping by $\pm 60^\circ$ around the circle and returning to the starting point. This forces a total angular turn of $360^\circ$, hence cycle length $6$. Therefore cycles exist only when $k=6$, and otherwise the graph on $N(A)$ is a forest of paths.

If $k=6$, the maximum occurs when $N(A)$ forms a 6-cycle, which has exactly $6$ edges. If $k \le 5$, the induced graph on $N(A)$ is acyclic with maximum degree $2$, hence it has at most $k-1$ edges.

The total number of edges is

$E = k + E(N(A)).$

If $k=6$, then $E \le 6 + 6 = 12$.

If $k \le 5$, then

$E \le k + (k-1) = 2k - 1 \le 9.$

The bound $12$ is achieved by a configuration consisting of a regular hexagon together with its center, where the center is connected to all six vertices and the hexagon edges form a 6-cycle of unit distances.

Thus, among 7 points, the same distance can occur at most $12$ times.

6 points

Let $A$ be a vertex of maximum degree $k$. Since there are five other points, $k \le 5$. As in the previous case,

$E = k + E(N(A)).$

The induced graph on $N(A)$ again has maximum degree at most $2$, hence it is a disjoint union of paths and possibly cycles. A cycle would require stepping repeatedly by $60^\circ$ and closing up, which forces length $6$. Since $|N(A)| \le 5$, no cycle is possible, so the graph on $N(A)$ is a disjoint union of paths.

A path on $k$ vertices has exactly $k-1$ edges, hence

$E(N(A)) \le k-1.$

Therefore,

$E \le k + (k-1) = 2k - 1 \le 9.$

To realize $9$, take a configuration where $k=5$ and the five neighbors of $A$ form a path of length $4$ in the unit-distance relation on the circle. This is achieved by placing five points on a circle centered at $A$ so that consecutive points differ by $60^\circ$ except one missing link to avoid closure. Then $E(N(A))=4$ and all five vertices are connected to $A$, giving

$E = 5 + 4 = 9.$

No configuration on six points can exceed this value because any attempt to increase $E(N(A))$ beyond $k-1$ would require a 6-cycle structure, which is impossible with only five vertices.

Thus, among 6 points, the same distance can occur at most $9$ times.

Final answers

For 7 distinct points in the plane, the same distance can occur at most $12$ times.

For 6 distinct points in the plane, the same distance can occur at most $9$ times.