Intereting Posts

Effective Upper Bound for the Number of Prime Divisors
How to project a n-dimensional point onto a 2-D subspace?
Please correct my answer (Probability)
Show that every graph $G$ has a bipartite subgraph with at least half of the edges of $G$
Show that 2S = S for all infinite sets
For the Fibonacci numbers, show for all $n$: $F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$
Why should I go on and differentiate this?
how does expectation maximization work?
Volume of a pyramid as a determinant?
Finite index subgroups of a virtually abelian group
Are there prime gaps of every size?
How to factor the ideal $(65537)$ in $\mathbb Z$?
Why call this a spectral projection?
Difference between external and internal direct product?
Easy explanation of analytic continuation

**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.

- Why is the shortest distance between two circles along the segment connecting their centers?
- Volume of irregular solid
- Why are second order linear PDEs classified as either elliptic, hyperbolic or parabolic?
- On the problem $1$ of Putnam $2009$
- Trisect unknown angle using pencil, straight edge & compass; Prove validity of technique
- How to prove $\cos \frac{2\pi }{5}=\frac{-1+\sqrt{5}}{4}$?

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.

- Software for drawing geometry diagrams
- Finding a Rotation Transformation from two Coordinate Frames in 3-Space
- When does intersection of measure 0 implies interior-disjointness?
- Involute of a circle - what is the separation distance?
- Why isn't $ SA_{\text{cube}} = 3x^2 $?
- Estimating the volume of a tumor from x-ray scans
- Polynomial approximation of circle or ellipse
- A diagram which is not the torus
- Importance of construction of polygons
- Linear algebra and geometric insight: a rigorous approach to vector spaces, matrices, and linear applications

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=25×2=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.

- What are affine spaces for?
- Bounded, non-constant harmonic functions: how far are they from existing?
- $\mathbf{Q} 2]=\mathbf{Q} 2]$?
- Simplifying an expression $\frac{x^7+y^7+z^7}{xyz(x^4+y^4+z^4)}$ if we know $x+y+z=0$
- Example for fintely additive but not countably additive probability measure
- Do we have $(g \wedge g)^g = 0$?
- $y_{2n}, y_{2n+1}$ and $y_{3n}$ all converge. What can we say about the sequence $ y_n$?
- Prove: The weak closure of the unit sphere is the unit ball.
- prove there is no smallest positive rational number
- Sum and product of Martingale processes
- Covariance between squared and exponential of Gaussian random variables
- what is the relationship between ZFC and first-order logic?
- Visual Ways to Remember Cross products of Unit vectors? Cross-product in $\mathbb F^3$?
- How to find this minimum of the value
- Proof of strictly increasing nature of $y(x)=x^{x^{x^{\ldots}}}$ on $[1,e^{\frac{1}{e}})$?