Determine the smallest integer $m_n$ which satisfies the following property: If $m_n$ points are chosen inside an equilateral triangle of sides 1, then at least two of them are at distance $\frac{1}{n}$ or less.
For example $m_3=10$ means that if you choose 10 points inside an equilateral triangle with sides 1 then at least two of them are at distance $\frac{1}{3}$ or less.
Hint : The equilateral triangle of side 1 can be divided into 4 equilateral triangle of sides $\frac{1}{2}$. Further an equilateral triangle of side 1 can be divided into 9 equilateral triangles of sides $\frac{1}{3}$.
I know how to divide the equilateral triangle. For example the equilateral triangle of side 1 can be divided into 4 equilateral triangle of sides $\frac{1}{2}$ as
I am guessing that the answer if $m_n=n^2+1$. I have a vague idea of the proof. But there are quite a few loose ends. Help please!
Best Answer
I'll assume that you are interested in the situations where $n$ is an integer, but part of my solution will apply to non-integer $n$ as well.
Thinking about regular arrangements of regular triangles forming a larger regular triangle, it is easy to see that for $n=1$, you can place $r_1=3$ points so that the minimal distance is $1$. For $n=2$ you have $r_2=6$ corresponding to the vertices in the picture in your question, and for $n=3$ you have $r_3=10$ which looks like the example equation you gave. These are the triangle numbers, with a slight index shift, for which there is a nice formula (although not quite so simple as the formula you gave):
$$r_n=\binom{n+2}{2} = \frac12n^2+\frac32n$$
Intuition might tell you that if you were to remove one point from such a regular configuration, then you have more room, thus allowing the points to shift around slightly in order to increase their minimal distance above that $1/n$. However, that intuition turns out to be wrong, as I'll show below.
Let's rephrase your question to a packing problem. Scale everything by $2n$, and you're asking about points in a triangle of side $2n$ which are at least distance $2$ apart from one another. In the interior, being at distance $2$ means that circles of radius $1$ around the points touch, so you can also talk about unit disks which must not overlap. At the boundary, the disks may well extend beyond the triangle of side $2n$, as long as they are contained in the triangle you get from that by a parallel displacement of all the edges by $1$ unit. That displacement adds $2\sqrt3$ to the edge length (please verify).
So the question I'm going to build upon is the question of how many unit disks one can place in a triangle of size $2n+2\sqrt3$ without overlap. Note however that your question is a slightly different one, and I'll get back to that in a moment. My favorite site for packing configurations is Erich's Packing Center. Its page on circles in a triangle describes the situation you're after. They do things the other way round: list the number of unit disks and compute the triangle size from that. But you can easily turn that relation around.
So as I said, your question is indeed slightly different: you want the minimal number of disks where the disks have to touch. Which means that if you take one disk less, then they won't have to touch, which in turn means that they would fit into a slightly smaller triangle.
Now look at the images at EPC. You'll find that the triangle size for $5$ disks is the same as for $6$. So while you could place $r_2=6$ points so that they are at least $1/2$ apart, you can't place $5$ points so that they are strictly more than that apart. You'll have to go down to $4$ points to achieve that. Therefore, $m_2=5$ which is not the same as the $r_2=6$ discussed above. The same holds for $n=3$: the same configuration which is used for $10$ disks is already used for $9$ disks, while $8$ disks fit into a smaller triangle. Therefore $m_3=9$.
For $n=4$, the situation appears to be the same at first glance: $14$ disks take the same amount of space than $15$ disks, while $13$ fit into a smaller triangle. But there is something interesting to note here: the configurations for $13$ and $14$ disks are only described as “found”, not “proved”. So they might not be the optimal solutions yet. For the $13$-disk arrangement, we don't have to care whether there is an even smaller one, as long as we know it to be smaller than for $14$. But we have no proof that you can't place $14$ disk into a triangle which is smaller than that for $15$ disks.
I'm not sure what is known past the end of that list. One could conjecture that the pattern holds: taking one disk out of a regular configuration maintains its size, while taking out two disks reduces the size. The latter can probably be proven by looking at how the 13-disk configuration looks, and applying the same modification to the two bottom-most rows to larger situations. I have no clue how to prove the other half.
So my conjecture would be
$$m_n = r_n-1 = \binom{n+2}{2} - 1 = \frac12n^2+\frac32n$$