For a pair and of points on the coordinate plane, let . We call a pair of (unordered) points [i]harmonic[/i] if . Determine the maximum number of harmonic pairs among 100 points in the plane.
Solution
Given a set of 100 points in the plane, we want to determine the maximum number of harmonic pairs, where a pair of points is considered harmonic if and .
To solve this problem, we can transform the distance function to make it easier to handle. By rotating the plane by 45 degrees, we change the coordinates of a point to . Under this transformation, the Manhattan distance becomes .
We claim that the maximum number of harmonic pairs is . To achieve this bound, we can place 25 points each in small neighborhoods around the four points .
To prove that this is the maximum number, we construct a graph with 100 vertices, where two vertices are connected if the corresponding points are harmonic. We need to show that has no (complete graph on 5 vertices).
Claim: has no .
Proof: Consider the following two facts:
1. If a coloring of the edges of with two colors does not produce a monochromatic triangle, then it must have a monochromatic cycle of length 5.
2. It is impossible to find three real numbers such that all points are mutually harmonic.
For each edge in , color the edge red if , or blue otherwise. Suppose, for contradiction, that there is a in with points . By fact 2, it has no monochromatic triangle, so by fact 1, it has a monochromatic cycle of length 5. Without loss of generality, assume the cycle is red, and let it be .
If , we have a contradiction because the extreme points would not be harmonic. Therefore, . Assume , so . Thus, .
Color the vertices with ordinate in black and those in white. Traversing changes the color of the interval each time, implying the odd cycle is bipartite, which is a contradiction.
By Turan's theorem, the strictest bound possible for the number of edges in without a is .
The answer is .