Consider a unit square that is covered by finitely many (potentially overlapping) rectangles of various sizes, with sides parallel to the sides of the square. We are allowed to choose some of these rectangles, so that the chosen rectangles are disjoint. Our goal is to maximize the total area $A$ of the chosen rectangles. Is there a (positive) value of $c$ such that we can always achieve $A \geq c$?

The left example below (with 4 rectangles) shows that we must have $c \leq \frac14$. enter image description here enter image description here

Because each rectangle contains the center of the square, we can only choose 1 rectangle, which has area a little over $\frac14$. There are also situations where we necessarily end up with an even smaller value of $A$. In the right image, a plus sign is covered with 8 rectangles. Again, we can only choose 1 of 8 rectangles, which gives us $15\%$ of the area of the plus sign. Since many plus signs can almost completely cover a square, this shows that we cannot have $c>0.15$. By tweaking the shape of the plus sign, we can even show that we must have $c<\frac18=0.125$.

My question here is whether such a positive value of $c$ exists at all. The above examples show that if it exists, it must be $<\frac18$.

Is there a $c>0$ such that, given any covering of a unit square with finitely many axis-parallel rectangles, it is possible to choose disjoint rectangles with total area at least $c$?

I do not know the answer to this question.

  • $\begingroup$ +1: Interesting problem. Pity not enough upvotes and views. $\endgroup$ – Aryabhata Aug 3 '17 at 19:46

Consider all rectangles of area $1$ with their bottom left hand corners at $(0,0)$ (and bases along the $x$ axis). The top right hand corners of the rectangles form the line $y=\frac1x$. Therfore the area covered by the rectangles is the area under this line. As $n\to\infty$, $\int_{1}^{n}\frac1xdx\to\infty$ so an arbitarilarly large area can be covered by rectangles of area 1 that all overlap. Therefore taking a finite selection of these rectangles of area $1$ (those with heights $\frac1n,\frac2n,...,\frac{n^2-1}{n},n)$ we can cover an arbitarily large area by making $n$ big enough. Therfore each rectangle covers an arbitarily small fraction of this area. Therfore by tiling and reducing the size of this shape (when needed) covered by these $n^2$ rectangles we can cover an arbitarily big square. Hence there doesn't $\exists c>0$.

  • 1
    $\begingroup$ I thought of this but I think it is not really clear that you can cover a square with these shapes. $\endgroup$ – user133281 Aug 3 '17 at 17:02
  • $\begingroup$ As the smallest side length is 1/n you can divide the remaining region into squares with side length 1/n and then for each of those squares you can put the same shape in but scaled by 1/n and then you can keep continuing this until an arbitrarily large fraction of the square is covered. $\endgroup$ – PJF49 Aug 3 '17 at 17:08
  • $\begingroup$ Clever! You would use that if you take (say) 1% of a square, and then 1% of the remaining area, and so on, that you then get arbitrarily close to the full area. $\endgroup$ – user133281 Aug 3 '17 at 21:03
  • $\begingroup$ Yes indeed. @user133281 $\endgroup$ – PJF49 Aug 3 '17 at 21:04

Take a rectangle with height $4$ and width $1/n$. Then rotate it $\pi$ radians clockwise about it's centre and place a new rectangle wherever the original rectangle is every $\pi/n^2$ radians. Then letting $n\to\infty$ the shape created tends to a circle however as all of the rectangles have the same centre they all overlap and only one can be choosen so the area that can be choosen $\to0$. Then consider a square with the same centre as the rectangles and side length $1$. As this square is completely inside the circle eventually the whole square is covered but the area of the rectangles that can be choosen $\to0$. So therefore there doesn't $\exists c>0$ such that the area has to be greater than $c$.

(If you're being picky then you might say that some of the rectangles are cut off by the border of the square and so the part inside in the square is no longer rectangular. Then instead you can tile the square with different sized circles arbitarily well so then again there doesn't $\exists c>0$.)

  • $\begingroup$ Of course. The rectangles were meant to be parallel to the sides of the square. I've edited the question to add this condition. $\endgroup$ – user133281 Aug 3 '17 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.