4
$\begingroup$

The questions here and here relate to the question as to whether, given ten equally sized coins and a configuration of ten dots in the plane, there is a way of placing the coins so that they cover all the dots without overlapping.

The solution given depends on the fact that a close-packing of circles in the plane covers more than ninety percent of the area, and then uses probability to show that the expected number of dots covered by a random close-packing of coins is greater than nine, so some particular configuration must allow all ten dots to be covered.

But such an argument does not go through for eleven dots - and I was wondering if there were a counterexample in this case (or for some number greater than eleven). The margin is quite low for eleven, so a counterexample would have to be quite delicate.

$\endgroup$
  • $\begingroup$ Maybe I should give a larger bounty for this. It seems to me to be a great problem with an elementary statement, at which the bounds of elementary reasoning are tested. Exceptional configurations are likely to have interesting properties. $\endgroup$ – Mark Bennet Dec 23 '15 at 22:16
7
+50
$\begingroup$

This is the Naoki Inaba coin-covering problem. The paper Covering Points with Disjoint Unit Disks shows a set of 45 points that can't be covered with unit disks. I believe that was beaten, but I don't recall the details.

$\endgroup$
  • $\begingroup$ Thank you, that's the kind of thing I was looking for, and indeed the kind of proof I had in my mind to try out if I found some time. They show also that twelve points can be covered. $\endgroup$ – Mark Bennet Nov 10 '15 at 7:29

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.