Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 43 (2002), No. 2, 411-422.

Covering the Unit Square by Squares

Janusz Januszewski

Instytut Matematyki i Fizyki ATR ul. Kaliskiego 7, 85-796 Bydgoszcz, Poland e-mail: januszew@mail.atr.bydgoszcz.pl

Abstract. Every sequence of squares with total area greater than or equal to 2 permits a covering of the unit square. MSC 2000: 52C15 Keywords: covering, square

Let (S_{n}) be a finite or infinite sequence of squares and let R be a rectangle. We say that (S_{n}) permits a covering of R (or that R can be covered by (S_{n})) if there exist rigid motions σ_{n} such that R ⊂ ⋃ σ_{n}S_{n}. The covering is parallel if all the squares σ_{n}S_{n} have sides parallel to a side of R.

Over thirty years ago Moon and Moser [3] showed, that any sequence of squares with total area not smaller than 3 permits a parallel covering of the unit square. The number 3 cannot be lessened for parallel covering, as the example of three squares of side lengths smaller than 1 shows. The natural question is how much this number can be lessened if we reject the condition of parallelism.

Obviously, the unit square cannot by covered by two squares of side lengths smaller than 1. The conjecture of M. Bognár is that any sequence of squares with total area 2 permits a covering of the unit square (see Problem 108 (iv) in [4]). We show that the conjecture is right.

We start with few lemmas. Denote by |S| the area of S and denote by [b_{1}, b_{2}] × [c_{1}, c_{2}] the set of the points (x, y) such that b_{1} ≤ x ≤ b_{2} and c_{1} ≤ y ≤ c_{2}. Assume that I = [0, 1]×[0, 1] and that R = [0, p] × [0, q], where p ≥ q > 0. Finally assume, that a_{n} denote the side length of a square S_{n}, for n = 1, 2, … and that a_{1} ≥ a_{2} ≥ …

Lemma 1. If the total area of (S_{n}) is not smaller than (q + a_{1})p + a_{1}q or if it is not smaller than (q + a_{1})p + q^{2}, then (S_{n}) permits a covering of R.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}2002 Heldermann Verlag

Proof. We cover R by squares from (S_{n}) according to the method described in the proof of Theorem 7 of [3] and in the proof of Theorem 1 of [2]. Here is a short description of our method.

If a_{1} < q, we put the squares in layers, whose bases are parallel to the base of R. We put the squares, side by side, from the left side of R to the right one along the base of the layer. The first layer has the same base as R (comp. Figure 1). If a square covers a point on the right side of R, the new layer is started directly above the last square in the preceding layer.

Figure 1

Assume now that a_{1} ≥ q. If a_{n} ≥ q for n = 1, 2, …, then R can be covered by (S_{n}). In the opposite case denote by k the greatest integer such that a_{k} ≥ q. We put the squares S_{1}, …, S_{k}, side by side, in a layer, whose base is the base of R. We put them from the left side of R to the right one along the base. If the union σ_{1}S_{1} ∪ … ∪ σ_{k}S_{k} does not cover R, the squares S_{k+1}, S_{k+2}, … are used for the covering of the rectangle [a_{1} +…+a_{k}, p]×[0, q] by the method described in the previous paragraph.

From the proof of Theorem 1 of [2] we conclude that I can be covered by (S_{n}) by our method. □

Lemma 2. If a_{1} < (\sqrt{2}+1)q and if the total area of (S_{n}) is not smaller than (\sqrt{2}+1)pq+q^{2}, then (S_{n}) permits a covering of R.

Proof. We use for the covering the method described in the proof of Lemma 1. The proof if similar to the proof of Lemma 1. □

Lemma 3. If a_{1} ≥ (\sqrt{2}+1)q and if the total area of (S_{n}) is not smaller than \frac{1}{2}(p+q)^{2}+q^{2}, then (S_{n}) permits a covering of R.

Proof. The motion σ_{1} is defined so that the sides of σ_{1}S_{1} contain the points (0, 0), (0, q), (a_{1}\sqrt{2} − q, 0), (a_{1}\sqrt{2} − q, q) (comp. Figure 2).

If a_{1} ≥ \frac{1}{2} \sqrt{2}(p + q), then R ⊂ σ_{1}S_{1}. So, in the further considerations we assume that a_{1} < \frac{1}{2} \sqrt{2}(p + q).

Case 1, when a_{2} < (\sqrt{2} + 1)q. The squares S_{2}, S_{3}, … are used for the covering of the rectangle [a_{1}\sqrt{2} − q, p] × [0, q] by the method described in the proof of Lemma 1. By Lemma 2 we see that if (S_{n}) does not permit a covering of R, then

∑ |S_{n}| < a_{1}^{2} + (\sqrt{2} + 1)(p − a_{1}\sqrt{2} + q)q + q^{2}.

Taking \frac{1}{2} \sqrt{2}(p + q) in place of a_{1} we have ∑ |S_{n}| < \frac{1}{2}(p + q)^{2} + q^{2}, which is again a contradiction.

Case 2, when a_{2} ≥ (\sqrt{2} + 1)q. If a_{n} ≥ (\sqrt{2} + 1)q for n = 1, 2, …, then R can be covered by (S_{n}). In the opposite case denote by k the greatest integer such that a_{k} ≥ (\sqrt{2} + 1)q. The motions σ_{2}, …, σ_{k} are defined so that the sides of σ_{i}S_{i} contain the points

\begin{matrix}((a_{1} + … + a_{i−1})\sqrt{2} − (i − 1)q, 0), ((a_{1} + … + a_{i−1})\sqrt{2} − (i − 1)q, q), \\ ((a_{1} + … + a_{i})\sqrt{2} − iq, 0), ((a_{1} + … + a_{i})\sqrt{2} − iq, q), \end{matrix}

for i = 2, …, k (see Fig. 2). If R is not contained in σ_{1}S_{1} ∪ … ∪ σ_{k}S_{k}, the squares S_{k+1}, S_{k+2}, … are used for the covering of the rectangle [(a_{1} + … + a_{k})\sqrt{2} − kq, p] × [0, q] by the method from Lemma 1.

Figure 2

It is easy to show that |S_{1}| + … + |S_{k}| is not greater than the area of a square whose sides contain the points

(0, 0), (0, q), ((a_{1} + … + a_{k})\sqrt{2} − kq, 0), ((a_{1} + … + a_{k})\sqrt{2} − kq, q).

By Case 1 we see that R can be covered by (S_{n}). □

Obviously, Lemmas 1–3 are still true if R is an arbitrary rectangle of sides of lengths p and q.

Theorem. Every sequence of squares with total area greater than or equal to 2 permits a covering of the unit square.

Proof. Let (S_{n}) be a sequence of squares with total area not smaller than 2. Denote by a_{n} the side length of S_{n} for n = 1, 2, … Without loss of generality we can assume, that a_{1} ≥ a_{2} ≥ . . ..

If a_{1} ≤ \frac{1}{2}, by Lemma 1 we see that (S_{n}) permits a covering of I. Obviously, if a_{1} ≥ 1, then I can be covered by S_{1}. So, in the further considerations we assume that \frac{1}{2} < a_{1} < 1.

The covering method depends on the size of squares in (S_{n}). Consider three cases.

Case 1, when a_{2} + a_{3} < 1. Subcase 1a, when a_{1} + a_{3} < 1. We use for the covering the method from Lemma 1. Denote by S_{n_{1}} the last square lying in the first layer.

If a_{1} +a_{2} < 1, the total area of squares lying in the first layer is smaller than a_{1}^{2} +(1− a_{1})^{2} +a_{n_{1}}^{2} (see Fig. 1). Obviously, a_{n_{1}} < 1−a_{1}. Assume that I is not covered. By Lemma 1 we see that the total area of squares which are used for the covering of the rectangle [0, 1] × [a_{n_{1}}, 1] is smaller than or equal to 1 − a_{n_{1}} + a_{n_{1}} + (1 − a_{n_{1}})a_{n_{1}}. Consequently,

∑ |S_{n}| < a_{1}^{2} + (1 − a_{1})^{2} + a_{n_{1}}^{2} + 1 + (1 − a_{n_{1}})a_{n_{1}} = 2a_{1}^{2} − 2a_{1} + 2 + a_{n_{1}}.

Taking 1−a_{1} in place of a_{n_{1}}, we have ∑ |S_{n}| < 2a_{1}^{2} −3a_{1} +3 < 2, which is a contradiction. If a_{1} + a_{2} ≥ 1 and if I is not covered, by Lemma 1 we see that

∑ |S_{n}| < a_{1}^{2} + a_{2}^{2} + 1 − a_{2} + a_{3} + (1 − a_{2})a_{3}.

Taking 1−a_{1} in place of a_{3} we obtain that ∑ |S_{n}| < a_{1}^{2} +a_{2}^{2} −2a_{1} −2a_{2} +a_{1}a_{2} +3. Denote by h(a_{1}, a_{2}) the function on the right side of this formula. Let T_{h} = {(a_{1}, a_{2}); 1 − a_{1} ≤ a_{2} ≤ a_{1} ≤ 1}. We see that h(a_{1}, a_{2}) does not have any maximum inside T_{h}. Consider h on the boundary of T_{h}. We have h(1, a_{2}) = a_{2}^{2} − a_{2} + 2 ≤ 2, provided 0 ≤ a_{2} ≤ 1. Moreover, h(a_{1}, a_{1}) = 3a_{1}^{2} − 4a_{1} + 3 ≤ 2 for \frac{1}{2} ≤ a_{1} ≤ 1. Finally, h(a_{1}, 1 − a_{1}) = a_{1}^{2} − a_{1} + 2 ≤ 2 provided \frac{1}{2} ≤ a_{1} ≤ 1. Consequently, ∑ |S_{n}| < h(a_{1}, a_{2}) ≤ 2 for (a_{1}, a_{2}) ∈ T_{h}, which is a contradiction. Subcase 1b, when a_{1} + a_{3} ≥ 1. We put the three first squares so that

σ_{1}S_{1} = [0, a_{1}] × [0, a_{1}], σ_{2}S_{2} = [1 − a_{2}, 1] × [0, a_{2}], σ_{3}S_{3} = [1 − a_{3}, 1] × [a_{2}, a_{2} + a_{3}].

If a_{2} + a_{3} ≤ a_{1}, the squares S_{4}, S_{5}, … are used for the covering of the rectangle [0, 1] × [1 − a_{2} − a_{3}, 1] by the method from Lemma 1. Assume that I is not covered. By Lemma 1 we have

∑ |S_{n}| < a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + 1 − a_{2} − a_{3} + a_{3} + (1 − a_{2} − a_{3})a_{3}.  (1)

If a_{2} ≥ \frac{1}{2}, taking 1−a_{2} in place of a_{3} and 1 in place of a_{1} in (1) we have ∑ |S_{n}| < 2a_{2}^{2}−3a_{2}+ 3 ≤ 2, a contradiction. If a_{2} < \frac{1}{2}, replacing a_{3} by a_{2} in (1) we have ∑ |S_{n}| < 1 + a_{1}^{2} < 2, which is a contradiction.

If a_{2} + a_{3} > a_{1}, the squares S_{4}, S_{5}, … are used for the covering of the rectangle [0, 1] × [a_{1}, 1] by the method from Lemma 1. If I is not covered, by Lemma 1 we have

∑ |S_{n}| < a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + 1 − a_{1} + a_{3} + (1 − a_{1})a_{3}.  (2)

If a_{2} ≥ \frac{1}{2}, taking 1 − a_{2} in place of a_{3} in (2) we obtain that

∑ |S_{n}| < a_{1}^{2} + 2a_{2}^{2} − 2a_{1} − 4a_{2} + a_{1}a_{2} + 4.

Denote by k(a_{1}, a_{2}) the function on the right side of this formula. Let T_{k} = \{(a_{1}, a_{2}); \frac{1}{2} ≤ a_{2} ≤ a_{1} ≤ 1}. We see that k(a_{1}, a_{2}) does not have any maximum inside T_{k}. Consider k on the boundary of T_{k}. We have k(a_{1}, \frac{1}{2}) = a_{1}^{2} − \frac{3}{2}a_{1} + \frac{5}{2}. This value is not greater than 2 provided \frac{1}{2} ≤ a_{1} ≤ 1. Moreover, k(1, a_{2}) = 2a_{2}^{2} − 3a_{2} + 3 ≤ 2 for \frac{1}{2} ≤ a_{2} ≤ 1. Finally, k(a_{1}, a_{1}) = 4a_{1}^{2} − 6a_{1} + 4 ≤ 2 provided \frac{1}{2} ≤ a_{1} ≤ 1. Consequently, ∑ |S_{n}| < k(a_{1}, a_{2}) ≤ 2 for (a_{1}, a_{2}) ∈ T_{k}, which is a contradiction. If a_{2} < \frac{1}{2}, replacing a_{3} by a_{2} in (2) we have

∑ |S_{n}| < a_{1}^{2} + 2a_{2}^{2} − a_{1} + 2a_{2} − a_{1}a_{2} + 1.

This value is also not greater than 2 provided 0 < a_{2} < \frac{1}{2} and \frac{1}{2} < a_{1} < 1, which is a contradiction.

Case 2, when a_{2} ≤ 0.87\sqrt{2} − 0.37\sqrt{2}a_{1} and when a_{2} + a_{3} ≥ 1. Observe, that the second condition of the case implies that a_{2} ≥ \frac{1}{2}.

First assume that a_{3} ≤ (\sqrt{2} + 1)(1 − a_{1}) or that 2a_{1} + a_{2}\sqrt{2} + a_{3}\sqrt{2} ≤ 3. We put the three first squares so that:

σ_{1}S_{1} = [0, a_{1}] × [0, a_{1}], σ_{2}S_{2} = [1 − a_{2}, 1] × [0, a_{2}], σ_{3}S_{3} = [1 − a_{3}, 1] × [1 − a_{3}, 1].

The remaining squares are used for the covering of the rectangle [0, 1 − a_{3}] × [a_{1}, 1] by the method from Lemma 1. Assume that I is not covered. By Lemma 1 we have

∑ |S_{n}| < a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + (1 − a_{1} + a_{3})(1 − a_{3}) + (1 − a_{1})^{2}.  (3)

If a_{3} ≤ (\sqrt{2}+1)(1−a_{1}), taking (\sqrt{2}+1)(1−a_{1}) in place of a_{3} and a_{1} in place of a_{2} in (3) we have ∑ |S_{n}| < (2−\sqrt{2})a_{1}^{2} +(\sqrt{2}−2)a_{1} +2 ≤ 2, a contradiction. If 2a_{1} +a_{2}\sqrt{2}+a_{3}\sqrt{2} ≤ 3, from a_{2} + a_{3} ≥ 1 we see that a_{1} ≤ \frac{1}{2}(3 − a_{2}\sqrt{2} − a_{3}\sqrt{2}) ≤ \frac{1}{2}(3 − \sqrt{2}). Moreover, a_{3} ≤ \frac{1}{2} \sqrt{2}(3 − 2a_{1} − a_{2}\sqrt{2}) ≤ \frac{1}{2} \sqrt{2}(3 − 2a_{3} − a_{3}\sqrt{2}), and consequently a_{3} ≤ \frac{3}{2}(\sqrt{2} − 1). Taking \frac{3}{2}(\sqrt{2}−1) in place of a_{3} and a_{1} in place of a_{2} in (3) we have ∑ |S_{n}| < 3a_{1}^{2}+a_{1}(\frac{3}{2} \sqrt{2}− \frac{9}{2})+2. This value is not greater than 2 for \frac{1}{2} < a_{1} ≤ \frac{1}{2}(3 − \sqrt{2}), which is a contradiction. Assume now that

a_{3} > (\sqrt{2} + 1)(1 − a_{1})  (4)

and that

2a_{1} + a_{2}\sqrt{2} + a_{3}\sqrt{2} > 3.  (5)

By a_{1} ≥ a_{3} > (\sqrt{2} + 1)(1 − a_{1}) we conclude that a_{1} > \frac{1}{2} \sqrt{2}. Consider four subcases.

Subcase 2a, when a_{2} ≤ \frac{1}{2} \sqrt{2} and when a_{4} < (\sqrt{2} + 1)(1 − a_{1}). From a_{2} ≤ \frac{1}{2} \sqrt{2} we see that a_{1} + a_{2}\sqrt{2} − 1 ≤ a_{1}. From (5) it follows that 3 − a_{1} − a_{2}\sqrt{2} − a_{3}\sqrt{2} < a_{1}. Obviously, 3 − a_{1} − a_{2}\sqrt{2} − a_{3}\sqrt{2} ≥ 3 − a_{1} − 2a_{2}\sqrt{2} > 0 (see Figure 3).

We put the three first squares so that σ_{1}S_{1} = [0, a_{1}] × [0, a_{1}], that the sides of σ_{2}S_{2} contain the points (a_{1}, 0), (1, 0), (a_{1}, a_{1} + a_{2}\sqrt{2} − 1), (1, a_{1} + a_{2}\sqrt{2} − 1) and that the sides of σ_{3}S_{3} contain the points (1, a_{1} + a_{2}\sqrt{2} − 1), (3 − a_{1} − a_{2}\sqrt{2} − a_{3}\sqrt{2}, 1), (1, 1) (see Figure 3). The remaining squares are used for the covering of the rectangle [0, 3 − a_{1} − a_{2}\sqrt{2} − a_{3}\sqrt{2}] × [a_{1}, 1] by the method from Lemma 1.

Figure 3

Assume that I is not covered. By Lemma 2 we see that

∑ |S_{n}| < a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + (\sqrt{2} + 1)(3 − a_{1} − a_{2}\sqrt{2} − a_{3}\sqrt{2})(1 − a_{1}) + (1 − a_{1})^{2}.

By applying the method of finding the absolute maximum of the function of three variables (similarly as in Case 1 for the function of two variables), we show that this value not greater than 2 provided (\sqrt{2} + 1)(1 − a_{1}) ≤ a_{3} ≤ a_{2} ≤ \frac{1}{2} \sqrt{2} ≤ a_{1} ≤ 1, which is a contradiction.

Subcase 2b, when a_{2} ≤ \frac{1}{2} \sqrt{2} and when a_{4} ≥ (\sqrt{2} + 1)(1 − a_{1}). We put the three first squares as in Subcase 2a. The squares S_{4}, S_{5}, … are used for the covering of the rectangle [0, 3 − a_{1} − a_{2}\sqrt{2} − a_{3}\sqrt{2}] × [1 − a_{1}, 1] by the method described in Lemma 3. By Lemma 3 we see that if I is not covered, then

∑ |S_{n}| < a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + \frac{1}{2}(4 − 2a_{1} − a_{2}\sqrt{2} − a_{3}\sqrt{2})^{2} + (1 − a_{1})^{2}.

By applying the method of finding the absolute maximum of the function of three variables we show that this value is smaller than or equal to 2 provided \frac{1}{2} ≤ a_{2} ≤ \frac{1}{2} \sqrt{2} ≤ a_{1} ≤ 1 and 1 − a_{2} ≤ a_{3} ≤ a_{2}, which is a contradiction. Subcase 2c, when a_{2} > \frac{1}{2} \sqrt{2} and when a_{3} ≤ \frac{3}{2} \sqrt{2} − \frac{1}{2} \sqrt{2}a_{1} − a_{2}. We put the three first squares as in Fig. 4, i.e. so that σ_{1}S_{1} = [0, a_{1}] × [0, a_{1}], so that the sides of σ_{2}S_{2} contain the points (a_{1}, 0), (1, 0), (a_{1}, a_{1} + a_{2}\sqrt{2} − 1), (1, a_{1} + a_{2}\sqrt{2} − 1) and so that the sides of σ_{3}S_{3} contain the points (0, a_{1}), (0, 1), (a_{1} + a_{3}\sqrt{2} − 1, a_{1}), (a_{1} + a_{3}\sqrt{2} − 1, 1).

Figure 4

If a_{4} < (\sqrt{2} + 1)(1 − a_{1}), the squares S_{4}, S_{5}, … are used for the covering of the rectangle [a_{1} + a_{3}\sqrt{2} − 1, 1] × [a_{1}, 1] by the method from Lemma 1. Assume that I is not covered. By Lemma 2 we see that if (S_{n}) does not permit a covering of I,

∑ |S_{n}| < a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + (\sqrt{2} + 1)(2 − a_{1} − a_{3}\sqrt{2})(1 − a_{1}) + (1 − a_{1})^{2}.

By applying the method of finding the absolute maximum of the function of three variables it can be shown that this value is not greater than 2 provided \frac{1}{2} \sqrt{2} ≤ a_{2} ≤ a_{1} ≤ 1, a_{2} ≤ 0.87\sqrt{2} − 0.37\sqrt{2}a_{1} and (\sqrt{2} + 1)(1 − a_{1}) ≤ a_{3} ≤ \frac{3}{2} \sqrt{2} − \frac{1}{2} \sqrt{2}a_{1} − a_{2}, which is a contradiction.

If a_{4} ≥ (\sqrt{2}+1)(1−a_{1}), the squares S_{4}, S_{5}, … are used for the covering of the rectangle [a_{1} + a_{3}\sqrt{2} − 1, 1] × [a_{1}, 1] by the method described in Lemma 3. Assume that I is not covered by our method. By Lemma 3 we see that

∑ |S_{n}| < a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + \frac{1}{2}(3 − 2a_{1} − a_{3}\sqrt{2})^{2} + (1 − a_{1})^{2}.

It can be shown that, under the assumptions of the subcase, this value is not greater than 2, which is a contradiction.

Subcase 2d, when a_{2} > \frac{1}{2} \sqrt{2} and when a_{3} > \frac{3}{2} \sqrt{2} − \frac{1}{2} \sqrt{2}a_{1} − a_{2}. We put the three first squares as in Subcase 2c. From a_{2} ≥ a_{3} > \frac{3}{2} \sqrt{2} − \frac{1}{2} \sqrt{2}a_{1} − a_{2} we have a_{2} > \frac{3}{4} \sqrt{2} − \frac{1}{4} \sqrt{2}a_{1}. Consequently, we see that a_{2}\sqrt{2} − 1 − (\frac{1}{2} − \frac{1}{2}a_{1}) > 0, i.e. that there are points in σ_{2}S_{2} with second coordinate greater than 1 (see Fig. 5). Moreover, the second condition of the subcase implies that a_{1} + a_{3}\sqrt{2} − 1 ≥ 2 − a_{2}\sqrt{2} (see Fig. 5).

If a_{1} + a_{2}\sqrt{2} ≥ 2, then I is covered by σ_{1}S_{1} ∪ σ_{2}S_{2} ∪ σ_{3}S_{3}. In the opposite case, the squares S_{4}, S_{5}, … are used for the covering of the square [a_{1}+a_{2}\sqrt{2}−1, 1]×[a_{1}+a_{2}\sqrt{2}−1, 1] by the method from Lemma 1.

Figure 5

Assume that I is not covered. By Lemma 1 we deduce that

|S_{4}| + |S_{5}| + … < 3(2 − a_{1} − a_{2}\sqrt{2})^{2}.

Consequently,

∑ |S_{n}| < a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + 3(2 − a_{1} − a_{2}\sqrt{2})^{2}.

It is easy to check that, under the assumptions of the subcase, this value is not greater than 2, which is a contradiction.

Case 3, when a_{2} > 0.87\sqrt{2} − 0.37\sqrt{2}a_{1}. For simplicity of the notation, we will write a instead of a_{1} and b instead of a_{2}. From a ≥ b we conclude that a > \frac{0.87\sqrt{2}}{1+0.37\sqrt{2}} = 0.8077 … Moreover, b > \frac{1}{2} \sqrt{2}.

We put the two first squares as in Fig. 6, i.e. so that σ_{1}S_{1} = [0, a] × [0, a] and that the sides of σ_{2}S_{2} contain the points (a, 0), (1, 0), (1, 1).

We show that the motion σ_{2} is achievable. From Fig. 6 we see that to show this, it is sufficient to show that u < b.

We see that u = \frac{b−w}{1−a} and w = \sqrt{1 − u^{2}}. Hence, u = \frac{b−\sqrt{1−u^{2}}}{1−a}, and consequently

u = \frac{b − ab + \sqrt{2 + a^{2} − 2a − b^{2}}}{a^{2} − 2a + 2}  (6)

Figure 6

A simple computation shows that the condition 0.87\sqrt{2} − 0.37\sqrt{2}a > \frac{1}{\sqrt{1+a^{2}}} is equivalent to the inequality

(a − 1)(0.2738a^{3} − 1.0138a^{2} + 0.7738a − 0.5138) > 0  (7)

for 0.8077 … < a < 1. The value in the first parentheses is negative. Denote the function in the second parentheses by h(a). We see that h′(a) is negative in the considered interval. Consequently, h(a) ≤ h(0.8077 …) < 0 and (7) holds. Hence, the condition b > 0.87\sqrt{2} − 0.37\sqrt{2}a implies that b > \frac{1}{\sqrt{1+a^{2}}} . It is easy to show that u < b provided b > \frac{1}{\sqrt{1+a^{2}}} . Thus, the covering as in Fig. 6 is always possible.

Denote by (s, 1), where s ≠ 1, the common point of the boundaries of I and σ_{2}S_{2}. From Fig. 6 we see that w = \frac{b−u}{1−s} and \frac{b−w}{1−a} = u. Hence,

s = \frac{ua}{b − u + au}.  (8)

By (6) and (8) we have

s = \frac{ab − a^{2}b + a\sqrt{2 + a^{2} − 2a − b^{2}}}{b + (a − 1)\sqrt{2 + a^{2} − 2a − b^{2}}} .  (9)

The squares S_{3}, S_{4}, … are used for the covering of the rectangle [0, s] × [a, 1]. If a_{3} < (\sqrt{2} + 1)(1 − a), we use the method from Lemma 1 for the covering of [0, s] × [a, 1]. Assume that I is not covered. By Lemma 2 we see that

∑ |S_{n}| < a^{2} + b^{2} + (\sqrt{2} + 1)(1 − a)s + (1 − a)^{2}.

From s < 1 we have ∑ |S_{n}| < 2a^{2} +(\sqrt{2}+1)(1−a)+(1−a)^{2} ≤ 2, which is a contradiction. If a_{3} ≥ (\sqrt{2} + 1)(1 − a), we use the method described in Lemma 3 for the covering of [0, s] × [a, 1]. Consequently, if (S_{n}) does not permit a covering of I, then

∑ |S_{n}| < a^{2} + b^{2} + \frac{1}{2}(s + 1 − a)^{2} + (1 − a)^{2}.  (10)

In order to obtain a contradiction, we show that the value on the right side of (10) is not greater than 2. We have

s + 1 − a = \frac{b − a^{2}b + (3a − a^{2} − 1)\sqrt{2 + a^{2} − 2a − b^{2}}}{b + (a − 1)\sqrt{2 + a^{2} − 2a − b^{2}}} .

From 3a − a^{2} − 1 ≤ a we see that in order to complete the proof it is sufficient to show that

a^{2} + b^{2} + \frac{1}{2}[\frac{b − a^{2}b + a\sqrt{2 + a^{2} − 2a − b^{2}}}{b + (a − 1)\sqrt{2 + a^{2} − 2a − b^{2}}} ]^{2} + (1 − a)^{2} ≤ 2.  (11)

In order to get this inequality it is convenient to multiply (11) by

2[b + (a − 1)\sqrt{2 + a^{2} − 2a − b^{2}}]^{2}.

Consequently, (11) is equivalent to

\begin{matrix}4a^{6} − 20a^{5} + 43a^{4} − 46a^{3} + 20a^{2} + 4a − 4+ \\ + 5b^{2} − a^{4}b^{2} + 4a^{3}b^{2} − 2a^{2}b^{4} + 5a^{2}b^{2} + 4ab^{4} − 16ab^{2}+ \\ \sqrt{2 + a^{2} − 2a − b^{2}}(6a^{3}b − 16a^{2}b + 4ab^{3} + 6ab − 4b^{3} + 4b) ≤ 0. \end{matrix}  (12)

for b ≤ a ≤ 1 and for b ≥ 0.87\sqrt{2} − 0.37\sqrt{2}a.

The value in the parentheses is positive, as is easy to check. For simplicity of further computations consider three subcases.

Subcase 3a, when b ≥ 0.8. Observe that 2 + a^{2} − 2a − b^{2} < 0.392 for (a, b) ∈ D, where

D = \{(a, b); 0.8 ≤ b ≤ a ≤ 1, b ≥ 0.87\sqrt{2} − 0.37\sqrt{2}a\}.

Consequently, replacing \sqrt{2 + a^{2} − 2a − b^{2}} by 0.63 in (12) we see that in order to show (12) for b ≥ 0.8 it is sufficient to show that

\begin{matrix}4a^{6} − 20a^{5} + 43a^{4} − 46a^{3} + 20a^{2} + 4a − 4+ \\ + 5b^{2} − a^{4}b^{2} + 4a^{3}b^{2} − 2a^{2}b^{4} + 5a^{2}b^{2} + 4ab^{4} − 16ab^{2}+ \\ 3.78a^{3}b − 10.08a^{2}b + 2.52ab^{3} + 3.78ab − 2.52b^{3} + 2.52b ≤ 0, \end{matrix}  (13)

for (a, b) ∈ D.

Denote by f(a, b) the function on the left side of (13). We see that the partial derivative

f′′′_{bbb}(a, b) = −48a^{2}b + 96ab + 15.12a − 15.12 > 0.

Consequently, f′′_{bb}(a, b) ≥ f′′_{bb}(a, 0.8) > 0. This means that f′_{b}(a, b) is increasing with respect to b. As a consequence, the function f(a, b) does not have any maximum inside D.

Consider the points from the boundary of D. We see that

f(a, a) = a^{6} − 12a^{5} + 54.3a^{4} − 74.6a^{3} + 28.78a^{2} + 6.52a − 4.

It is easy to see that this value is not greater than zero for 0.8077 … ≤ a ≤ 1. Obviously, f(1, b) = 2b^{4} − 3b^{2} + 1 ≤ 0 for 0.8 ≤ b ≤ 1. Moreover,

f(a, 0.8) = 4a^{6} − 20a^{5} + 42.36a^{4} − 40.416a^{3} + 14.3168a^{2} − 0.28736a − 0.07424.

A computation shows that f(a, 0.8) ≤ 0 provided \frac{0.87\sqrt{2}−0.8}{0.37\sqrt{2}} ≤ a ≤ 1. It can be shown

that also f(a, 0.87\sqrt{2} − 0.37\sqrt{2}a) ≤ 0 for 0.8077 … ≤ a ≤ \frac{0.87\sqrt{2}−0.8}{0.37\sqrt{2}}.

Subcase 3b, when 0.77 ≤ b ≤ 0.8. Observe that now 2+a^{2} −2a−b^{2} < 0.422. Consequently, replacing \sqrt{2 + a^{2} − 2a − b^{2}} by 0.65 on the left side of (12) we see that in order to confirm (12) it is sufficient to show that

\begin{matrix}4a^{6} − 20a^{5} + 43a^{4} − 46a^{3} + 20a^{2} + 4a − 4+ \\ + 5b^{2} − a^{4}b^{2} + 4a^{3}b^{2} − 2a^{2}b^{4} + 5a^{2}b^{2} + 4ab^{4} − 16ab^{2}+ \\ 3.9a^{3}b − 10.4a^{2}b + 2.6ab^{3} + 3.9ab − 2.6b^{3} + 2.6b ≤ 0, \end{matrix}  (14)

for 0.77 ≤ b ≤ 0.8, for b ≥ 0.87\sqrt{2} − 0.37\sqrt{2}a and for a ≤ 1. Denote by g(a, b) the function on the left side of (14). We have

g′′′_{bbb}(a, b) = −48a^{2}b + 96ab + 15.6a − 15.6 > 0.

Consequently, g′′_{bb}(a, b) ≥ g′′_{bb}(a, 0.77) > 0 and g′_{b}(a, b) ≤ g′_{b}(a, 0.8) < 0. Hence, g(a, b) ≤ g(a, 0.77) = 4a^{6}−20a^{5}+42.4071a^{4}−40.6254a^{3}+14.25343918a^{2}+0.10970744a−0.2204858 ≤ 0, provided \frac{0.87\sqrt{2}−0.77}{0.37\sqrt{2}} ≤ a ≤ 1, as is easy to check, and g(a, b) ≤ g(a, 0.87\sqrt{2}−0.37\sqrt{2}a) ≤

0, provided \frac{0.87\sqrt{2}−0.8}{0.37\sqrt{2}} ≤ a ≤ \frac{0.87\sqrt{2}−0.77}{0.37\sqrt{2}}, as is easy to show.

Subcase 3c, when b < 0.77. Observe that 2 + a^{2} − 2a − b^{2} ≤ 0.5. Taking 0.71 in place of \sqrt{2 + a^{2} − 2a − b^{2}} on the left side of (12) we see that to show (12) it is sufficient to show that

\begin{matrix}4a^{6} − 20a^{5} + 43a^{4} − 46a^{3} + 20a^{2} + 4a − 4+ \\ + 5b^{2} − a^{4}b^{2} + 4a^{3}b^{2} − 2a^{2}b^{4} + 5a^{2}b^{2} + 4ab^{4} − 16ab^{2}+ \\ 4.26a^{3}b − 11.36a^{2}b + 2.84ab^{3} + 4.26ab − 2.84b^{3} + 2.84b ≤ 0, \end{matrix}  (15)

for 0.87\sqrt{2} − 0.37\sqrt{2}a ≤ b ≤ 0.77 and for a ≤ 1.

An analysis similar to that in Subcase 3b shows that (15) holds. □

In [1] and [2] it is proved that any sequence of rectangles whose side lengths are not greater than 1 permits a parallel covering of I, provided the total area of this sequence is not smaller than 3.

The author conjectures that the unit square can be covered by any sequence of rectangles of side lengths not greater than 1 with total area greater than or equal to 2.

References

[1] Bezdek, A.; Bezdek, K.: Eine hinreichende Bedingung für die Überdeckung des Einheitswürfels durch homothetische Exemplare im n-dimensionalen euklidischen Raum. Beiträge Algebra Geom. 17 (1984), 5–21. Zbl 0556.52008

[2] Groemer, H.: Covering and packing properties of bounded sequences of convex sets. Mathematika 29 (1982), 18–31. Zbl 0496.52011

[3] Moon, J. W.; Moser, L.: Some packing and covering theorems. Colloq. Math. 17 (1967), 103–110. Zbl 0152.39502

[4] Moser, W.; Pach, J.: Research Problems in Discrete Geometry. Privately published collection of problems, 1994.

Received November 27, 2000