Sunday, 22 June 2014

co.combinatorics - 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?

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)

No comments:

Post a Comment