Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
TRUE OR FALSE
Suppose that a rectangle in $R^{2}$ can be covered by (allowing overlaps) $25$ discs of radius $1$, then it can also be covered by $101$ discs of radius $0.5$.
Of course, though it is a true or false question, I would like the logic on it and possible a general proof.
The answer is true but I don't see any specific logic.
P.S. The question is from the entrance exam 2012 to graduate program at TIFR, Mumbai.
This is really funny - but this is not actually a math question.
Here's the trick: If 25 circles can cover the full rectangle, then 25 circles of half-radius can cover the half-scale rectangle (i.e. cutting both side lengths in half). Tile this 4 times, and you see that yes, 100 half-radius circles can cover the whole rectangle.
I just realized that there are 101 circles. I suppose you wear the 101$^{st}$ as a hat.
Well, wouldn't it actually take fewer in most cases?
There are two basic arrangements of overlapping circles that, between them, encompasses a solid area greater than that of each individual circle. The orthogonal arrangement is easier to visualize especially relating to a rectangle, so we'll use it. One iteration of this arrangement of circles takes five of them; four in a square with their edges touching, and one in the middle filling the gap in the center.
One iteration would completely cover a square 2R on a side (it can be no wider than the center circle, of diameter 2R, or some of the square would be outside the addjacent points of the outer four circles). If you needed to cover a rectangle composed of two of these squares, 2R*4R, you'd need two iterations of the pattern, but (here's the kicker) two of the circles from each iteration are congruent with one other, and are redundant; 5 circles of radius R cover a 2R*2R square, but only 8 are needed for 2R*4R, not 10. Double the area again, to a square 4R*4R, and you need 4 iterations of the original shape (2 of the rectangular 7-circle pattern), but now all four iterations have a circle that is congruent with one from the other three, as well as another circle congruent with one other iteration; that's 7 circles out of 20 that are redundant so you only need 13.
The number of orthogonally-patterned circles of radius r that are required to cover a rectangle of area n*m where n and m are even multiples of r is the sum of two related products of n and m; to cover each dimension of the rectangle with circles, you need one more circle per dimension than half the number of radii in the dimension, so the first set of orthogonal circles is the product of those two quantities. Then, the second set fills in the gaps, and requires the product of half the number of circles as there are radii in each dimension. Thus, $N(r,n,m) = (n/2r+1)(m/2r+1) + nm/4r$. Halve the radius and you find that $N(r/2,n,m) = (n/r+1)(m/r+1) + nm/2r$, and if you instead double the dimensions you'll find that $N(r/2,n,m) = N(r,2n,2m)$.
Working backwards with this formula, a rectangle that requires 25 circles of radius r would actually be a square 6r on a side; $N(r, 6r, 6r) = (6r/2r + 1)(6r/2r + 1) + (6r/2r)(6r/2r) = 4^2 + 3^2 = 25$. Halving the radius of the circles, we'd need $N(r/2, 6r, 6r) = N(r,12r,12r) = 7^2 + 6^2 = 85$. That's one extreme; the other is a rectangle (2r*16r), using a variation of the coverage pattern where one circle covers each short end and the remainder of the shape is filled in with the normal pattern. The number of circles in that case reduces to the very simple equation $N(r,2r,2xr) = 3x+1$, which when solved for x=8 is 25. Halve r, and the most efficient pattern goes back to the one stated above, so $N(r/2, 2r, 16r) = N(r,4r, 32r) = 3*9 + 2*16 = 59$.
So, while it would take more than double the number of circles when the radius is halved, it would never take 4x the circles. So, the answer to the question as stated is "true"; a rectangle that requires 25 discs of radius $r$ to cover with overlap can be covered with 100 discs of radius $r/2$; in fact you could cover a larger rectangle with this many.
TRUE. Here is a sketch of my proof:
We try to find the largest rectangle that can be covered by 25 discs of radius 1, and then see how many discs of radius 0.5 are needed to cover it. Now, given one disc of radius 1, the largest rectangle possible such that it is completely covered by the disc is one where the given disc will be the circumcircle of the rectangle (please draw the figure yourself).
Let the length and breadth of this rectangle be a & b => Area of rect=ab. Also, since the diagonal of the rectangle is the diameter(=2) of the disc we get, sqrt(a^2+b^2)=2 i.e. a^2+b^2=4. Now, we want to maximize (ab), subject to the condition (a^2+b^2-4)=0. Using Lagrange's Multiplier Method we get ab is max. when a=b=sqrt(2). Thus, Area of largest rect. that can be covered by one disc=ab=2.
We have 25 discs of radius 1, thus 25 subrectangles with area 2 will form the largest rectangle that can be covered by 25 discs of radius 1.
=>Area of largest rect. that can be covered by 25 discs of radius 1=25x2=50.
Now we apply the same procedure for discs of radius 0.5 to find the area of the largest rectangle that can be covered by one disc of radius 0.5. Here we get a=b=1/sqrt(2). Thus, area of each subrect.=ab=0.5
Hence, no. of subrectangles required to cover a rect. of area 50=100. Thus, no. of discs of radius 0.5 required to cover rect of area 50 is 100 (since each disc will completely cover one subrect).
=> 101 discs of radius 0.5 will also cover the rectangle.
