13 plates puzzle

[bonanova]

Plates on a table

This may not be a chestnut, but it should be. I've seen it a couple places. If you haven't seen it, work it out before looking.

13 plates, but no more than 13, can be placed on a dinner table such that no two of them touch. How many plates does it take to completely cover the table?

You may assume the plates are identical perfect circles; the table is a perfect rectangle; the center of every plate lies within the table's perimeter, so that it will not fall; and completely cover means completely obscure the table from view looking from above.

The answer is 52.

Double the diameter of the plates. The table is [just] covered. If a single point were not covered, another plate could have been centered there. Halve all the dimensions [plates and table]. Place four replicas 2x2 and coalesce them.

This works for any number, of course. But saying N plates might lead to a lucky guess of 4N.
_________________
_{Vidi, vici, veni.}

[groza528]

Are the initial 13 plates permitted to hang over the edge?

[Quailman]

[Zag]

I split out this puzzle while it is under discussion, since I don't want to put a lot of discussion in the chestnuts thread.

I don't know about a table that just fits 13 plates, but I think it is pretty clear that the 4N solution is not correct. Consider this arrangement -- it is pretty clear that you can finish covering the table with a lot fewer than 32 plates. Just 10 more will plug up all the holes, so you can cover it with 18 plates

[Chuck]

It could be a very narrow table with the 13 plates in a straight line.

[Jack_Ian]

If it's rewritten to say "How many plates does it take to guarantee completely covering the table?", then the solution given should work. It should also work for non-rectangular tables.

Something like…

If the maximum number identical and perfectly circular plates that you can place on a table, such that no two plates touch, is N. Then how many plates would you need to ensure completely obscuring the tabletop when seen from above?

[bonanova]

Yes, the description of the original plates is wrong. Create a hexagonal tiling of the plane.

Case 1: dense original plates.
Center an inscribing plate on each tile. [Decrease the plate diameter by an infinitessimal amount if you wish, so they do not touch.] Increase the plate diameter so they circumscribe the tiles. The plane is covered. Now shrink the plane so the plates become original size. The area ratio of circum- to in-scribing circles is 4/3. So here a 4/3 density increase suffices.

Case 2: sparse original plates.
Place an inscribing plate, regularly, on only 1/3 of the hex tiles. [Increase the plate diameter by an infinitessimal amount if you wish.] This is the sparsest layout that does not admit another non-touching plate. Here, by comparison to the first case, a fourfold density increase is needed.

Thus for any initial layout, 4/3 x is necessary, while 4 x is sufficient. Further reduction might accrue when going from the plane to a table [end effects.]

The OP thus needs to carry the sense that the sparsest original layout may have occurred: "I've just placed 13 plates on a table in such a way that another non-touching plate cannot be added. How many plates are required to ensure the table is completely covered?"
_________________
_{Vidi, vici, veni.}

[ralphmerridew]

Does the "sparse" possibility also work on very small numbers of plates? (For example, 1 plate can block a circular table with diameter 1.99, but I think it takes 7 plates to completely cover the table; can that be tweaked to a rectangular table?)

[ChickenMarengo]

It can't be tweaked to a rectangular table. You can prove it like this:

Suppose you have a rectangular table with n plates on it, and nowhere to add another plate without touching one already there.

Divide the table into n regions, so that each point is in the same region as the nearest centre-of-a-plate.

Replace all the plates with ones of double the radius. Each larger plate now covers the region containing its centre. If it didn't, then the region contains a point more than 2r from the nearest centre-of-a-plate, so an extra plate could have been placed there to start with.

So between them the larger plates cover the table.

Shrink the table and plates down by a factor of 2, and make 4 copies of the table. Assemble these into a rectangle the same size as the original table, and covered by 4n plates of the original size.

This works for a rectangle, or any other region with can be divided into 4 congruent regions, each similar to itself.

[PuzzleScot]

I think you may have misstated the original puzzle (since you suspect it should be 'a chestnut').

I believe the original arrangement is that N plates are arranged on a table so that no more plates can be placed without touching another.

This gives a more mathematically sound answer, so I'll let you hve a go at this version before publishing the answer.

[bonanova]

[Jack_Ian]

Remember to include this in your general solution.

[PuzzleScot]