Circles covering a rectangle

[bonanova]

This is another puzzle where precise wording is important -- I'll try to get it right, but if anything is unclear, please ask ... I'll start out by saying that all the circles in this puzzle have the same radius, the aspect ratio of the rectangle is not specified and does not matter, and its size, relative to the size of the circles is only indirectly implied. Only the constraints stated in the puzzle should be assumed.

• I've drawn 17 circles that at least partially overlap a rectangle.
• Their centers all lie within the rectangle.
• None of the circles overlap or even touch any of the other circles.
• There is no room for an 18th circle to be added to the group.

That is, the circles are drawn in such a way that even though there is space between them, it is impossible to draw another circle whose center lies within the rectangle that does not at least partially overlap one of the first 17 circles. That is all you know about the relative sizes of things. And it is enough information to answer the following question:

First, let's erase the circles that I drew. Then I will paint the rectangle red and give you a large supply of opaque white circles. What is the smallest number of circles you will need to completely cover the rectangle? (so that no red will be showing.) The centers of the circles, again, must lie within the rectangle, but now, of course, the circles can overlap each other,

Edit: The puzzle can be solved as stated, but in order to guarantee the solution is the absolute smallest number, the following constraint is added to the original placement: The 17 circles were drawn as densely as possible without overlap. Thanks to @Molly Mae for raising this point.

[Izzy]

Hmm. The first thing we want to do is find the largest such rectangle that can be filled with 17 circles in such a way. We know that a square has maximum area out of rectangles with the same perimeter. So, to maximize the area, I want to try to arrange the circles as closely to a square as possible. 

Consider the following pattern (without the weird double spacing that completely distorts it.) Without loss of generality, let the circles have radius 1. 

O      O      O

|O      O      O      O|

|    O      O      O     |

|O      O      O      O|

|  _  O ___  O  _  O  |

 

Draw the circles so that two adjacent circles on the same line have distance exactly 2 between them.  Also, let the distance between two circles that are above and below each other also be 2. Draw the rectangle so that each side is tangent to the outer circles. (I filled some of it in, you get the idea. ) Then, the area of this rectangle is 14 by 10 = 140 units^2. The area of each one of our circles is pi. If we could be perfectly efficient with our circles (we can't), it would take 140/pi = ~45 circles to cover our rectangle. Of course, this won't perfectly overlap our rectangle, but at least we have a lower bound. 

I am not sure of the optimal way to cover a region with circles. If you start with the top corner being the edge of a circle (like this: https://i.stack.imgur.com/WCSIr.png ), it would take 8 circles to cover the first row  ( the ceiling of 14 / sqrt(2)) and 6 to cover the first column (the ceiling of 10/sqrt(2)), leading to 48 total circles, which is fairly close to the previous lower bound! 

[Molly Mae]

On 1/22/2018 at 5:40 PM, bonanova said:

This is another puzzle where precise wording is important -- I'll try to get it right, but if anything is unclear, please ask ... I'll start out by saying that all the circles in this puzzle have the same radius, the aspect ratio of the rectangle is not specified and does not matter, and its size, relative to the size of the circles is only indirectly implied. Only the constraints stated in the puzzle should be assumed.

• I've drawn 17 circles that at least partially overlap a rectangle.
• Their centers all lie within the rectangle.
• None of the circles overlap or even touch any of the other circles.
• There is no room for an 18th circle to be added to the group.

That is, the circles are drawn in such a way that even though there is space between them, it is impossible to draw another circle whose center lies within the rectangle that does not at least partially overlap one of the first 17 circles. That is all you know about the relative sizes of things. And it is enough information to answer the following question:

First, let's erase the circles that I drew. Then I will paint the rectangle red and give you a large supply of opaque white circles. What is the smallest number of circles you will need to completely cover the rectangle? (so that no red will be showing.) The centers of the circles, again, must lie within the rectangle, but now, of course, the circles can overlap each other.

Clarifying question: Is the rectangle as large as possible meeting those constraints?  Or as small as possible meeting those constraints?  I feel like the number of circles required depends on that, but maybe it doesn't.

[bonanova]

@Molly Mae Fair question.

Spoiler

The relative size of rectangle and circles given in the OP is limited to the statement that 17 non-overlapping circles are on the rectangle, and it's not possible to add another circle that does not overlap one of them. It doesn't speak to whether the circles are as dense as possible (or as sparse as possible) for that statement to be true.

The 17 circles possibly could be moved together a bit without overlap, (and the rectangle could then be smaller, requiring fewer circles to cover it) or they possibly could be spread apart somewhat without permitting an 18th circle that does not overlap (and the rectangle might then be larger and require more circles to cover it.) The OP only says that I drew a rectangle, and I did put 17 circles on it (densely or sparsely) and another circle cannot be added without overlap.

Since that's all that we know then, as you point out, we don't have enough info to state the absolute minimum number of covering circles.

Two options here. (1) leave it as is but instead ask "given only what we know, what number of plates will cover the rectangle, where removing any one of them will expose part of the rectangle?" or (2) add to the OP: "The 17 circles were drawn as densely as possible without overlap." The second option allows the question in the OP to stay as is, asking for the absolute minimum number of circles to cover the rectangle.

I like option (2), and I'll amend the OP

Good question. Thanks.

 

Edited January 27, 2018 by bonanova
Stating things more clearly

[CaptainEd]

Here's a different rectangle that may work:

 

Place a row of 6 circles, then a row of 5, then a row of 6, as shown in the top figure in the accompanying PDF file. Separate them by a very small epsilon.

They fit inside the rectangle with no room for another circle. The length is 10r (plus a few epsilon), and the height is roughly 3.464 r.

Next, to fully paint this rectangle: without epsilons, we could string out 5 circles to exactly cover the top edge, but with epsilons between them, we need 6. So divide the top edge by 6, and place the circles so that each one covers exactly one chord (10r/6), as shown in the bottom figure. Then place 7 circles as shown, and 6 more. The heights add up to more than 3.464 r, so 19 circles suffice.

Pennies and Rectangle.pdf

Edited November 18, 2018 by CaptainEd

[plainglazed]

Spoiler fwiw

Spoiler

Approached this kinda from what I learned from another bonanova puzzle (which happens to be my favorite of all time and what really got me hooked here)

by looking at the rectangle in somewhat of a degenerative case were it approaches a line segment of 16 circle diameters.  That is, if the circle's diameter is said to be one unit, a rectangle which is just over sixteen units long and infinitesimally wide I think satisfies the OP.  Sixteen unit circles can cover a sixteen unit line segment so maybe seventeen circles would be the minimum to cover the above described rectangle.

Hole in a Sphere

 

 

[CaptainEd]

Oooh, sounds like you’ve nailed it, plainglazed.