Each Point has Three Closest Neighbors
I met Alexander Karabegov during the All-Soviet Math Olympiad in Yerevan. He was one year older than me. By then, when I was still competing in 1976, he was already a freshman at Moscow State University. He proposed the following two related puzzles for the Moscow Olympiad, which I had to solve.
Puzzle 1. You are given a finite number of points on a plane. Prove that there exists a point with not more than 3 closest neighbors.
Just in case, by closest neighbors I mean all points at the minimal distance from a given point. I am sure I solved both puzzles at the time. I leave the solution to the first one to the reader.
Puzzle 2. Can you place a finite number of points on the plane in such a way that each point has exactly 3 closest neighbors?
The last problem has an elegant solution with 24 points chosen from a triangular grid. The story continued almost 40 years later, when Alexander sent me an image (below) of such a configuration with 16 points. He conjectures that this is the minimal configuration.
Karabegov’s Conjecture. Any finite planar point configuration in which every point has exactly 3 closest neighbors must contain at least 16 points.
Can you prove it?
Initially, I didn’t want to give the 24-points solution, but the image above is a big hint, so here you go.
Both constructions reveal the same underlying pattern. The constructions consist of rhombuses formed by two equilateral triangles, and the rhombuses are connected to each other. The 24-point construction consists of 6 rhombuses, while the 16-point construction consists of 4 rhombuses. What will happen if we try the construction with 3 rhombuses? The image below shows such a configuration, which now has extra edges with the shortest distance. We now see 3 points with more than three closest neighbors each, violating the condition. So the conjecture doesn’t break.
So far, every smaller attempt failed — can you prove that 16 is minimal?
Share:
Leave a comment