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.
$\begingroup$
$\endgroup$
12
-
7$\begingroup$ Perhaps I am misunderstanding this, but I thought MathOverflow was for asking questions to which you do not already know the answer. $\endgroup$– Charles StaatsApr 6, 2010 at 22:58
-
2$\begingroup$ This doesn't yield a very tight bound, but if you fill, say, a 2x2 area densely enough with evenly-spaced points, then no matter how the discs are placed there will always be some points uncovered in the "inverted trefoil" area where three discs come together. $\endgroup$– jordancurveApr 7, 2010 at 5:02
-
2$\begingroup$ @DouglasS.Stones An upper bound appears in this paper: arxiv.org/abs/1101.3468 $\endgroup$– Yoav KallusJan 25, 2014 at 21:16
-
2$\begingroup$ I think this question is also interesting in higher dimensions. How does the minimal number $N(d)$ (defined in the obvious way) grow with the dimension $d$? $\endgroup$– Roland BacherApr 15, 2015 at 8:39
-
4$\begingroup$ Practical application of this question: all my buckets are the same size, can I still catch all the water if my roof is leaking at $N$ points? $\endgroup$– GlorfindelFeb 1, 2023 at 19:47
|
Show 7 more comments
5 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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)
answered Apr 7, 2010 at 7:00
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
1
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?
answered Apr 12, 2010 at 1:44
-
9
$\begingroup$
$\endgroup$
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).
