Puzzle time - Dots and Frisbees

[jon-nyc]

Yeah I don’t have an answer yet. I suspect the answer is you can’t guarantee coverage.

Imagine you tile the plane with hexagons and stick the biggest possible circle inside each hexagon, you cover 90.7% of the plane with your circles because that is the ratio of the area of the circle to the area of the hexagon containing it. That is a just over 9 out of 10. Given the problem references 10 points, I’m guessing - just guessing - that that is an inflection point. IOW 9 you can guarantee coverage, 10 you can’t.

[taiwan_girl]

click to show

I have not yet look at the replies, but I think you can DISPROVE your theory.

I think that you could arrange the dots so that it would be impossible to dover them without overlapping.

For example, place the dots in a line very close to each other but not touching. Assuming that the frisbees are larger than the dots, then you would have to overlap them to cover the dots.

(Of course, the above seems to easy, so I am sure I am missing something! LOL)

[jon-nyc]

@taiwan_girl There’s no requirement that each dot be covered by a distinct frisbee. In your example one frisbee could cover most or all of the dots.

[taiwan_girl]

@jon-nyc said in Puzzle time - Dots and Frisbees:

@taiwan_girl There’s no requirement that each dot be covered by a distinct frisbee. In your example one frisbee could cover most or all of the dots.

Okay, so the frisbees can be any size in relation to the dot, but they (frisbees) all have to be the same size.

Hmmmm.

[jon-nyc]

I have an answer but it’s a bit hand-wavy.

This hint they gave helped:

HINT: If the frisbees were square, you could cover the whole plane with them, thus most of the floor and all of the dots.  You can't do that with disjoint unit disks, but what fraction of the plane can you cover with them?

[taiwan_girl]

@jon, the smaller the size of the frisbee, the greater "area" of the floor that could have the coverage of the frisbees. As the frisbees get larger, there will be more open area.

[Klaus]

Ah, I think I got it. Even without handwaving.

click to show

The dots can always be covered by a hexagon pattern.

A hexagon pattern covers 90.7% of the plane, as you say, but of course it can be placed in infinitely many ways on the plane.

However, for any fixed distribution of dots, the expected value of covered dots of a randomly placed hexagon pattern is 9.07.

Since 9.07 is greater than 9, it means that there must be some covering that covers more than 9 dots, i.e., 10 (because otherwise the expected value couldn't be >9).

[jon-nyc]

Yes Klaus.

Or at any rate that’s my take. We’ll get the official answer Saturday.

[jon-nyc]

@taiwan_girl

Ignoring the spaces near the walls (which the problem definition allows us to do) the blank space is the same regardless of the size of the frisbees. Smaller discs have smaller spacing but there are more of them. As Klaus pointed out, you can tile the space completely with hexagons and the biggest circle you can fit in a hexagon covers 90.7% of it, regardless of hexagon size.

[Ivorythumper]

@jon-nyc said in Puzzle time - Dots and Frisbees:

I have an answer but it’s a bit hand-wavy.

This hint they gave helped:

HINT: If the frisbees were square, you could cover the whole plane with them, thus most of the floor and all of the dots.  You can't do that with disjoint unit disks, but what fraction of the plane can you cover with them?

A frisbee is circular. Patently so...

Interesting history!

[Klaus]

What's interesting about the proof is that it is non-constructive: You can prove that a covering exists, but the proof doesn't give you a way to actually find that covering. Brouwer and Hilbert fought passionately for decades about whether a non-constructive proof is actually a proof .

[Ivorythumper]

I'd guess any disproof would require that some points were placed on the circumferences such that rotation or movement of any three, or movement of any two would void the solution.

[Horace]

I don't see the necessary logical connection between % coverage of the hex pattern of circles, and an intentionally arrayed set of 10 dots meant to avoid coverage.

[Klaus]

@Horace said in Puzzle time - Dots and Frisbees:

I don't see the necessary logical connection between % coverage of the hex pattern of circles, and an intentionally arrayed set of 10 dots meant to avoid coverage.

You take an intentionally arrayed set of 10 dots and now consider the expected value of dots covered by a randomly chosen hex covering. If it's >9, there must be a covering with 10.

[Horace]

@Klaus said in Puzzle time - Dots and Frisbees:

@Horace said in Puzzle time - Dots and Frisbees:

I don't see the necessary logical connection between % coverage of the hex pattern of circles, and an intentionally arrayed set of 10 dots meant to avoid coverage.

You take an intentionally arrayed set of 10 dots and now consider the expected value of dots covered by a randomly chosen hex covering. If it's >9, there must be a covering with 10.

I'm sure that works. In any case, it's not a disproof that a covering of 11 is always possible. At best, this solution is the simplest one which could establish that 10 is always possible.

[Ivorythumper]

@Horace My drawing shows that 8 of the 10 dots (the blue vertical sticks represent the location of a non-dimensional point) are covered by non-overlapping circles, so 2 are not. The test would be to have any number of non-overlapping circles cover all 10.

I haven't tested any patterns for that yet, but it seems easy enough since the circles don't need to be touching. It doesn't say anything about being in a hex pattern.

[Ivorythumper]

@Horace IOW, what I'm doodling with is a solution that solves for say 8 of the 10 points, and any movement of frisbees that tries to cover all 10 causes overlap.

The above doodles are too spread out -- any such "disproof" would only be concerns with the points around one frisbee -- presumably some one in the center, some on the perimeter, and some in the voids between the hex pattern.

[Ivorythumper]

@Horace I must be missing something here, as I'm finding easy solutions.

[Axtremus]

@Ivorythumper said in Puzzle time - Dots and Frisbees:

… I'm finding easy solutions.

My mathematical cheats easy solutions:

click to show

1. Use theoretical frisbees whose sizes are infinitesimally small — one frisbee per dot
2. Use a theoretical frisbee who size is infinitely large — one frisbee to cover them all
   

[jon-nyc]

SOLUTION: The naked mathematical question being asked here is: Can any set of 10 dots in the plane be covered by disjoint unit disks? If the dots are close together, you can cover them with one disk; if they're spread widely apart, you can cover each with its own disk. It's the medium distances that could cause problems.

Certainly you can cover any two dots, and a little more thought will convince you that three or four are also doable. How about large numbers of dots?

The answer is certainly "no" if 10 is replaced by 10,000. The reason is that you can't "tile" the plane with unit disks; in other words, you can't arrange disjoint unit disks so as to cover the whole plane (as you could, say, with unit squares). If you put down 10,000 dots in a 100 x 100 grid pattern covering a square somewhat bigger than a unit disk, it won't be possible to cover every dot with disjoint unit disks.

So it's a question of quantity: is 10 more like 3, or more like 10,000? Here's a thought: how much of the plane can be covered by disjoint unit disks? You would probably guess that the best way to pack unit disks is in a hexagonal array, with each row of disks fitted nicely into the cracks between the disks in the row below. And you'd be right.

How good is this disk-packing — in other words, if you choose a large region of the plane (say, a 1,000,000 x 1,000,000 square) and pack it hexagonally with disks, what fraction of the region will be covered? In the limit, that fraction must be the fraction of the area of one of those hexagonal cells that is occupied by an inscribed unit disk. Of course, the disk, if it has radius 1, has area pi. The hexagon is made up of six equilateral triangles of altitude 1 and area 1/sqrt(3), thus total area 6/sqrt(3) = sqrt(12). It follows that the fraction of area covered by the disk is pi/sqrt(12) ~ 0.9069.

Hmm. The disks cover more than 90% of the plane; crudely speaking, more than 9 points out of 10. Can we make use of that? Trouble is, the dots on the floor are not random points, they are (in the worst case) arranged as if by an adversary.

But we can shift the hexagonal disk-packing randomly. To do this, just fix some hexagonal cell and pick a point in it uniformly at random; then shift (without rotating) the whole picture by moving the center of the cell to the selected point. Now we can say that for any dot on the plane, the probability that it is covered by some disk of the randomly shifted configuration is 0.9096.

It follows that of our 10 dots, the average number covered by disks of the randomly shifted hexagonal packing is 9.096. But then some configurations must cover all 10 points, and the problem is solved!

And this is an interesting addition:

[The actual maximum number of points in the plane that can always be covered by disjoint unit disks is not known; embarrassingly, the best results currently are that 12 points are always coverable and 42 are not.]