Twentieth IMAR Mathematical Competition

Consider the diameter graph $\Gamma$ on $n$ pairwise distinct lattice points in the plane, i.e., the geometric graph on those points, whose edges are the diameters of the configuration. We will prove that $\Gamma$ has at least one vertex of degree 1. Removal of one such and the edge it is incident to, allows then an inductive approach — the base case, $n=2$, is clear. As expected, the argument hinges on the fact that every two diameters intersect: Either they both emanate from the same point or they both cross at some interior point. If $\Gamma$ has a vertex $A$ of degree at least 3, proceed along the standard lines in the continuous realm: The diameters emanating from $A$ all lie within the angle formed by two diameters $AB$ and $AC$, where $\angle BAC\le 60^{\circ }$. Letting $AX$ be a third diameter from $A$, it then follows that $X$ is the desired vertex of degree 1, as a hypothetical diameter $XY$, $Y\ne A$, cannot intersect both $AB$ and $AC$.

It is a fact that $\Gamma$ has at most $n$ edges. Suppose, if possible, $\Gamma$ has $n$ edges and is 2-regular (all vertices have degree 2). As every two diameters intersect, this is possible if and only if $n$ is odd, in which case $\Gamma$ is a star-shaped self-crossing $n$-cycle $A_1{A}_2{A}_3\dots A_n$ whose polygonal convex hull reads around the boundary $A_1{A}_3{A}_5\dots A_n{A}_2{A}_4{A}_6\dots A_{n-1}$. Write $A_i{A}_{i+1}=d$, $i=1,2,\dots ,n$ (indices are reduced modulo $n$), so $(x_{i+1}-x_i{)}^2+(y_{i+1}-y_i{)}^2=d^2$, $i=1,2,\dots ,n$; clearly, $d^2$ is an integer. Without loss of generality, assume the configuration is the smallest possible.

By minimality, the $2n$ differences $x_{i+1}-x_i$ and $y_{i+1}-y_i$ cannot all be even — otherwise, the midpoints of all line segments $A_i{A}_j$ would again be lattice points, and a homothety of factor $\frac{1}{2}$ from some $A_i$ would yield a smaller configuration. Hence one of the index sets $I=\{i:x_{i+1}-x_i\equiv 1(\mathrm{mod}2)\}$ and $J=\{i:y_{i+1}-y_i\equiv 1(\mathrm{mod}2)\}$, say, $I$, is non-empty. Hence again, $d^2\equiv 1(\mathrm{mod}4)$, so for no index $i$ are $x_{i+1}-x_i$ and $y_{i+1}-y_i$ both even. Consequently, the union $I\cup J$ exhausts all $n$ indices.

Rule out the case $d^2\equiv 1(\mathrm{mod}4)$ as follows: If $d^2\equiv 1(\mathrm{mod}4)$, then $I$ and $J$ are disjoint. By the preceding, $I\cup J$ covers all $n$ indices, so $|I|+|J|=n$ which is odd. On the other hand, ${\sum }_{i=1}^n(x_{i+1}-x_i)=0$ implies that $|I|$ is even; similarly, ${\sum }_{i=1}^n(y_{i+1}-y_i)=0$ implies that $|J|$ is even, and hence so is $|I|+|J|$, contradicting the fact that $|I|+|J|=n$ is odd.

Finally, rule out the case $d^2\equiv 2(\mathrm{mod}4)$: If $d^2\equiv 2(\mathrm{mod}4)$, then $I=J$, so $|I|=n$, contradicting again the parity of $|I|$ established above. Consequently, the diameter graph $\Gamma$ is not 2-regular, as desired.

Remark. The required diameter upper bound is always achieved, so $n-1$ is, in fact, the maximal number of diameters a planar configuration of $n$ lattice points may have. To prove it, consider the Diophantine equation $x^2+y^2=5^N$ $(\ast )$ where $N$ is a non-negative integer. By Jacobi's two-square theorem, the number of pairwise distinct solutions of the Diophantine equation $x^2+y^2=M$, where $M$ is a positive integer, is equal to four times the excess of the number of divisors of $M$ that are congruent to 1 modulo 4 over those congruent to 3 modulo 4. In the case at hand, $(\ast )$ has exactly $4(N+1)$ pairwise distinct solutions. This can equally well be established directly, by noticing that $1\pm 2\sqrt{-1}$ are Gaussian primes, and $\frac{1}{\pi }\arg (1+2\sqrt{-1})$ is irrational; explicitly, the solutions are $u(1+2\sqrt{-1}{)}^k(1-2\sqrt{-1}{)}^{N-k}$, where $u=\pm 1$ or $\pm \sqrt{-1}$, and $k=0,1,\dots ,N$. Exactly $N+1$ of these solutions lie in the first quadrant, $x>0$ and $y\ge 0$; and since 5 is odd, exactly $\lfloor \frac{1}{2}(N+1)\rfloor$ of these, say, $(x_i,y_i)$, $i=1,2,\dots ,\lfloor \frac{1}{2}(N+1)\rfloor$, satisfy $x>y\ge 0$. The $\lfloor \frac{1}{2}(N+1)\rfloor$ lattice points $(x_i,y_i)$ are all exactly $5^{N/2}$ away from the origin, and every two are (strictly) less than $5^{N/2}$ distance apart. Consequently, the origin and the $(x_i,y_i)$ form a planar configuration of $\lfloor \frac{1}{2}(N+3)\rfloor$ lattice points with exactly $\lfloor \frac{1}{2}(N+1)\rfloor$ diameters of length $5^{N/2}$ each. Setting $N=2n-3$ completes the argument.

We end by describing a related configuration. Consider an even integer $N\ge n$. The $(x_i,y_i)$ above and the $(5^{N/2}-x_i,y_i)$ form a configuration of $N+2$ lattice points with exactly $N+1$ diameters: $\frac{1}{2}N+1$ of these join $(0,0)$ to each $(x_i,y_i)$, and another $\frac{1}{2}N$ join $(5^{N/2},0)$ to each $(5^{N/2}-x_i,y_i)$ with a positive $y_i$. Deletion of any $N-n+2$ points with both coordinates positive then settles the case.