What is the minimum N for which there exist N points in the plane that cannot be covered by any number of non-overlapping closed unit discs?

Question

This problem was posed in March 2010 at G4G9 in a talk by the Japanese mathematician Hirokazu "Iwahiro" Iwasawa. He claims there is a simple proof that N > 10, though he did not share it with the audience, since it proving it is apparently an enlightening exercise in its own right.

Answer 1

The trick for N = 10 (which I heard from a friend earlier today) is to check that the density of the triangular packing of unit diameter circles is high enough that some translate of this packing must cover all the points.

Answer 2

I was told this puzzle last Friday by Peter Winkler (who had mentioned that it was told to him by a Japanese fellow who is perhaps the one you are referring to).

The solution in the $n \leq 10 $ case is to consider the tiling of the plane by unit height hexagons. Inscribe within each of these hexagons a unit circle. This grid of circles has density > 0.90 on the plane, and so if you randomly place this grid on the plane you accordingly have expected number of points covered > 9 (out of the 10), and this implies exists an arrangement that covers 10. (theres a few details missing from this probabilistic method argument, but you get the basic idea).

I believe for the $n>10$ case we have some way of computing an upper bound on the density of a sphere packing on the plane that rules it out in general. (or something to that extent)

Answer 3

In the answer to Open problems in Euclidean geometry? , Alexey Ustinov brings into attention to a 2012 article.

Greg Aloupis, Robert A. Hearn, Hirokazu Iwasawa, Ryuhei Uehara, Covering Points with Disjoint Unit Disks, 24th Canadian Conference on Computational Geometry (2012)

The abstract of that article confirms that it's concerned of the same problem, and gives improved bounds.

We consider the following problem. How many points must be placed in the plane so that no collection of disjoint unit disks can cover them? The answer, k, is already known to satisfy 11 ≤ k ≤ 53. Here, we improve the lower bound to 13 and the upper bound to 50. We also provide a set of 45 points that apparently cannot be covered, although this has been determined via computer search.

The article also claims that the lower bound of 11 was published in 2008

Answer 4

To bring this problem back to the attention of MO, I'll make a guess. Consider the following set of 13 points: 12 equally spaced on a circle of radius $1+\epsilon$, the 13th at the center of that circle. Can you cover all 13 points with non-overlapping unit disks?

Answer 5

You can find a probabilistic proof of the case N = 10 in this paper:

Y. Okayama, M. Kiyomi, and R. Uehara. On covering of any point configuration by disjoint unit disks. In 23rd Canadian Conference on Computational Geometry (CCCG), pages 393–397, 2011. (Accepted to Geombinatorics).