Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Leaving out non-overlapping in the title seems a bit too clever. –  John Jiang Apr 6 '10 at 22:39
1  
Maybe I am missing something, but the result seems obviously false: take a point surrounded by 9 other points in a small circle, then how are you going to have a disk covering the center point without touching the remaining points? If I interpret the problem as saying not every point has to be in a disk, then it seems rather trivially true, because all I need to make sure is every time I add a new disk, it covers at least one point, which is certainly doable. –  John Jiang Apr 6 '10 at 22:44
7  
Perhaps I am misunderstanding this, but I thought MathOverflow was for asking questions to which you do not already know the answer. –  Charles Staats Apr 6 '10 at 22:58
    
Perhaps the original poster could rewrite his question so as to make the second part the main "question", and then make the current title a remark to lend background context or interest. –  Yemon Choi Apr 6 '10 at 23:20
1  
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. –  Josh Jordan Apr 7 '10 at 5:02
show 4 more comments

3 Answers

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.

share|improve this answer
add comment

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)

share|improve this answer
add comment

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?

share|improve this answer
1  
Yes. imgur.com/4ZCVy.jpg –  Josh Jordan Apr 12 '10 at 5:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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