Our frequent and reliably insightful commenter Jonathan Kariv sends along this neat puzzle:
Your enemy chooses 10 points on an infinite tabletop and gives you 10 coins of the same size (let’s say U.S. quarters). Can you always place the coins on the tabletop in such a way that all 10 points are covered, but no two coins overlap?
If your enemy puts all 10 points far away from each other, you can just put one quarter over each point. If he scrunches them up real near each other, you can just put one quarter over all of them, and put the other nine quarters anywhere you want. But if he’s clever enough, can he make your job impossible?
Edit: I originally described the tabletop as “big”; I’ve edited this post to change it from big to infinite, in order to be true to the puzzle as Kariv originally posed it. My apologies for the original inaccurate transcription.
Are we ignoring the trivial answer of the corner? Or allowing the quarters to overlap the boundaries?
Sitting to think about non-trivial answers now.
If there are an infinite number of points and coins, he can make my job impossible – although I think I’d offer my enemy 99% my coins in exchange for a truce, and quickly exchange my 1% for some foreign currency before he does.
All he’d have to do is arrange the dots in a sufficiently dense grid on the paper. Now matter how I close-pack my coins, there will be points in the gaps.
In fact, he doesn’t need an infinite number of points, some smallish finite number will do, covering sufficiently densely a sufficiently large area of the plane. However, I haven’t found a specific arrangement of a specific number of coins.
But am I allowed to choose what kind of coin? If so, I’ll choose the Cabinda commemorative 2005 30 centavos coin.
No, because the radius of a coin is twice its diameter.
If the point is half on top of one radius and the coin is simultaneously covering another point, then you can simply move either the coin over both, or place one coin on each point.
“Can you always place the coins on the tabletop in such a way that all 10 points are covered, but no two coins overlap?”
No. I will not reveal my reason for saying so yet, so as to not spoil it for others, but this seems obvious to me (of course, maybe I’ve missed a trick and am completely wrong).
Martin – I do not believe that a coin’s radius can be twice it’s diameter, I think you mean it’s diameter is twice it’s radius.
Do all coins need to be flush on the tabletop? That is, can coins be stacked on top of each other?
If they must all be touching the table then I believe only four points are necessary to prevent them from being covered by coins. Like Al, I’ll keep my thinking quiet for now.
I think he could make the job impossible. When three coins are nested together in a triangle pattern, there is a gap right in the middle of the triangle. So one point could be placed in that gap.
The trick would be how to place the other nine points such that they “fixture” three coins into the triangle pattern. I haven’t got that part figured out. Not yet anyways…
The Bad Puzzle Theorem applies I bet. The number 10 cannot really have anything to do with it, if you cannot with 10 then you will not be able to with a lower number — 3 or 4. So it would be a bad puzzle with a 10 point countere example. Hence you can always do it.
Ken B – you definitely can’t do it with an infinite # of points, as Mike H points out.
He will try and force you to place a coin that topples over the edge, I think.
10 isn’t infinite. My bet is any finite set can be covered. Otherwise the puzzle as stated would be a bad one.
Some infinite sets can be, even uncountable and dense ones.
(Actually I bet any nowhere-dense countable set can be but that’s just a gut feeling.)
If the table is very small, then you wouldn’t be able to fit all the coins on it.
The table is infinite. Steve paraphrazed me and changed it from “disjoint unit circles in the plane” to “coins on a large table”.
I believe the answer is no. Daniel and others were onto something when they were talking about using the edge. Your enemy could place 9 points in an arc that has the same radius as a coin and with two points on the edge of the table. The arc would be created so that placing a coin so the edge covers all points would cause it to fall off the table (ie, the center of the arc/partial circle of points is past the edge of the table). Then, place the 10th point on the edge of the table half way between the two endpoints of the arc.
I noted that Landsburg said “tabletop, “ not “plane.” That suggests that edges are relevant here.
I also noted that Landsburg did not specify that the table is rectangular. That suggests that corners were NOT relevant here.
Could he do it with fewer than 9?
Well, the edge solution(s) are now moot as the tabletop is now a plane. I think you may be able to modify my solution so that 9 points are placed in a circle the same size as the coin and equal distances apart from each other along the edge. Then, the 10th point is placed in the center of the circle. I’m not sure if it still works, but it might.
It’s not a question of using the edge, as Steve has updated the puzzle to posit an infinite table – no edges. And if I have three points in a triangle, plus a point at the center of the triangle, I can simple shift one of the coins to cover a corner and the center.
I just realized that my circle solution above is silly as a single coin could just cover all the points. The enemy would have to move the points out by an infinitesimally small amount, so the diameter is slightly larger than that of the coin.
No edges? No corners?
No fun.
Ok, circles stack in hexagonal grids. I suspect the trick is to position points in a manner that is askew from a hexagonal grid. Points equally spaced pentagonally or heptagonally, less than one diameter apart, perhaps? Or a spiral pattern?
Where can I purchase said infinite tabletop to test out my theory?
@Mike H is right, that the solution is trivial for a triangular or square coin. Thus, the only possible solution is to force a point into the gap between circular coins. However, I suspect that it’s always possible to cover the points, but I can’t prove it.
Do the points have to be covered by an open neighborhood? If the coin touches it, does it still count? I’m leaning towards “no, he can’t make it impossible”, but I don’t have a full justification yet.
I’d like to see how the question would change for old-timey company scrip coins, which often had geometric shapes punched out of the middle.
http://en.wikipedia.org/wiki/File:Coal_scrip.jpg
@Ken B, it’s possible that the number 10 is a key point. If I make an equilateral triangle, divided into 4 equal sized component triangles, and then place points at the vertices of the sub-triangles and at their centers, I have exactly 10 points. If the verticle axis of the large triangle is at least 1.5 diameters, then I can cover one point per coin. The question is can I shrink the triangles to force a point into a gap.
@Al V: You could be right, but I doubt it. Since there is no 4 point counterexample I expect there is a proof you can alwys do it.
@Ken B, I think you are right. I certainly can’t visualize a solution on an infinite table.
@Ken B, I think you are right. 10 isn’t infinite.
Worst. Concept. For a Snakes on a Plane sequel. Ever.
Get a piece of 1mm = 1/25in graph paper, A4 or US Letter size, and draw a point at each intersection. Then, no matter how many non-tesselating coins you have, you can’t cover all the points (unless the coins are, say, 2007 CA$1000000 coins or similar, in which case I just need a bigger piece of graph paper).
Since I have solved the puzzle for some value of N points, I suggest that KenB has mis-applied the bad puzzle theorem. It does not imply that there is no solution for any number of coins. Instead, the bad puzzle theorem implies that the minimum number of points my enemy needs to draw to stymie me is either 10 or 11.
The question is – how small must my graph paper be before my enemy loses?
The points can always be covered.
For simplicity, suppose we have an infinite number of quarters. This doesn’t make the task any easier, for if the points are all covered, we simply remove all but the ten (or less) quarters that cover a point. Randomly choosing a starting point and arrange the quarters in a hexagonal grid. Choose our units so that a quarter is a unit circle. The hexagons have side length of 2/3 * sqrt(3), and thus an area of 2*sqrt(3) = 3.4641, while the circle has an area of 3.1416. Thus, the quarters cover over 90% of the plane, so a randomly chosen hexagonal grid of quarters covers over 9 points on average. If a random grid covers more than 9 points on average, at least one particular grid covers more than 9 points. QED.
The argument fails with 11 points. I don’t know the answer in this case.
Jeffrey: I love your approach but I think it needs more argument.
Try this: Take the set of all those circles with area .51 that are contained entirely in the unit square. Each of these covers over half the area of the square, so if I pick one at random, it should cover at least two of the four vertices.
This is clearly wrong. In what important way does it differ from your argument?
Bravo, Jeffrey! Really elegant solution.
(Also note that the bad puzzle theorem has failed here, since the proof does not establish whether 11 is possible.)
Jeffrey, you’ve assumed that any point of the plane is equally likely to be a point my enemy chooses. However, there’s no reason why he has to choose the points in that manner.
Therefore, you can’t compare areas to compute probabilities or average numbers of coins.
Apart from that, it’s a beautiful argument – so beautiful that it’s surely worth inventing a puzzle that it solves.
I think you guys are missing Jeffrey’s point. I’ll flesh it out.
Let the points 1-10 lie anywhere you choose, chosen as cleverly as you like.
Pick a random point A on the plane, and generate the infinite hexagonal grid of coins laid out such that the center of one of the coins is at point A. (Point A is assumed to be random, but no need to assume that points 1-10 are random.)
Designate as Xn the random variable that takes a value 1 iff point n is covered by a coin. Since point A (and hence the quarter grid) is uniformly random, the expected value of Xn is equal to the fraction of the plane covered by coins, which is > .9.
Let S be the total number of points that are covered: S = X1 + X2 +…+ X10. By the properties of expected values, E[S]>9.
Therefore, there must exist regions of the sample space of A for which the quarters will cover strictly more than 9 points, i.e. 10 points.
Q.E.D.
One technical fix to the solution: it is not possible to pick a point A uniformly from an infinite plane, so instead designate an arbitrary square on the plane with sides equal to the diameter of a coin, and chose A uniformly random from that square.
Note also that Jeffrey’s solution proves that it is always possible not only to cover the 10 points, but to cover them when restricted to using a packed hexagonal grid arrangement, which I found surprising.
@Al, yes you’re right. What can I say, it was early over here.
Re: Ed
Yes, that’s what I’m going for.
More precisely on the random selection of a hexagonal grid: Start by choosing an arbitrary starting point and arbitrary axes and tessellate the plane with hexagons of the appropriate size for a quarter to be inscribed. Next, arbitrarily choose a hexagon.
Now choose a random point within the hexagon uniformly, and place the center of the first quarter on this point. Place the remaining quarters in the hexagonal pattern in line with the fixed axes.
And now, all points on the plane are equally likely to be covered by a quarter. (This is the difference between my solution and Landsburg’s example.)
>Note also that Jeffrey’s solution proves that it is always possible not only to cover the 10 points, but to cover them when restricted to using a packed hexagonal grid arrangement, which I found surprising.
Not only that, but it works even if the enemy chooses your axes!
Jeffrey & Ed: Breathtakingly awesome solution!
ed: You’ve convinced me that Jeffrey is right. Thanks—-and many thanks to Jeffrey. This really is quite beautiful.
I apologize for being dense, but I don’t follow how proving that some set of 10 coints must cover 10 points proves that I can cover any set of 10 points.
Congrats to Jeffery. Thanks Ed for doing the fleshing out.
I should also probably mention that, 10 is the number of points given precisely because of this solution.
It’s unknown weather 11 points can always be covered. It is known the 55 points cannot always be covered but 54 is also unknown.
Jonathan Kariv: Thanks for the great puzzle.
Congratulations to Ed and Jeffrey for the interesting solution to this puzzle. I wonder if Steve have had another solution in mind though.
Gaah, sorry for the typo.
Al V: Ed and Jeffrey’s solution starts with the assumption that the ten points have been chosen, and makes no assumptions about those locations of the points. Therefore this is a general solution that can be applied to any 10 points. Given any 10 points, their logic applies. Are you still confused?
David Grayson: I had no other solution in mind; I hadn’t spent much time on this puzzle, but even if I had, I doubt that I’d have found this clever solution.
Yes, I see Jeffrey’s point now. Very nice :-)
Is there a reference for this proof?
I know I’m way late to this party, but out of curiosity does that proof mean that ANY pattern that covers greater than 90% of an area can be placed and oriented in such a way that it covers any set of 10 points in the area?
Quite an elegant solution Jeffery! If I understand it correctly, we can generalize your bound for higher dimensions:
Dimension Packing Fraction Coins
— — —
1 1.00 infinite
2 0.9067 10
3 0.7405 8
4 0.6100 7
5 0.4652 5
6 0.3729 4
7 0.2952 3
8 0.2536 3
But I have to stop here, since it seems that we only know the optimal hypersphere packing densities for n=8 and a non-optimal density would tarnish your result!
We could think up an analogous problem for 3D at least. Imagine yourself the commander of 8 bombers about to run an attack on an enemy starship (has to be in space to avoid the tabletop, er, edge effects). You know that the enemy has precisely 8 bombs that explode quickly and spherically but are only dangerous up to a finite fixed radius. Furthermore the bombs short circuit themselves if their blast radius would overlap. Is there an attack pattern that would guarantee you success? Would you be able to do it with nine planes/bombs?