What the smallest number of circles of radius $\sqrt{2}$ that are needed to cover a rectangle $(a)$ of size $6\times 3$? $(b)$ of size $5\times 3$?
Problem
Source: Baltic way 2005/13
Tags: geometry, rectangle, analytic geometry, geometry proposed
20.09.2006 20:54
Could anyone please post a solution to this question?
12.12.2010 16:39
For a): (I'm assuming we also have to cover the edges of the rectangle). Consider a $2\times 2$ square. The distance from the vertex common to all $4$ unit squares to one of the outer vertices is $\sqrt{2}$ and hence a circle with radius $\sqrt{2}$ with its centre coinciding with the centre of the square would cover the whole $2\times 2$ block. We can cover a $6\times 3$ rectangle in $6$ different $2\times 2$ blocks (an example would be if the bottom left vertex of the $6\times 3$ rectangle is the origin, then the $6$ circles would have their centres with coordinates as $(1,1),(1,2),(3,1),(3,2),(5,1),(5,2)$). So the upper bound is $6$. Now suppose we could cover a $6\times 3$ rectangle with $5$ circles with radius $\sqrt{2}$. Consider the points $(0,0),(0,3),(3,0),(3,3),(6,0)$ and $(6,3)$. The distance between any of the two is $3$ or more. Since the largest chord of a circle with radius $\sqrt{2}$ is $2\sqrt{2}\approx 2.8284<3$, it follows a circle cannot contain two of the aforementioned points. Then the lower bound is $6$ as well. Hence the final answer of $6$. For b): It follows from from part a) that the upper bound is 6. Like we did in a), consider the $5$ points $(0,0),(0,3),(5,0),(5,3)$ and $\left(\frac{5}{2},\frac{3}{2}\right)$. The distance between any two of these points, although tighter than last time, is at least $\frac{\sqrt{34}}{2}\approx 2.9154>2.8282\approx 2\sqrt{2}$ and the lower bound of $5$ follows, since $4$ circles with radius $\sqrt{2}$ would be incapable of covering more than $4$ of these points. Hence the answer is either $5$ or $6$. The $5$ circles with centres $\left(\frac{5}{4},\frac{1}{2}\right),\left(\frac{15}{4},\frac{1}{2}\right),(1,2),(4,2)$ and $(5,2)$ do the trick (boiling down to the fact that $\sqrt{2}>1.346$).