Choosing disjoint rectangles with large total area

381 Views Asked by At

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.

2

There are 2 best solutions below

4
On BEST ANSWER

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
On

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$.)