Maths Olympiad Prep

Library / /25 of 45

Combinatorics Difficulty 8.6 Shortlist Prove it United States

For a pair A=(x1,y1)A = (x_1, y_1) and B=(x2,y2)B = (x_2, y_2) of points on the coordinate plane, let d(A,B)=x1x2+y1y2d(A, B) = |x_1 - x_2| + |y_1 - y_2|. We call a pair (A,B)(A, B) of (unordered) points harmonic if 1<d(A,B)21 < d(A, B) \le 2. Determine the maximum number of harmonic pairs among 100 points on the plane.

(This problem was suggested by Zuming Feng and Oleg Golberg.)

Solution

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 (x1,y1)(x_1, y_1) precedes (x2,y2)(x_2, y_2), denoted by (x1,y1)(x2,y2)(x_1, y_1) \prec (x_2, y_2), if and only if x1x2x_1 \le x_2 and y1y2y_1 \le y_2. 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 A,B,CA, B, C in the order of their xx-coordinates form a chain or an antichain under the ordering we defined. Then d(A,B)+d(B,C)=d(A,C)d(A, B) + d(B, C) = d(A, C) and all pairs of A,B,CA, B, C 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 mn+1mn + 1 real numbers either contains a non-increasing sequence of length m+1m+1 or a non-decreasing sequence of length n+1n+1.)

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
(1002)4(252)=3750=6252 \binom{100}{2} - 4 \cdot \binom{25}{2} = 3750 = 6 \cdot 25^2
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 A(0,1)A(0,1), B(1,0)B(1,0), C(0,1)C(0,-1), D(1,0)D(-1,0). On each of the sides AB,BC,CD,DAAB, BC, CD, DA choose 25 points close to A,B,C,DA, B, C, D, respectively. Among the chosen 100 points, any pair of two points lying on different sides of the square is good. Therefore, 6252=37506 \cdot 25^2 = 3750 is the maximum number of good pairs among 100 points of the plane.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.