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.

[Prof. Templeton]

@ HoustonHokie

My previous lay-out would indeed need to be

5.66 by 6.66

Forgot to optimize around the perimiter.

Plates are in a 4 x 3 grid

.41 in between so you can't fit one in diagonally

.92 from plate to edge for same reason.

Edited February 2, 2009 by Prof. Templeton

[Prof. Templeton]

I would argue that that is the optimal size of the table provided that overhang is allowed, which HoustonHokie does not seem to account for.

He's trying to find the size of the initial table first, then worry about covering it.

[Guest]

He's trying to find the size of the initial table first, then worry about covering it.

I understand that.

that HoustonHokie's tables do not meet the initial criteria because, for instance, on the table measuring 6.5 x 5.33 I could place a thirteenth plate on the table whose center is directly over the lower left corner of the table, which is allowed if overhang is acceptable.

[Guest]

@ HoustonHokie

My previous lay-out would indeed need to be

5.66 by 6.66

Forgot to optimize around the perimiter.

Plates are in a 4 x 3 grid

.41 in between so you can't fit one in diagonally

.92 from plate to edge for same reason.

I agree with

your .41 between the plates, but I think your plate-to-edge is now too large.

I used 1/2 from plate to edge. (for dimensions of 6.24 x 4.83) Going back now to determine why.

[Prof. Templeton]

I agree with

your .41 between the plates, but I think your plate-to-edge is now too large.

I used 1/2 from plate to edge. (for dimensions of 6.24 x 4.83) Going back now to determine why.

Yeah

.7 from plate to edge.

[Prof. Templeton]

I understand that.

that HoustonHokie's tables do not meet the initial criteria because, for instance, on the table measuring 6.5 x 5.33 I could place a thirteenth plate on the table whose center is directly over the lower left corner of the table, which is allowed if overhang is acceptable.

I don't think overhang is allowed for the initial 12 plates, only for the covering.

[Izzy]

I say "ish" because it's a bit sloppy, and I'm not sure all the plates are exactly the same size. But... yeah, if done properly it would definitely be in the 26-30 range.

[Guest]

I got

40

Edited February 3, 2009 by Kevin_3.1415

[Prof. Templeton]

I say "ish" because it's a bit sloppy, and I'm not sure all the plates are exactly the same size. But... yeah, if done properly it would definitely be in the 26-30 range.

I think your table needs to be bigger. If I understand the OP correctly, the table should have plates spread out so that 1 more plate could not fit, but just barely.

I think there has to be just slightly less then .41 between the plates and the plates are just slightly less then .7 from the edge of the table (depending on the lay-out) if we use a plate diameter of 1 that is. Otherwise we could have a 1 x 12 table and about 28 plates would definitely cover it.

[Izzy]

I think your table needs to be bigger. If I understand the OP correctly, the table should have plates spread out so that 1 more plate could not fit, but just barely.

All the OP said was that the plates had to be close enough together so another plate couldn't fit. *shrugs*

[bonanova]

All the OP said was that the plates had to be close enough together so another plate couldn't fit. *shrugs*

What PT is saying is that you've drawn the plates closer together than the OP says they have to be.

Or, that the OP allows the table to be bigger than you've drawn it.

That is, if you want to prove that a certain number of plates is enough to cover a table [any table] consistent with the OP,

then you have to deal with the most difficult case that the OP permits.

Putting it another way, if N plates cover the table you drew, but won't cover a bigger table that is still consistent with the OP,

then you haven't proved that N guarantees coverage. That is, a counter-example [bigger table] exists for which N fails.

But if N suffices for the worst-case [largest possible] table, then you've proved that N will succeed for any table.

The OP has the word ensure in it.

[HoustonHokie]

Yeah

.7 from plate to edge.

With that in mind, it looks like the biggest table would be

2.41 x 17.97, which would allow a single row of plates to be placed at 0.41 between plates and 0.70 from plate to edge. The total area of this arrangement is 43.3, which is larger than the 35.0 achievable with a 5.25 x 6.66 table or the three arrangements I proposed earlier. Now, the question is whether largest area = most plates, or if there could be something in a more compact arrangement that would be more difficult to cover.

[HoustonHokie]

I think the answer

somewhere between 48 and 60. Here's a picture of the optimal covering for four plates. The grey square is sqrt2 by sqrt2 (d=1). Layed out in a rectangle of 4 by 3 squares we could cover a table 5.657 by 4.243. But I think this table could be a little over that and still fit the description of the OP. Of course the OP leaves the size of the table up to us, so maybe we need to find the optimal sized table first.

With that in mind, it looks like the biggest table would be

2.41 x 17.97, which would allow a single row of plates to be placed at 0.41 between plates and 0.70 from plate to edge. The total area of this arrangement is 43.3, which is larger than the 35.0 achievable with a 5.25 x 6.66 table or the three arrangements I proposed earlier. Now, the question is whether largest area = most plates, or if there could be something in a more compact arrangement that would be more difficult to cover.

Combining this table size with PT's optimal coverage arrangement, I get:

104 plates are required to completely cover the 2.41 x 17.97 table. If that's the minimum number of plates needed to cover the maximum size table, the problem is solved. Of course, I said if...

[HoustonHokie]

Combining this table size with PT's optimal coverage arrangement, I get:

104 plates are required to completely cover the 2.41 x 17.97 table. If that's the minimum number of plates needed to cover the maximum size table, the problem is solved. Of course, I said if...

Or I could make it a little better...

Now I'm down to 86 plates with an even more optimal arrangement of the plates. Remember I said if...

Note: there are 4 plates in the drawing that violate an OP condition that their centers be on the table. They could be moved so that their centers are on the table and still provide the coverage that necessitates their inclusion in the first place. They would just overlap more...

[bonanova]

Combining this table size with PT's optimal coverage arrangement, I get:

104 plates are required to completely cover the 2.41 x 17.97 table. If that's the minimum number of plates needed to cover the maximum size table, the problem is solved. Of course, I said if...

Sorry if the OP is confusing on the overlap / overhang question.

I'll be more specific here.

Plates are allowed to overhang the table, just so long as the center of the plate lies on the table.

That is true for the original 12 plate configuration as well as the completely covering case.

That is, no plate can be added without overlapping another plate, even tho it might overhang the table.

This means your table could shrink by a plate radius on each edge.

[Guest]

Sorry if the OP is confusing on the overlap / overhang question.

I'll be more specific here.

Plates are allowed to overhang the table, just so long as the center of the plate lies on the table.

That is true for the original 12 plate configuration as well as the completely covering case.

That is, no plate can be added without overlapping another plate, even tho it might overhang the table.

This means your table could shrink by a plate radius on each edge.

The answers have ranged wildly, and mine is no exception. I say the answer is 32.

The OP said 12 plates on the table, no more can be added without violating either the overlap or center-on-the-table rule (AKA gravity!)

If the plate diameter is 1 unit, I think the table size approaches 3 x 4 units. With the plates teetering on their centers, you could have a table as small as 2 x 3 units, or 1 x 6 units. The table can grow almost 1 unit in each direction before another plate can be added - in fact it must be smaller, because at some point you can offset the rows for a more efficient packing.

I arrange my plates as 4 x 5 plates along the table, with a single plate in the center of where each set of 4 lower plates meet. That is 20 on the bottom and 12 covering holes on the top.

32. Yes, that's the ticket!

[Prof. Templeton]

Sorry if the OP is confusing on the overlap / overhang question.

I'll be more specific here.

Plates are allowed to overhang the table, just so long as the center of the plate lies on the table.

That is true for the original 12 plate configuration as well as the completely covering case.

That is, no plate can be added without overlapping another plate, even tho it might overhang the table.

This means your table could shrink by a plate radius on each edge.

the table is now 1.41 x 16.97. 4 plates cover 1.41 x 1.41 so we would need 48 plates.

[Guest]

i think it will only take 18

[HoustonHokie]

the table is now 1.41 x 16.97. 4 plates cover 1.41 x 1.41 so we would need 48 plates.

A quick check reveals that

48 plates will cover all 3 table sizes: 1.41 x 16.97; 2.83 x 8.49; 4.25 x 5.66. All require exactly 48 plates, so it doesn't matter how the table is sized, except that it conform to the OP requirements - now that we know what they are

[Izzy]

Now I'm down to 86 plates with an even more optimal arrangement of the plates. Remember I said if...

Note: there are 4 plates in the drawing that violate an OP condition that their centers be on the table. They could be moved so that their centers are on the table and still provide the coverage that necessitates their inclusion in the first place. They would just overlap more...

Dude, how do you do it so neatly?

*edit* Grah, the image didn't show. But you know what I'm talking about.

Edited February 3, 2009 by Izzy

[Prof. Templeton]

A quick check reveals that

48 plates will cover all 3 table sizes: 1.41 x 16.97; 2.83 x 8.49; 4.25 x 5.66. All require exactly 48 plates, so it doesn't matter how the table is sized, except that it conform to the OP requirements - now that we know what they are

I had a feeling we were making it harder then was intended.

[Guest]

come to think of it i may take more than 18 plates to cover the table maybe about 28

[Guest]

Since the problem seems to be "what is the minimal number of plates that, regardless of the size of the table (provided it still can meet the requirement of the 12 plates laid out in the OP) will be sufficient to cover it fully?", all I can come up with is :

If the radius of a plate is 1, we can easily see that

width= 2*sqrt(2) - epsilon ~= 2.83

and height = 24*sqrt(2) ~= 33.94

are acceptable dimensions for the table (that is, we can lay 12 plates on it and be in a situation where no new plate can be added without falling or overlapping).

The surface of this table being 96 square units, and the surface of a plate being pi square units, any answer below 30 wouldn't even make sense.

As the Professor pointed out, 4 plates can cover one of these 2*sqrt(2) - sided squares... and I'm pretty sure that covering is optimal for any arrangement of such squares... which works our total out to 48 (for all 3 arrangements of 12 such squares).

Question : can we find another arrangement of the 12 "initial" plates that leads to a bigger (or less manageable) table ? I doubt that.

It's like asking "what's the biggest table that can be fully covered with 12 plates of radius 2 ?" If we go with the professor's covering, we're back to a table of 96 square units.

If we can't, 31 is our absolute minimum, and 48 seems like a really good arrangment.

[Guest]

I have a table size of 5.5d x 4.33d (5* sqrt(3)/2) that satisfies the initial conditions, but I can't figure out how to cover it with less than 51 plates.

I get that table from HoustonHokie's 6.5dx5.33d table (see post 23). If you subtract 1/2 d from each edge, I don't think you can fit anymore on without falling off.

Btw, where did 4.25 x 5.66 come from?

Edited February 3, 2009 by voltage

[Prof. Templeton]

I have a table size of 5.5d x 4.33d (5* sqrt(3)/2) that satisfies the initial conditions, but I can't figure out how to cover it with less than 51 plates

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.