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_2$. 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}$

For the best lower bounds on the above let $m = \lfloor\sqrt{n}\rfloor^2$.

I have more to do.

  • $\begingroup$ This is not a puzzle. The question is off-topic here. This question was closed on Math.SE for lack of context. $\endgroup$ Dec 29, 2023 at 17:41
  • $\begingroup$ @DanielMathias I have added context and the work I have done. I felt maybe then it was more of a puzzle so I posted it here. $\endgroup$ Dec 29, 2023 at 17:44
  • 1
    $\begingroup$ The question (on Math.SE) may need further editing before it can be reopened. In any case, math problems (as opposed to math puzzles) are off-topic here. $\endgroup$ Dec 29, 2023 at 17:50
  • $\begingroup$ @DanielMathias I apologize Daniel. I am unclear where the line is between the two. Is there somewhere that explains this? $\endgroup$ Dec 29, 2023 at 17:54
  • $\begingroup$ Some background on the community decision. There is no clear line, and it is somewhat subjective. A math puzzle is a puzzle requiring some understanding or application of mathematics to solve. The key point being that a math puzzle is specifically designed to be a puzzle with an intended solution. $\endgroup$ Dec 29, 2023 at 20:15


Browse other questions tagged or ask your own question.