Covering a Square Floor with Square Rugs

Question

You are given a finite collection of axis-aligned square rugs. (You do not choose the collection of rugs that you receive and the rugs are not necessarily all the same size.) Your objective is to move the rugs, without rotating them, to completely cover an axis-aligned square floor. The rugs are allowed to overlap.

Can you cover the entire floor if the total area of the rugs is three times the area of the floor?

---

I made this problem up myself and I have not been able to prove it or find a counterexample. My work so far:

---

Let the table have area 1.

Let $N$ be the number of rugs. If $N \in {1,2,3}$ then the answer is trivial. So assume $N \geq 4$.

Let $R_i$ be the $i$-th rug.

Let $r_i$ be the area of the $i$-th rug where $r_i \geq r_{i+1}$ for each $i$. Assume for all $i$, $r_i < 1.$

---

Let $N = 4$. If each rug has area greater than $\frac{1}{4}$. Then we can divide the floor into quarters and cover each quarter with a rug. So we assume otherwise and so $r_4 < \frac{1}{4}$.

Then $\frac{r_1 + r_2 + r_3}{3} > \frac{11}{12}$. Therefore $r_1 > \frac{11}{12}$.

Suppose $r_1 \approx 1$ and $r_2 = r_3$. We find $r_2 > \frac{7}{8}$.

Suppose $r_1 = r_2 \approx 1$. We find $r_3 > \frac{3}{4}$.

Place $R_1$ and $R_2$ in opposite corners. This will leave two uncovered rectangles with side lengths $1 - \sqrt{r_1}$ and $1 - \sqrt{r_2}$.

Place $R_3$ in one of the open corners.

Then we need that $r_4 \geq \left(1 - \sqrt{r_2}\right)^2$ to cover the floor.

Now let $r_1$ and $r_3$ be at their maximums. So that $r_2 + r_4$ is as small as possible.

Let $r_1 \approx 1$. Let $x = r_2 = r_3$ then $r_4 = 3 - (1 + x + x) = 2 - 2x$.

Then using the previous inequality, we need that $2 - 2x > \left(1 - \sqrt{x}\right)^2$. This inequality is true for $0 \leq x < 1$.

Therefore it is always possible to cover the floor for $N = 4$.

---

Generalizing, we can assume for $N \geq m^2$, that there are only $m^2 - 1$ rugs with area greater than $\frac{1}{m^2}$.

So that $r_{m^2} < \frac{1}{m^2}$.

$r_1 > \frac{3 - \frac{N - m^2+1}{m^2}}{m^2-1}$

$r_2 > \frac{2 - \frac{N - m^2+1}{m^2}}{m^2-2}$

$r_3 > \frac{1 - \frac{N - m^2+1}{m^2}}{m^2-3}$

---

I have more to do.

Answer 1

Let $a$ = area of the floor.

Let $r(n)$ = equal of each rug

$\epsilon$ = an inifinitesimally small amount.

As a general rule the larger a rug the more inefficiently it must be used while the smaller a rug the more efficient it gets. (only exception to this is one rug covering the entire floor will be perfectly efficient of course)

For $N=4$, even if $r(1,2,3)$ are each equal to $a-\epsilon$ which is the most inefficient setup possible, the fourth rug will still cover the last remaining corner as the total exposed area is only $\epsilon^2$.

For higher values of $N$ it only gets more and more efficient as the maximum amount of wasted space will always be to have $r(1,2,3)$ each equal to $a-\epsilon$

The closest we ever get to needing the full $3a$ area of the rugs is actually for $N=3$

Answer 2

Here is a proof:

The floor is assumed to be the unit square. Denote the lengths of the sides of the square rugs by $a_1,\ldots,a_n$. Then $a_1^2+\ldots+a_n^2 = 3$ and we may further assume that $1\geq a_1\geq\ldots\geq a_n$.

Now, we subdivide this ordered sequence of squares into smaller sequences of squares such that the sum of the sides of the squares in each sequence is just larger than 1. Formally, this may be accomplished by choosing indexes $0=i_0<i_1<\ldots<i_k\leq n$ such that $$\sum_{i=1}^{i_1} a_i \geq 1, \sum_{i=1}^{i_1-1} a_i <1,$$ $$\sum_{i=i_1+1}^{i_2} a_i \geq 1, \sum_{i=i_1+1}^{i_2-1} a_i <1,$$ and so on until $$\sum_{i=i_k+1}^n a_i <1.$$

Each of these sequences $a_{i_{j-1}+1},\ldots,a_{i_j}$ for $j=1,\ldots,k$ covers a rectangle of width at least 1 and height $a_{i_j}$. Thus, we have to prove that $$ a_{i_1}+\ldots+a_{i_k}\geq 1.$$ (Just place these rectangles below each other into the unit square.)

But we know that $$3=\sum_{i=1}^{i_1-1}a_i^2 + a_{i_1}^2 + \sum_{i=i_1+1}^{i_2-1}a_i^2 + a_{i_2}^2 + \sum_{i=i_2+1}^{i_3-1}a_i^2 + \ldots + a_{i_k}^2 + \sum_{i=i_k+1}^n a_i^2.$$ Here, each term with a summation sign corresponds to a sequence of squares which can be placed in a rectangle of length at most 1 (as $\sum_{i_{j-1}+1}^{i_j-1} a_i < 1$ by the choice of the $i_j$) and width at most $a_{i_{j-1}}$ (by the monotonic order of the $a_i$). Thus, we find $$ 3 \leq 1 + a_{i_1}^2 + a_{i_1} + a_{i_2}^2 + a_{i_2} + \ldots + a_{i_k}^2 + a_{i_k}.$$ (Here, each summand corresponds to exactly one summand from the previous equation.)

As all sides are smaller than one, it holds that $a_{i_j}^2\leq a_{i_j}$ and therefore $$3\leq 1 + 2(a_{i_1}+\ldots+a_{i_k})$$ which proves the desired inequality.