Maths Olympiad Prep

Library / /4 of 4

Geometry Difficulty 6.8 National olympiad Prove it Romania

A diameter of a finite planar set is any line segment of maximal Euclidean length having both end points in that set. A lattice point in the Cartesian plane is one whose coordinates are both integral. Given an integer n2n \ge 2, prove that a set of nn lattice points in the plane has at most n1n-1 diameters.

Solution

Consider the diameter graph Γ\Gamma on nn 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=2n=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 AA of degree at least 3, proceed along the standard lines in the continuous realm: The diameters emanating from AA all lie within the angle formed by two diameters ABAB and ACAC, where BAC60\angle BAC \le 60^\circ. Letting AXAX be a third diameter from AA, it then follows that XX is the desired vertex of degree 1, as a hypothetical diameter XYXY, YAY \ne A, cannot intersect both ABAB and ACAC.

It is a fact that Γ\Gamma has at most nn edges. Suppose, if possible, Γ\Gamma has nn edges and is 2-regular (all vertices have degree 2). As every two diameters intersect, this is possible if and only if nn is odd, in which case Γ\Gamma is a star-shaped self-crossing nn-cycle A1A2A3AnA_1A_2A_3\dots A_n whose polygonal convex hull reads around the boundary A1A3A5AnA2A4A6An1A_1A_3A_5\dots A_nA_2A_4A_6\dots A_{n-1}. Write AiAi+1=dA_iA_{i+1} = d, i=1,2,,ni = 1, 2, \dots, n (indices are reduced modulo nn), so (xi+1xi)2+(yi+1yi)2=d2(x_{i+1} - x_i)^2 + (y_{i+1} - y_i)^2 = d^2, i=1,2,,ni = 1, 2, \dots, n; clearly, d2d^2 is an integer. Without loss of generality, assume the configuration is the smallest possible.

By minimality, the 2n2n differences xi+1xix_{i+1} - x_i and yi+1yiy_{i+1} - y_i cannot all be even — otherwise, the midpoints of all line segments AiAjA_iA_j would again be lattice points, and a homothety of factor 12\frac{1}{2} from some AiA_i would yield a smaller configuration. Hence one of the index sets I={i:xi+1xi1(mod2)}I = \{i: x_{i+1} - x_i \equiv 1 \pmod 2\} and J={i:yi+1yi1(mod2)}J = \{i: y_{i+1} - y_i \equiv 1 \pmod 2\}, say, II, is non-empty. Hence again, d21(mod4)d^2 \equiv 1 \pmod 4, so for no index ii are xi+1xix_{i+1} - x_i and yi+1yiy_{i+1} - y_i both even. Consequently, the union IJI \cup J exhausts all nn indices.

Rule out the case d21(mod4)d^2 \equiv 1 \pmod 4 as follows: If d21(mod4)d^2 \equiv 1 \pmod 4, then II and JJ are disjoint. By the preceding, IJI \cup J covers all nn indices, so I+J=n|I| + |J| = n which is odd. On the other hand, i=1n(xi+1xi)=0\sum_{i=1}^n (x_{i+1} - x_i) = 0 implies that I|I| is even; similarly, i=1n(yi+1yi)=0\sum_{i=1}^n (y_{i+1} - y_i) = 0 implies that J|J| is even, and hence so is I+J|I| + |J|, contradicting the fact that I+J=n|I| + |J| = n is odd.

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

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

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.