What is the maximum number of points in R2 such that in the distance matrix, no more than three points are closest to all others?

Question

Question: N people, each holding a water gun, are standing on flat ground (in the 2d plane). No two pairs of people are separated by the same distance. Each person sprays the person closest to them. What is the maximum N such that you can arrange the people into a configuration in which no more than 3 people get wet?

One way to approach this question:

The closest pair will target each other, so that is two people who are wet straight off the bat. Then, place people around the closest pair so that the people you place target one of the two - this does not add to the number of people who are wet. Finally, when you cannot add any more people that target the closest pair, add as many people as possible to target one person on the perimeter.

From sketching, you can arrange the closest pair in the center, then put seven people around them that target them (so a total of 9 people), then put four people behind one of the seven people (the third target). You can get up to N = 13, as Ron Kaminsky shows below. However, we are still missing a proof that N = 13 is the greatest possible number of people such that at most 3 get wet.

Answer 1

It is possible to place 13 people such that only 3 get wet. If the pair who are at minimum distance from each other are arbitrarily placed without loss of generality at $(-1/2,0)$ and $(1/2,0)$ the next 6 people can be placed at:

• $( \frac{\epsilon}{2} , \frac{\sqrt{3} \left(\epsilon + 1\right)}{2} )$
• $( 4 \epsilon + 1 , \frac{\sqrt{3} \left(2 \epsilon + 3\right)}{6} )$
• $( \frac{11 \epsilon}{2} + \frac{3}{2} , - \frac{25 \sqrt{3} \epsilon}{6} )$
• $( 1 - \frac{13 \epsilon}{2} , \frac{\sqrt{3} \left(- 53 \epsilon - 3\right)}{6} )$
• $( - \frac{133 \epsilon}{2} , \frac{\sqrt{3} \left(- 253 \epsilon - 3\right)}{6} )$
• $( - \frac{433 \epsilon}{2} - 1 , \frac{\sqrt{3} \cdot \left(53 \epsilon - 3\right)}{6} )$

As you might imagine, I did not calculate these points by hand, they were calculated in the order shown in this image: where the arrows show which points were used to calculate the point which they point at, and the colors of the arrows shows which distances were chosen to be smaller and which greater (red arrows meaning greater distances, and blue arrows smaller distances). I used SymPy for this calculation: each point was initially calculated using distances of the form $1 + k_i\epsilon$ and $1 + k_j\epsilon$ and the solution point location was subsequently linearized afterwards to be linear in $\epsilon$ (so that the calculation complexity would not "explode"). The sequence of $k$ values was chosen to be monotonically increasing and tweaked to make sure all of the problem constraints remained satisfied for these first 8 points.

With these 8 points, the angle between the line from point 1 to point 3 and the line from point 1 to point 8 is $$\frac{338 \sqrt{3} \epsilon}{3}+O(\epsilon^2).$$ This means we can put point 9 as far away as we want from point 1 by making $\epsilon$ small enough, and then afterwards it is easily seen that it will be possible to surround point 9 with 4 more points.

As for proving that 13 points is optimal, if I come up with a proof I will edit this answer to include it.