# Can we place $18$ points in a regular hexagon of side $2$ such that the minimal distance between points is $>1$?

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!

• IIRC, it can be added that with $19$ points $>1$ is not possible (only $=1$) – Hagen von Eitzen Mar 1 at 11:41
• Perhaps it helps to distinguish cases according to the number of points in the central hexagon of side length $1$? There are at most $5$ points in this region, and the remaining region is a hexagonal annulus. It seems impossible, but it seems that any proof will be a rather cumbersome exercise in elementary geometry. – Servaes Mar 1 at 13:12
• Minor result; a configuration of $18$ points cannot contain all vertices of the regular hexagon of side $2$. – Servaes Mar 1 at 17:33
• By gnawing off 17 shapes of diameter 1, I found that one point must lie within a comet-shaped thing of area $\approx 0.2$ (and diameter slightly $>1$). There are six symmetric copies of this comet and so I can conclude that there must be a point at most $0.2$ off the centre of the hexagon, or each "comet tail" must contain exactly one point. -- I did this in a geogebra session with confusingly many radius 1 circles, so I am not 100% sure about the exact sizes stated above – Hagen von Eitzen Mar 1 at 17:55

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.

In a cube $$Q$$ with an edge $$1$$ are placed $$8$$ points. Whether always among them there exist two points placed at distance at most $$1$$?

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.

• "But the smallest known side ...". Does this signify that a denser packing has been proven to be impossible, or does this signify that no denser packing has as yet been discovered? – user2661923 Mar 4 at 18:55
• So it seems the answer is no. Great idea to connect it with packing of disks inside hexagons. – orangeskid Mar 4 at 20:14
• However, can you prove the above fact? The idea is good to show that we cannot place $19$ points, since that would show a more dense packing of disks in the plane. That is not possible ( classic result, but not easy to prove). – orangeskid Mar 5 at 0:30
• @orangeskid I updated an answer. – Alex Ravsky Mar 6 at 7:39
• Interesting! Now, maybe there is a similar solution for the hexagon? How about $19$ points? It should follow from other results, but even this one seems difficult. – orangeskid Mar 6 at 9:38