# Pigeonhole Principle Points in a Triangle

Suppose we have an equilateral triangle with side length $1$. In this equilateral triangle, we place $8$ points either on the boundary or inside the triangle itself. Then what is the maximum possible value for the shortest distance between any two of the points?

An interesting conjecture of Paul Erdos and Norman Oler states that, if $n=\frac{k(k+1)}{2}$ is a triangular number, then the optimal number for $n-1$ points is the same as for $n$ points; this sheds some light on that the answers for $n=10$ and for $n=9$ are the same (and how to find them) but this can hardly help you to find the optimum for $n=8$.

-
By the way, Andy, if this is homework, I doubt your professor would make you prove bounds as computationally time-consuming as this one! Was the original question something more like "Prove that the minimum distance is less than X"? – Lopsy Jan 29 '12 at 22:45

I think this is answered by the diagram for $n=8$ at this link.

-
right but this question deals with points in an equilateral triangle, not circles... does the proof for the circles yield a solution for points? The way I see it, we could move the radi of the circles towards the boundaries, and it would seem like we would have a farther distance between the points. I don't see a trivial connection between points and circles, but perhaps I'm wrong – Andy Jan 29 '12 at 22:32
Look at the points in the triangle which can be centers of circles with a given radius. Only points sufficiently far from each side have this property. In fact, the set of points satisfying this is shaped like a smaller equilateral triangle. Now, for the purposes of your question, consider the 8 points as the centers of the 8 circles, and put them inside the previously described smaller triangle. That transforms the circle problem into the point problem. – Lopsy Jan 29 '12 at 22:38

If you accept the link pointed out by Gerry Myerson then you can add some lines to get this diagram

Your equilateral triangle is the red one; in the diagram, you have to subtract $\sqrt{3}$ twice from the edge of the black equilateral triangle, while the centres of touching circles are $2$ apart. So to get the answer to your question for an equilateral triangle with side length 1 you need

$$\dfrac{2}{(2 + 2 \sqrt{3} + 2\sqrt{33}/3)-2 \sqrt{3}} = \dfrac{\sqrt{33}-3}{8} \approx 0.343$$

compared with $\dfrac{1}{3} \approx 0.333$ for nine or ten points.

-