Puzzle time - Dots and Frisbees
-
-
click to show
@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 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.
@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.
-
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?
"You never know what worse luck your bad luck has saved you from."
-Cormac McCarthy -
@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.
-
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.
-
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?
@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...
-
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 .
-
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.
-
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.
@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 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.
@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.
Education is extremely important.
-
@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.
@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.
-
@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.
@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.
-
@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.
@Horace I must be missing something here, as I'm finding easy solutions.
-
@Horace I must be missing something here, as I'm finding easy solutions.
@Ivorythumper said in Puzzle time - Dots and Frisbees:
… I'm finding easy solutions.
My
mathematical cheatseasy solutions:
click to show -
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.]
"You never know what worse luck your bad luck has saved you from."
-Cormac McCarthy -
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.]
@jon-nyc said in Puzzle time - Dots and Frisbees:
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.
That's the part I got hung up on. But I understand that this method does work to establish that 10 is always possible. But as puzzles go, this solution seems less than satisfying to me. Probably the same reason you called your solution 'handwavy' even though it's mathematically coherent.
[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.]
Right, that's part of the reason why this solution is not totally satisfying.
