9
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ IIRC, it can be added that with $19$ points $>1$ is not possible (only $=1$) $\endgroup$ – Hagen von Eitzen Mar 1 at 11:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Servaes Mar 1 at 13:12
  • 1
    $\begingroup$ Minor result; a configuration of $18$ points cannot contain all vertices of the regular hexagon of side $2$. $\endgroup$ – Servaes Mar 1 at 17:33
  • 1
    $\begingroup$ 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 $\endgroup$ – Hagen von Eitzen Mar 1 at 17:55
2
$\begingroup$

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.

enter image description here

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ "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? $\endgroup$ – user2661923 Mar 4 at 18:55
  • 1
    $\begingroup$ So it seems the answer is no. Great idea to connect it with packing of disks inside hexagons. $\endgroup$ – orangeskid Mar 4 at 20:14
  • 1
    $\begingroup$ 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). $\endgroup$ – orangeskid Mar 5 at 0:30
  • $\begingroup$ @orangeskid I updated an answer. $\endgroup$ – Alex Ravsky Mar 6 at 7:39
  • 1
    $\begingroup$ 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. $\endgroup$ – orangeskid Mar 6 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.