For a pair and of points on the coordinate plane, let . We call a pair of (unordered) points harmonic if . Determine the maximum number of harmonic pairs among 100 points on the plane.
(This problem was suggested by Zuming Feng and Oleg Golberg.)
For a pair and of points on the coordinate plane, let . We call a pair of (unordered) points harmonic if . Determine the maximum number of harmonic pairs among 100 points on the plane.
(This problem was suggested by Zuming Feng and Oleg Golberg.)
We claim that there do not exist five points on the plane such that they are pairwise harmonic. Suppose such a set of five points exists. We say precedes , denoted by , if and only if and . This defines a partial order on the set. Because it has five elements, it has either a chain or an antichain of three elements. Let in the order of their -coordinates form a chain or an antichain under the ordering we defined. Then and all pairs of cannot be good. (This may also be proved by invoking the pigeon-hole principle to prove the more general result of Erdős-Szekeres: a sequence of real numbers either contains a non-increasing sequence of length or a non-decreasing sequence of length .)
Consider the graph with vertices at 100 points of the plane and edges connecting good pairs. Then due to the above statement the graph has no complete subgraph with 5 vertices. By Turan's theorem it has at most
edges. Therefore, every set of 100 points of the plane has at most 3750 harmonic pairs.
To complete our proof, we show that the bound 3750 can be attained. Consider the square with vertices at , , , . On each of the sides choose 25 points close to , respectively. Among the chosen 100 points, any pair of two points lying on different sides of the square is good. Therefore, is the maximum number of good pairs among 100 points of the plane.