combinatorial-geometryeuclidean-geometrygeometry
Can we place $18$ points in a regular hexagon of side $2$ such that the minimal distance between points is $>1$?
This a follow-up of this question. In the answers provided for it there are shown solutions for $14$, $15$, $16$, and $17$ points. Also, we can place $19$ points so that the minimal distance between them is exactly $1$.
Thank you for your interest!
This kind of problem is very hard. You might have a look at packomania which has solutions for many numbers of circles in squares and rectangles. Most of them are found experimentally and not proven to be maximal. You can almost incorporate the wraparound by shrinking the square or rectangle by the radius in each direction, but I don't think it gets the corners right.
Here are 15 points with minimal distance $1$ and all minimal distances marked.
Now, move the blue points towards the centre a bit (e.g., until they form a smaller equilateral triangle and with blue-blue distances equal to blue-red -- that is, with these distances $=3-\sqrt3=1.2679\ldots$). That allows you to move the green dots inwards as well, thereby making all distances slightly $>1$.
(Finally, drop one of the points in order to reach the desired number of $14$ points.)
Best Answer
Assume that we placed $18$ points in a regular hexagon of side $2$ such that the minimal distance between points is $2r$. It follows that we can pack $18$ circles of radius $r$ into a regular hexagon of side $2+\tfrac{2r}{\sqrt{3}}$, or $18$ unit circles into a regular hexagon of side $\tfrac 2r+\tfrac{2}{\sqrt{3}}$. But the smallest known side of such a hexagon is $4+\tfrac{2}{\sqrt{3}}$. It follows $r\le \tfrac 12$.
I expect that an easy proof of the example optimality following from a partition of the hexagon into $17$ pieces of diameter at most $1$ is impossible. I guess that a proof of the example optimality is hard.
One of approaches to the proof, started by Hagen von Eitzen is to localize positions of points in a solution. This approach was inductively used to solve a similar problem below. I proposed it at the final stage of All-Ukrainian student mathematical olympiad in 2001. No participants achieved an advance solving the problem. Also I found this problem (without a solution) in a book “How nonstandard problems are solved” by A. Ya. Kanel'-Belov and A. K. Koval'dgi, (Moskow, MCNMO, 1997, in Russian), see Problem 15 at p. 49.
First we remark that a maximal distance from a polyhedron to a point outside it can be reached in one of vertices of the polyhedron. Now let $x_1,\dots, x_8\in Q$. Suppose that all distances between points are greater than $1.$ Then in every of $8$ closed cubes at the picture can be placed at most one point $x_i.$ Without loss of generality we can suppose that $x_1\in M_1.$ If $x_1=(x_1^1,x_1^2,x_1^3),$ then $x_1\le a_1,$ where $|(1,1/2,1/2)-(a_1,0,0)|=1,$ thus $a_1=1-1/\sqrt{2}<1/2$ (otherwise for all $i\in\{1,\dots,4\}$ we have $|A_i-x_1|<1$ and therefore there exists $j\ne 1$ such that $|x_i-x_j|<1$). We can similarly prove that $x_1^2\le a_1,x_1^3\le a_1.$ Thus, a point $x_1$ is in cube $M'_1$ with an edge $a_1.$ Similar arguments can be used for all other $x_i$. Assume that it is already proved that all points $x_i$ have to be in small cubes with an edge $a_n.$ Similarly to the previous we can prove, that all of them must be in small cubes with edge $a_{n+1},$ where $|(1,a_n,a_n)-(a_{n+1},0,0)|=1,$ thus $2a_n^2+a^2_{n+1}-2a_{n+1}=0$. If $a_{n+1}>a_n,$ then $3a_{n+1}^2-2a_{n+1}>0$ and therefore $a_{n+1}>2/3,$ that is impossible, because $a_{n+1}\le a_1<1/2.$ Thus a sequence $\{a_n\}$ has a limit $a$, and $3a^2-2a=0.$ Hence $a=0.$ Thus all points are placed in vertices of the cube $S,$ a contradiction.