Plates that cover a table

[bonanova]

In our last table and plates puzzle, we filled a circular table with plates that touched without overlap.

Now we want more plates. Read on ...

I've just placed 12 [circular] plates on a rectangular table.

They don't touch each other; but they're close enough that you can't add a plate without overlap,

Edit: even tho it overhangs the edge, so long as its center is over the table.

The plates are now removed and you are asked to completely cover the table with plates.

Edit: cover means you can't see any part of the table.

Twelve won't do it, so you'll have to order some more.

But they're expensive, so you don't want to order more than are needed.

How many plates are needed to ensure the table can be completely covered?

Obviously we now allow overlap and overhang, so long as the center of the plate is on the table.

Edited February 3, 2009 by bonanova
Clarify overhang, overlap and cover.

[Guest]

23.928, 24.027, and 24.055. So you're right in there with 23.815 which should be able to be covered with 48.

Ok, massaged my spacing around the edges a bit better and now I can get less. I'll agree with 48.

[bonanova]

Excellent work all.

The solution is 4 times the number of plates that satisfies the OP

Given that observation, does a proof suggest itself?

Can the proof be made rigorous?

We have a number that is sufficient to cover the table; is it also necessary? [i.e. optimal?]

[Guest]

Excellent work all.

Can the proof be made rigorous?

We have a number that is sufficient to cover the table; is it also necessary? [i.e. optimal?]

The solution is 4 times the number of plates that satisfies the OP

Given that observation, does a proof suggest itself?

I don't understand how you are discussing such a large table. I assume the table dimensions are expressed in terms of plate diameter (not radius).

If your plate has diameter = 1 unit, and the table is 5.5 x 4.3 (or thereabouts), you can get way more than 12 plates on it where they are not overlapping and their centers remain on the table. In fact, you can easily get 30 plates on such a table. In my previous post, I suggested that the size limit (where you can fit 12 such plates but not 13) approaches 3 x 4 d

The area of one plate is pi/4 square units; the area of the table proposed, 24 sq units or so, can easily hold many more than 12, even if you don't take advantage of the fact you are allowed to overhang the edges.

What the heck?

Oh yeah, my answer, 32 is not a multiple of 12!

Edited February 3, 2009 by xucam

[bonanova]

... my answer, 32 is not a multiple of 12 ...

Can anyone construct a counter example?

If not, this stands as the lowest [not disproved or retracted] answer to date.

[HoustonHokie]

I don't understand how you are discussing such a large table. I assume the table dimensions are expressed in terms of plate diameter (not radius).

If your plate has diameter = 1 unit, and the table is 5.5 x 4.3 (or thereabouts), you can get way more than 12 plates on it where they are not overlapping and their centers remain on the table. In fact, you can easily get 30 plates on such a table. In my previous post, I suggested that the size limit (where you can fit 12 such plates but not 13) approaches 3 x 4 d

The area of one plate is pi/4 square units; the area of the table proposed, 24 sq units or so, can easily hold many more than 12, even if you don't take advantage of the fact you are allowed to overhang the edges.

What the heck?

Oh yeah, my answer, 32 is not a multiple of 12!

It's not that you can fit more than 12 plates on such a large table. Of course it's possible to place more than 12 plates on the tables we've been discussing. The nuance we've been looking at is an optimal arrangement of 12 plates on that table such that you cannot add a 13th without either overlapping one of the original 12 or it's center being over the edge. So we've been trying to maximize the spacing between the plates to create the largest table possible where those conditions are not violated. Then, having acheived such a table, we remove the original 12 and see how many plates it takes to cover it completely. The phrasing of the OP (which has been both debated and clarified - thanks, BN), requires us to find the largest table possible to fulfill the 12 plate condition, and the smallest number of plates to cover it completely.

So, you have to do both of the following to solve the puzzle:

1. maximize the size of the table that can have an optimal arrangement of 12 plates, and

2. minimze the number of plates it takes to completely cover it.

I think you'll find that 32 plates are not enough to cover the maximum table.

[Guest]

It's not that you can fit more than 12 plates on such a large table. Of course it's possible to place more than 12 plates on the tables we've been discussing. The nuance we've been looking at is an optimal arrangement of 12 plates on that table such that you cannot add a 13th without either overlapping one of the original 12 or it's center being over the edge. So we've been trying to maximize the spacing between the plates to create the largest table possible where those conditions are not violated. Then, having acheived such a table, we remove the original 12 and see how many plates it takes to cover it completely. The phrasing of the OP (which has been both debated and clarified - thanks, BN), requires us to find the largest table possible to fulfill the 12 plate condition, and the smallest number of plates to cover it completely.

So, you have to do both of the following to solve the puzzle:

1. maximize the size of the table that can have an optimal arrangement of 12 plates, and

2. minimze the number of plates it takes to completely cover it.

I think you'll find that 32 plates are not enough to cover the maximum table.

With your eloquent restatement of the puzzle. It is your estimation of the maximum table size that cannot hold another plate that I have issue with.

I believe that the table you are considering is too large, you can get many more than 12 plates on without overlap and with centers on the table.

I believe that the actual maximum table size approaches, but is less than, 3d x 4d.

Edited February 3, 2009 by xucam

[Prof. Templeton]

With your eloquent restatement of the puzzle. It is your estimation of the maximum table size that cannot hold another plate that I have issue with.

I believe that the table you are considering is too large, you can get many more than 12 plates on without overlap and with centers on the table.

I believe that the actual maximum table size approaches, but is less than, 3d x 4d.

The plate diameter is 1d and the table is 3d x 4d, you could have a 3x4 grid of plates and each would touch another plate or the edge of the table at 0,90,180, and 270 degrees. You can certainly pack the same twelve plates onto a slightly smaller table by arranging them differently, but lets look at this arrangement. The most open space now on the table with our plates arranged in this grid style is between the plates diagonally (at 45 degrees). Diagonally there is .41 units from the edge of one plate to the next. In order to maximize the table size we would need to expand this diagonal distance to approach 1, so another plate barely does not fit. With only .41 units we are not maximized yet at 3d x 4d.

[Guest]

The plate diameter is 1d and the table is 3d x 4d, you could have a 3x4 grid of plates and each would touch another plate or the edge of the table at 0,90,180, and 270 degrees. You can certainly pack the same twelve plates onto a slightly smaller table by arranging them differently, but lets look at this arrangement. The most open space now on the table with our plates arranged in this grid style is between the plates diagonally (at 45 degrees). Diagonally there is .41 units from the edge of one plate to the next. In order to maximize the table size we would need to expand this diagonal distance to approach 1, so another plate barely does not fit. With only .41 units we are not maximized yet at 3d x 4d.

between what you are describing and I am envisioning is the extent to which the plates are allowed to 'hang out'.

And by the way, I now think that 32 was an over-estimate. We can cover the table with 23 plates!

In my crude drawing below, the blue shaded area shows a table that is just barely bigger than 2d x 3d (each line is r, so 2 lines equal d). This shows 12 plates as a row of 3 x 4. The plates do not overlap, and their centers are (barely) on the table, as per the OP. As you say, you might be able to get a little bit smaller by offsetting the rows, but I'll assume for now that that won't materially affect the answer. You also might want to quibble about the plates perched precariously in the corners - but you can get a flat, circular object to extend virtually 75% of its area over a corner of a flat table, and with plates on top they would definitely stay.

The drawing also shows a large, 3d x 4d 'table' outlined with a dashed line. It also shows that if the table were in fact just over 3d x 4d, you would be able to get a whole bunch more plates on there. However, I didn't realize until I sketched it, but you only have to grow the table in one direction, which would yield a table of 2d x 4d, depicted with dashed lines plus the one dark line.

If you had such a table, I assert that I'd be able to add an additional plate, number 13, by simply moving it over and nestling it between the 2 adjacent plates. This is why I think the table size discussed is far too big, this table can accomodate 13 plates and is just 8 square d units.

Finally, the pink plates show how I'd fill the extra space. Simple center each covering plate on the center of the space between each rank and file of plates, basically offset by 1/2 d from the bottom layer. In the 2d x 4d table you will need 8 of them to cover the gaps, plus the 15 on the bottom, giving you a grand total of 23. (Note that the pink plate in the bottom corner is simply for reference, and would not be part of the final 23).

And 23 is 32 (original postulate) backwards!

Edited February 4, 2009 by xucam

[Guest]

Erm, I don't mean to sound patronizing, but: you're still answering a different problem than we are.

The first part is to "find the biggest table on which we can find an arrangement of 12 plates so that no plate can be added without overlapping". If these plates are of diameter d, this problem is equivalent to "finding the biggest table that can be fully covered by 12 plates of diamter 2d". This is very different than asking "what's the biggest table on which I can not fit more than 12 plates without overlapping", which seems to be your interpretation of the problem.

The best answer people have come up with for that first part is a rectangle with sides d*sqrt(2) and d*12*sqrt(2) (factor 12 can be distributed on both sides, though, the 3 cases seem to be equivalent). This is already twice as big as 3d*4d.

The second part is: "how do we cover that table fully with as few plates as possible ?"

With a total area of at least 24d^2, and a plate area of pi*(d^2)/4, it is obvious that 31 is the absolute minimum we can come up with (and that's not considering *any* overlapping). And so far, the best arrangement that has been offered yields a result of 48 plates.

[HoustonHokie]

Perhaps this will help illustrate what we've been saying (I always like a good drawing ).

The image below shows a 3d x 4d table and an arrangement of 10 (red) plates which won't allow for any more. You can see my attempts to add (green) plates which always either overlap another (red) plate or the center of the (green) plate is not on the table. I've spaced the 6 central (red) plates at 1.35D horizontally & vertically, which makes the (green) plates in between overlap. Additionally, I've only allowed 0.17D between the top row of (red) plates and the top edge of the table, which prevents the (green) plates with centers right on the edge of the table from being placed without overlapping that row of (red) plates. [The interplate dimensions could actually be a little larger, but this is easier to see without high image quality.] With this arrangement, there is no way to get an 11th plate on the table, much less 12. So the table has to be enlarged, and PT's & CL's calculations in that regard have been quite helpful in determining the size of the table required. I hope this helps show what we've been trying to say.

[Guest]

Erm, I don't mean to sound patronizing, but: you're still answering a different problem than we are.

Not at all, I think that was obvious. Thanks to HH for the helpful diagram.

The first part is to "find the biggest table on which we can find an arrangement of 12 plates so that no plate can be added without overlapping". If these plates are of diameter d, this problem is equivalent to "finding the biggest table that can be fully covered by 12 plates of diamter 2d". This is very different than asking "what's the biggest table on which I can not fit more than 12 plates without overlapping", which seems to be your interpretation of the problem.

Nor do I mean to be patronizing, but I think mine is the more obvious interpretation of the problem. It isn't stated that you should find a maximally inefficient pattern to arrange the plates in the first place. I can easily add another plate to your table, I simply nudge one of the existing plates over, this is not excluded in the OP. This sounds trite, but it is the crux of the issue. I can add a plate without overlap or undue overhang, to your table.

The best answer people have come up with for that first part is a rectangle with sides d*sqrt(2) and d*12*sqrt(2) (factor 12 can be distributed on both sides, though, the 3 cases seem to be equivalent). This is already twice as big as 3d*4d.

2d x 4d, covered by 23 plates

The second part is: "how do we cover that table fully with as few plates as possible ?"

No kidding. I think it was obvious from my responses that I had the same approach, I just think your table from the first part is far too large.

Edited February 4, 2009 by xucam

[Guest]

Nor do I mean to be patronizing, but I think mine is the more obvious interpretation of the problem. It isn't stated that you should find a maximally inefficient pattern to arrange the plates in the first place. I can easily add another plate to your table, I simply nudge one of the existing plates over, this is not excluded in the OP. This sounds trite, but it is the crux of the issue. I can add a plate without overlap or undue overhang, to your table.

I won't make a call on which is the more obvious interpretation, but you clearly have a point there. This does pose an alternate part 1 of the problem. But can't that 2d*4d table hold 15 plates ? I'm getting lost here.

Edited February 4, 2009 by hellmake

[Guest]

I won't make a call on which is the more obvious interpretation, but you clearly have a point there. This does pose an alternate part 1 of the problem. But can't that 2d*4d table hold 15 plates ? I'm getting lost here.

Fair enough. Sorry.

Got lost with the restatements, but was saying the the maximum table size *approaches* that, because as you say, at 2d x 4d you can get 3 additional plates on. At a slightly smaller size (shrinking the 4d dimension) you can get 14 plates on by offsetting them, and just below that you can get only 12.

So more accurately

2d x (4d - X) where X is not specified.

[HoustonHokie]

It isn't stated that you should find a maximally inefficient pattern to arrange the plates in the first place.

No, but it is inferred.

The OP gives that 12 plates are on the table and no more can be placed without overlap. Then it asks how many plates are necessary to ensure that the table is covered later on. The ensure part of the OP is what makes us look for the maximally inefficient arrangement. We want to make sure that the waiter can cover the table with plates, no matter what the size, as long as it satisfies the original conditions of the OP (because, of course, the waiter doesn't know the size of tables in his own restaurant

).

I don't want to beat a dead horse, but another way to look at it is like this: The waiter comes to you and says, "I just placed 12 plates on my table and they don't overlap one another and I can't place any more without overlap. Now, I need to cover that table with plates and I don't know how many to order so that I have enough. How many plates do I need?" Being a good problem solver, you tell him, "Well, I don't know the exact dimensions of your table, so I don't know exactly how many you need - it could be anywhere from 12 to 48. So, if you get 48 plates, it will definitely be enough."

That's why I did the problem the way I did.

By the way, you'll notice that I said 12 was the minimum - that's because I've got an arrangement where 12 plates can cover a table that meets the OP requirements. Actually, I have 2 such arrangements.

And I'll throw this out there, too, for what it's worth. That 48 number only stands because the plates are not necessarily arranged in a 3x4 grid. I can cover a 4.25D x 5.66D table with only 45 plates. But I can't do the same for a 2x6 grid or a 1x12 row (yet).

[bonanova]

xucam,

See if one of these statements helps:

1. If you work with only a subset of OP-allowed cases, you have not ensured coverage.
   
2. To ensure coverage for all possible configurations, you have to cover the worst case.
   
3. If OP does not disallow a particular case, you can't rule it out.
   

[Prof. Templeton]

of the four plates was a pretty good proof. You can see the diagonal of the square it covers is 2d. Since we're calling our plates d=1, the square is sqrt2 by sqrt2. One plate on our original table sat on a square that was sqrt2 by sqrt2 so four plates are need to totally cover where one plate sat initially. 12 initial plates = 12*4 for coverage.

[Guest]

xucam,

See if one of these statements helps:

1. If you work with only a subset of OP-allowed cases, you have not ensured coverage.
   
2. To ensure coverage for all possible configurations, you have to cover the worst case.
   
3. If OP does not disallow a particular case, you can't rule it out.
   

All good suggestions.

1) Since the OP said you couldn't get another plate on the table, which you can by moving a plate with the 'large table' interpretation, I suggest it fails all three tests.

2) I did try to maximize the size of the table to include all OP-allowed cases - based on my interpretation.

3) I understand that mine is the minority opinion. At least we can ll agree that the world is flat.

To PT: You probably did have a good proof, I read through but confess I did not go back and study every post.

To HH: IBID #2, I did consider the 'ensure' clause of the OP, and therefore tried to maximize the table size to one where 12 but not 13 plates could fit. 'nuff said.

[Prof. Templeton]

To PT: You probably did have a good proof, I read through but confess I did not go back and study every post.

My reply was directed at bn, who said we still need a proof for 48 plates when he edited the post description.

[HoustonHokie]

My reply was directed at bn, who said we still need a proof for 48 plates when he edited the post description.

Yes we do, because we need to make sure that the coverage is the most effecient possible.

In the square arrangement of plates you proposed, each circle effectively covers a square with an area equal to 0.5D units². There is another way to arrange the plates - like a honeycomb - where each circle effectively covers a hexagon with an area equal to 0.65D units². On the face of it, that would seem like the better arrangement, because each circle covers more area. But, because they have to be offset from one another instead of stacking horizontally & vertically, some of that efficiency is lost in this particular case. Also, it just happens that the exterior dimensions of the table are multiples of the square arrangement, but not multiples of any of the hexagonal arrangement. But using the hexagonal arrangement is why I can cover the 5.66D by 4.25D table with ony 45 plates. It just doesn't work for the other two possibilities because you end up with partial plates at the edges - at least you do when the plates are oriented "square" with the table. There may be a solution for the other two tables that uses less than 48 with an appropriate rotation. I don't see it yet, but I haven't played with it enough to know for sure. If I can find that, and all other possible tables are smaller than those three, the solution won't be 48 anymore. And that's what bn is driving at with the proof request, I believe...

[Guest]

Why don't you just take like 25 plates, smash em up into a bunch of little pieces, then cover the table in "plate" dust. Because technically, you are covering it with plates.... just in a smaller... non usable size.

[bonanova]

We've come from what seems at first to be an intractable problem and found some very nice results. Since the table edges seem like a separate issue, let's separate the rectangular table case from the infinite plane case. One has edge effects, the other does not.

Two results, I think.

1. For the 12-plate finite table problem, 4x is agreed by all to be sufficient to cover the table.
   xucam argues 4x might be overkill but agrees it's sufficient.
   PT gives a proof using a 2x2 overlapping plates that tile that table.
   See below for a generalization of the table problem.
   
   
   
2. For the infinite plane, I postulate that 4x is both sufficient and necessary.
   By 4x I mean comparing two things:
   (a) the sparsest of all configurations that do not permit adding a plate without overlap and
   (b) the minimal configuration that covers completely - which HH has found [but not amenable to a rectangular boundary].
   

It seems we're an inch away from two nice general proofs. So ...

1. To generalize the finite table problem, let's amend the OP to say that N plates were used initially.
   This precludes inspection of specific table dimensions.
   
   
   
2. For the infinite plane problem, HH can finish his hex packing analysis to obtain a very elegant result.
   

[Guest]

(b) the minimal configuration that covers completely - which HH has found [but not amenable to a rectangular boundary].

Just noting that the configuration offered by Prof T. in post 24 (on page 2) covers a a square of side d*sqrt(2) with 4 plates.

This means that, with 4 plates (total area = 4*pi*(d/2)^2 = pi*d^2) cover a surface of 2*d^2. The ratio of "plate surface"/"table surface covered" is thus pi/2.

Now if you look at HH's configuration, take each individual d*d square : it is covered by 1 plate and 4 fourths of plates. That is 2 plates (total area pi/2 * d^2) covering a surface of d^2. You guessed it, the ratio is the same. Actually, if you take Prof T's arrangment and put a couple of those next to each other.. you'll notice that the arrangements are basically the same.

Therefore, we can say that table dimensions which are multiples of d*sqrt(2) allow to use the optimal packing of the "infinite plane problem" (provided this is, in fact, the optimal packing... which we kinda suspect to be the case).

The d*sqrt(2) arrangement is also very useful for part 1, because each of these squares represents the space secured by one of the initial plates.

[HoustonHokie]

I'm going to put aside the hexagonal packing stuff for a while and try to tackle these proofs.

The finite solution problem is most easily dealt with when the plates are arranged in an n x 1 row on the table initially. And, to further simplify the problem, let's consider that a single plate is on the table. We'll work from there to n x 1, and eventually to any rectangular grid. First, we need to define the maximum table which satisfies the OP conditions.

To start with, let's consider that the table could have any shape. The conditions on placing a second plate require:

1. Not overlapping the first plate, and

2. Not having the center of the new plate off of the table.

The first condition requires the center of the second plate to be at least one radius from the edge of the original plate. The second condition requires the edge of the table to extend to the center of the second plate. Therefore, in order to prevent another plate from being placed on the table, the edge of the table must be less than one plate radius from the edge of the plate. Tracing a path around the edge of the plate exactly one radius away from it's edge defines another circle with a radius equal to twice that of the plate, and also defines the largest table of any shape meeting the OP conditions.

But our table was specified in the OP as being rectangular. So, we need to define the largest rectangle with its furthest edge one radius away from the plate. Any rectangle inscribed in the circular table previously defined will meet these conditions, but the largest such rectangle is actually a square. It's area is 2D units² and its sides measure √2D. Thus we have defined the largest rectangular table meeting the OP conditions with n=1. Let's call this table the unit table.

To expand to other values of n, let's consider how we might construct a table with n plates. The simplest means of construction would be to place n unit tables side by side in an n x 1 rectangular grid. This would allow for the construction of a table for any value of n, even prime numbers, which become problematic in an a x b grid. But let's check and see if this means of construction is, in fact, creating the largest table meeting the OP conditions for n plates. The means to checking this is to plot the circular boundary conditions for each of the n plates (the circular table) we defined earlier. If the new table is entirely contained within the composite boundary for n plates, we can say it meets the OP conditions. Because each of the individual unit tables is contained within the boundary for the plate it holds and the composite boundary is simply the intersection of multiple individual boundaries, we can say with certainty that the new n x 1 table will be contained within the composite boundary, and the table will meet the OP conditions. But is it the largest such table? Consider what happens if we increase the dimensions. First, consider an increase in the y-direction. An increase in the y-direction can only be accommodated by a corresponding decrease in the x-direction and compression of the plate spacing, or else the table would exceed the composite boundary. Similarly, an increase in the x-direction can only be accommodated by a corresponding decrease in the y-direction and expansion of the plate spacing. Additionally, an increase in the x-dimension is further limited because once the spacing of the plates reaches 2D from center-to-center of adjacent plates, the table will not meet OP conditions. Either dimensional change, even if it results in a table meeting OP conditions, will result in a table with less area than one made of n x 1 unit tables. So we can say that a table made by placing n unit tables side by side defines the maximum table for n plates.

I won't go through it all here, but we can expand this proof for non-prime values of n to show that a table made by placing n unit tables in an a x b rectangular grid (where a and b are factors of n and a x b = n) also creates a maximum table for n plates.

I think this discussion combined with PT's proof of 4 plates covering a unit table proves the general solution is 4n.

As far as the infinite plane/hexagonal packing goes, I think that it may not be relevant any more. My proof above showed that a maximum table can be acheived with an n x 1 arrangement of plates, and so as n approaches infinity, you don't need an infinite plane, but something closer to an infinite line (in that it is bound in one direction but not the other). Hexagonal packing only proves more efficient than square packing in configurations where the plane expands in both the x- and y-directions, so it will never provide the minimum coverage for all tables satisfying the OP conditions.

At HoustonHokie's Hexagonal Hamburgers and Hash, deep in the Heart of Texas, all the tables are hexagons (except for the big circular table in the middle), and the answer might be, well, a little bit different.

[bonanova]

Yeah, I think the pieces are all there. Great work.

Choose one ...

Puzzles decrease industrial productivity and distract students from study.

Puzzles are like a workout: nothing useful is done, but useful work becomes easier.

Here are two nice solutions, for which I do not claim credit.

[Guy Kindler and Peter Winkler]

Place enough plates that another cannot be added without overlap

1. Double the radius of the plates, covering the table.
   • The centers didn't move, so none of them fell off.
     
   • If the table weren't covered, the uncovered area would have admitted a plate before doubling.
     

[*]Place 4 instances of the covered table into a 2x2 grid.

[*]Coalesce the tables and shrink the linear scale by a factor 2.

A table the size of the original is covered with 4x plates.

Create a hexagonal tiling of the plane

[*]Inscribe a circle in every 3rd hexagon in such a way the that circles are maximally spaced. *

Increase their diameter by an infinitesimal amount.

No circles of that diameter can be added to the plane without overlap. This is the plane's worst case.

[*]Circumscribe a circle about every hexagon. *

The plane is optimally covered, using 3x circles, 4/3 larger in area.

[*]Normalize diameters to those of worst case by a 3/4 area scaling.

The density [circles/unit area] of covering circles is 4x the worst case density.

* HH has shown tilings 1 and 2.

[Prime]

Yeah, I think the pieces are all there. Great work.

Choose one ...

Puzzles decrease industrial productivity and distract students from study.

Puzzles are like a workout: nothing useful is done, but useful work becomes easier.

Here are two nice solutions, for which I do not claim credit.

[Guy Kindler and Peter Winkler]

Place enough plates that another cannot be added without overlap

1. Double the radius of the plates, covering the table.
   • The centers didn't move, so none of them fell off.
     
   • If the table weren't covered, the uncovered area would have admitted a plate before doubling.
     

[*]Place 4 instances of the covered table into a 2x2 grid.

[*]Coalesce the tables and shrink the linear scale by a factor 2.

A table the size of the original is covered with 4x plates.

Create a hexagonal tiling of the plane

[*]Inscribe a circle in every 3rd hexagon in such a way the that circles are maximally spaced. *

Increase their diameter by an infinitesimal amount.

No circles of that diameter can be added to the plane without overlap. This is the plane's worst case.

[*]Circumscribe a circle about every hexagon. *

The plane is optimally covered, using 3x circles, 4/3 larger in area.

[*]Normalize diameters to those of worst case by a 3/4 area scaling.

The density [circles/unit area] of covering circles is 4x the worst case density.

* HH has shown tilings 1 and 2.

With redefined conditions in the OP, allowing the plates to overhang the edges of the table, that seems even more as a waste of expensive china.

Of course, 4 times the plates is always enough, but where is the proof that we can't always do better than that?

Here is a simple illustration.

Allign a plate with its center on the corner of the table and place the remaining plates as shown:

The red extra plates and the yellow intervenning spaces add up to 20 areas. Together with the original plates that makes 32.

However, that is far from the optimal placement and you could fit more than 12 non-overlapping plates on that table, even if the extra plates in red could not fit as shown. (That means that a table that could fit 12 non-overlapping plates at the most would be even smaller, thus it could be possible to use even less plates to cover it completely.)

Edited February 8, 2009 by Prime