Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 39 (1998), No. 2, 481-495.

Unilateral Tilings of the Plane with Squares of Three Sizes

Horst Martini  Endre Makai^{1}  Valeriu Soltan^{2}

Fakultät für Mathematik, TU Chemnitz D–09009 Chemnitz, Germany, Martini@mathematik.tu-chemnitz.de

Mathematical Institute of the Hungarian Academy of Sciences H–1364 Budapest, Pb. 127, Hungary, makai@math-inst.hu

Mathematical Institute of the Academy of Sciences of Moldova MD–2028 Chişinău, Moldova, 17soltan@mathem.moldova.su

Abstract. A tiling H of the Euclidean plane by squares of three distinct sizes is said to be a unilateral 3-tiling (or U3-tiling) if no two congruent tiles have a common side, and it is called equitransitive provided for any pair S, S′ of congruent tiles of H there is a congruence transform of the plane mapping S onto S′ and also mapping H onto itself. Contrary to the assertion by D. Schattschneider that there are only five equitransitive U3-tilings, we present three new such tilings (two of them are due to B. Grünbaum). We describe the local environments of each tile in a U3-tiling with their global extensions, as well as further global properties of U3-tilings. Keywords: tiling of the plane, squares, unilaterality, equitransitivity MSC 1991: 52C20

0. Introduction

Problems on tiling a square or a rectangle into squares of several distinct sizes have been studied by many mathematicians (see [2], Sections C2–C5, and [6], Section 2.4, for references).

1Partially supported by the Hungarian National Foundation for Scientific Research, grant no. T-024037, as well as by the Academy of Sciences of Moldova and Deutsche Forschungsgemeinschaft.

2Supported by Deutsche Forschungsgemeinschaft.

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

On the other hand, there are only a few results on tiling the whole plane into noncongruent squares (see, e.g., [3], [4], [5], [7], also [2], Section C10, and [6], Section 2.4).

One of the still unsettled (and attractive) problems here is to describe all possible tilings of the plane with squares of n given sizes. This problem has been investigated by Schattschneider [8] (see also Grünbaum and Shephard [6], pp. 76–81) for some special types of tilings.

Figure 1

It is obvious that for any positive integer n there is a tiling of the Euclidean plane with squares of n distinct sizes. In Figure 1 one can see examples of such tilings by two and three distinct squares, respectively (cf. [6], Figures 2.4.2 and 2.4.5). These pictures can be easily redrawn for an arbitrary n (cf. [6], p. 81, Exercise 9.a).

Since the whole variety of tilings of the plane into squares of n distinct sizes is too extensive, several authors have restricted their attention to special classes of tilings. According to [6], a tiling H by squares is called unilateral if no two congruent tiles (if they exist) have a common side, and it is called equitransitive provided for any pair S, S′ of congruent tiles of H there is a congruence transform of the plane mapping S onto S′ and also mapping H onto itself.

It is easy to verify (see [6], p. 81, Exercise 4) that there is only one (up to congruence) equitransitive, unilateral tiling of the plane with squares of two fixed sizes, as shown in Figure 1(i). Schattschneider [8] has described five equitransitive, unilateral tilings of the plane with squares of three sizes, claiming that there are exactly five such tilings (see [6], Figure 2.4.5). Contrary to her opinion (and therefore also to Exercise 2.4.6.b from [6]) we show in Figure 2 a new tiling of this type, which is a slight modification of Figure 2.4.5.d in [6]. Note that the symmetry group of this tiling contains all lattice translations with lattice basis (6; 0), (0; 8), and also reflections with respect to the coordinate axes, followed by translation along the half basis vector in the direction of the respective coordinate axis (i.e., glide reflections), as well as reflections with respect to the points (±\frac{3}{2}; −2).)

In response to our Figure 2, B. Grünbaum sent us two further equitransitive U3-tilings (and kindly agreed to their inclusion in our paper, see Figure 3). These are also modifications of figures from [6], namely of Figures 2.4.5.d and 2.4.5.e, respectively.

Figure 3

Thus the problem to describe all equitransitive, unilateral tilings of the plane with squares of three distinct sizes still remains open.

Our purpose here is to study some properties of unilateral – not necessarily equitransitive – tilings of the plane with squares of three sizes, which we will briefly call U3-tilings. To formulate our results, we need some definitions and notation. For a given U3-tiling H, we denote by λ_{1}, λ_{2}, λ_{3} the sizes of the tiling squares, assuming everywhere that λ_{1} < λ_{2} < λ_{3}. Thus by a λ_{i}-tile we mean a tile of size λ_{i}, i = 1, 2, 3. A side of H is any side of a tiling square, and skel H (the skeleton of H) is the union of all sides of H. Every tile is supposed to be closed. Two tiles are neighbourly if their intersection is a non-degenerate line segment.

The paper is organized as follows. In Section 1 we introduce the notion of a vortex and discuss the possibility for a λ_{i}-tile to be a vortex. Section 2 is devoted to the study of neighbourly environments of a λ_{i}-tile, and in Section 3 some global properties of U3-tilings are exposed.

1. Vortices

In what follows, H stands for a tiling of the plane by squares.

Definition 1. We say that a tile of H is a vortex if its sides are locally extendable in skel H according to an orientation of the tile, but none of them is extendable according to the other orientation.

In other words, a tile T with the vertices a, b, c, d, taken according to some orientation of T, is a vortex provided the following two conditions are satisfied:

(i) there are line segments [a, b′], [b, c′], [c, d′], and [d, a′], each of them properly containing the respective side of T and lying in skel H,

(ii) every vertex of T belongs to the relative interior of a side of another tile (see Figure 4).

Figure 4

Theorem 1. If H is a U3-tiling of the plane with squares of sizes λ_{1}, λ_{2}, λ_{3}, then every λ_{1}-tile is a vortex.

Proof. Let T be a λ_{1}-tile. Denote by a, b, c, d the vertices of T, as shown in Figure 4. At least one of the vertices of T, say a, lies in the interior of a side of another tile, R, since otherwise every side of T would be a side of another tile. Then the right angle with apex a, lying outside T ∪ R, is covered by a new tile, S. Since H is unilateral, S is larger than T, and b lies in the interior of a side of S. As above, the right angle with apex b, lying outside T ∪ S, is covered by a new tile V, and the right angle with vertex c, lying outside T ∪ V, is covered by a new tile W. Since W is larger than T, d lies in the interior of a side of W. If there were a new tile touching T and lying between R and W, this tile would be smaller than T, which is impossible. Hence [a, d] lies in a side of R and d is a vertex of R. Summing up, we obtain that T is a vortex. □

Theorem 2. If H is a U3-tiling of the plane with squares of sizes λ_{1}, λ_{2}, λ_{3}, then every λ_{2}-tile is a vortex.

Proof. Let T be a λ_{2}-tile. Denote by a, b, c, d the vertices of T, as shown in Figure 4. The vertex a is either a common vertex of four tiles in H, or is a relative inner point of a side of a tile S_{1} ∈ H and a vertex of a tile S_{2} ∈ H different from T. Thus we may assume that a is a vertex of a tile S ∈ H, and S∩]a, b[ ≠ ∅.

From the unilaterality of H it follows that b cannot be a vertex of a tile different from T and having common points with ]a, b[. Namely, in the contrary case [a, b] would be a side of another λ_{2}-tile, or would be the union of sides of at least two λ_{1}-tiles. Hence [a, b] is properly extendable to a segment [a, b′] ⊂ skel H, and [b, c] is not properly extendable to a segment [b′, c] ⊂ skel H. Similarly, there are proper extensions [b, c′], [c, d′], and [d, a′] in skel H of the respective sides of T, and each of the points c, d, a is an interior point of a side of another tile. In other words, T is a vortex of H. □

Remark 1. It is obvious that the assertions of Theorems 1 and 2 hold in the case of unilateral tilings with squares of an arbitrary number n (≥ 2) of distinct sizes.

Lemma 1. Let H be a U3-tiling of the plane with squares of sizes λ_{1}, λ_{2}, λ_{3}. Then at least one λ_{1}-tile has a common point with a pair of tiles of sizes λ_{2} and λ_{3}, respectively.

Proof. Assume, for contradiction, that no λ_{1}-tile in H has the required property, and choose a λ_{1}-tile T ∈ H. Since T is a vortex (see Theorem 1), there are four tiles neighbourly to T. By the assumption, all these tiles are congruent to each other.

First consider the case when all these four tiles are of size λ_{2}. Since each of them is a vortex (see Theorem 2), there are four more λ_{1}-tiles, as shown in Figure 5(i). Again by the assumption, each of these new λ_{1}-tiles is surrounded by four λ_{2}-tiles. By continuing this consideration, we obtain the tiling of the whole plane with squares of sizes λ_{1} and λ_{2}, as shown in Figure 1(i). The last statement contradicts the fact that H is a U3-tiling.

Figure 5

Now consider the case when all four tiles neighbourly to T are of size λ_{3}. We claim that also in this case there are four additional λ_{1}-tiles covering right exterior angles formed by the union of T and these four λ_{3}-tiles. Indeed, assume for a moment that one of these new tiles, say S, is of size λ_{2}, as shown in Figure 5(ii). Since S is a vortex, there is a λ_{1}-tile R neighbourly to S as shown in Figure 5(ii). In this case R satisfies the conclusion of Lemma 1, a contradiction. Then, by using the claim, we finish the proof as in the first case. □

Figure 6

Figure 7

Remark 2. We cannot assert that under the hypothesis of Lemma 1 every λ_{1}-tile has a common point with two noncongruent neighbourly tiles. For example, all neighbourly tiles of the shaded λ_{1}-tile in Figures 6 and 7 are either of size λ_{2} or of size λ_{3}, respectively. In Figure 6 (Figure 7, respectively), besides the central λ_{1}-tile we have four ”rays” of λ_{2}-tiles (λ_{3}-tiles, respectively), and between any two neighbouring ”rays” there is a packing of λ_{1}-tiles and λ_{2}-tiles (λ_{3}-tiles, respectively), as in Figure 1(i). (The ”rays” in Figure 6 are discontinuous.)

Theorem 3. Any U3-tiling of the plane with squares of sizes λ_{1}, λ_{2}, λ_{3} has a λ_{3}-tile which is not a vortex.

Proof. Due to Lemma 1, there is a λ_{1}-tile T_{1} (that is a vortex by Theorem 1), having a common point with two noncongruent neighbourly tiles. Moreover, there is at least one such common point, with any given cyclic order of the sizes of squares adjacent to it. Thus there exists a side [a, b] of T_{1} which belongs to a side [a, e] of a λ_{3}-tile T_{3}, and b is a vertex of a λ_{2}-tile T_{2}. Let [b, f] be the side of T_{2} having common relative interior points with [a, e].

First we are going to prove that [a, e] is the union of [a, b] and [b, f]. Denote by [f, g] the side of T_{2} adjacent to [b, f]. Since T_{2} is a vortex and since [a, f] is a proper extension of [b, f] in skel H, there is a proper extension [f′, g] of [f, g] in skel H. Hence [a, e] is covered by the union of [a, b] and [b, f]. At the same time [a, e] is not a proper part of [a, f], since otherwise the segment [e, f] would be of length smaller than λ_{1}, i.e., it could not be on a side of any tile in H, different from T_{2}. Hence [a, e] = [a, b] ∪ [b, f].

From the fact that both T_{1} and T_{2} are vortices it follows that the segment [a, e] is not properly extendable inside skel H. Thus T_{3} is not a vortex. □

Figure 8

Remark 3. Observe that some U3-tilings can have vortices of the largest size. For example, the shaded squares in Figure 8 are vortices. In the figure, besides the central λ_{3}-tile we have four discontinuous ”rays” of λ_{1}-tiles, and between any two neighbouring ”rays” there is a packing of λ_{2}- and λ_{3}-tiles, as in Figure 1(i).

By considering the tiling shown in Figure 1(ii) and from the proof of Theorem 3 we conclude the following corollary, mentioned in [6], p. 81, without proof.

Corollary 1. Let λ_{1}, λ_{2}, λ_{3} be any three positive real numbers such that λ_{1} < λ_{2} < λ_{3}. There exists a U3-tiling of the plane with squares of sizes λ_{1}, λ_{2}, λ_{3} if and only if λ_{1} + λ_{2} = λ_{3}.

2. Neighbourly Environments

In this section we describe possible combinations of the placement of tiles in a U3-tiling, neighbourly to a given λ_{i}-tile, i = 1, 2, 3, that we will call neighbourly environment of the tile.

Lemma 2. No λ_{3}-tile of a U3-tiling has a point in common with two distinct λ_{2}-tiles.

Proof. Assume, for contradiction, that a λ_{3}-tile T has a point a in common with two distinct λ_{2}-tiles S_{1}, S_{2}. Since S_{1} and S_{2} have no common side, a is a vertex of T and of S_{1}, say. If a were an interior point of a side of S_{2}, then S_{2} would not be a vortex. Hence a is also a vertex of S_{2}. Now, again using the fact that both S_{1} and S_{2} are vortices, we conclude that no tile covers the right angle with apex a exterior to S_{1} ∪ T ∪ S_{2}. □

Theorem 4. Let H be a U3-tiling of the plane with squares of sizes λ_{1}, λ_{2}, λ_{3}. Then Figures 9 and 10 describe all (up to congruence) neighbourly environments of a λ_{1}-tile and of a λ_{2}-tile, respectively.

Proof. Since any of the neighbourly environments depicted in Figures 9 and 10 occurs in one of the tilings shown in this paper, it remains to prove that no other combination of neighbourly tiles exists.

From the fact that any λ_{1}-tile is a vortex it easily follows that no two λ_{1}-tiles have a common point. Figures 9(i)–(vi) show that, for a given λ_{1}-tile, any combination of neighbourly λ_{2}-tiles and λ_{3}-tiles is possible.

Recall that any λ_{2}-tile is a vortex. With the notation of Figure 3, the neighbours of T along [a, b], considered in the order from a to b, are either a λ_{3}-tile, or a λ_{1}-tile, or a λ_{1}-tile and a λ_{3}-tile, respectively. Together with Theorems 1 and 2, this condition implies that there are no more possible neighbourly environments of a λ_{2}-tile than those shown in Figures 10(i)–(vi). □

Figure 10

Lemma 3. Let H be a U3-tiling of the plane with squares of sizes λ_{1}, λ_{2}, λ_{3}, and let [a, b] be a side of a λ_{3}-tile T and S_{1}, S_{2} be two λ_{1}-tiles such that their sides [c, a] and [b, d] together with [a, b] form a line segment [c, d]. Then λ_{2} = 2λ_{1}, and, up to congruence, there are exactly six neighbourly environments of T including T, S_{1}, S_{2} as shown in Figure 11.

Proof. First we prove that no other neighbourly environments exist than those in Figure 11. Since both S_{1}, S_{2} are vortices, T, S_{1}, S_{2} lie on the same side of the segment [c, d], and [c, d] is the union of sides of some tiles not overlapping T ∪ S_{1} ∪ S_{2}. Clearly, none of these new tiles is of size λ_{1}. Hence their number is two, one of them being a λ_{2}-tile and the second being a λ_{3}-tile. This implies λ_{2} = 2λ_{1}.

Denote by e, f the other two vertices of T such that a, b, e, f are ordered according to an orientation of T. Let V_{1} and V_{2} be the tiles neighbourly to both T, S_{1} and T, S_{2}, respectively, like in Figure 11. If both V_{1}, V_{2} are λ_{3}-tiles, then we have one of the configurations depicted in Figures 11(i) and 11(ii). If one of V_{1}, V_{2} is a λ_{2}-tile and the second is a λ_{3}-tile, we have one of the configurations depicted in Figures 11(iii)–(vi).

Figure 11

It remains to show that both V_{1}, V_{2} cannot be of size λ_{2}. Indeed, assume that both V_{1}, V_{2} are λ_{2}-tiles and [g, f], [e, h] are their sides such that [g, h] is a line segment including [f, e]. Then, since both V_{1}, V_{2} are vortices, [g, h] is the union of sides of some tiles not overlapping T ∪ V_{1} ∪ V_{2}. It is easy to see that these new tiles form an ordered sequence (starting from g) either of the form {λ_{1}-tile, λ_{3}-tile, λ_{2}-tile, …}, contradicting Theorems 1 and 2, or of the form {λ_{3}-tile, λ_{2}-tile, …}, contradicting the fact that V_{2} is a vortex.

For finishing the proof of Lemma 3, we give examples of U3-tilings containing each of the neighbourly environments in Figure 11. Indeed, the environments (i), (ii), and (iii) occur in the U3-tilings from Figures 12(i)-(iii), respectively. The environment (iv) occurs in the U3-tiling from Figure 12(ii), and both environments (v) and (vi) occur in the U3-tiling from Figure 12(iv). □

Theorem 5. Let H be a U3-tiling of the plane with squares of sizes λ_{1}, λ_{2}, λ_{3}.

1) If λ_{2} ≠ 2λ_{1}, then, up to congruence, Figure 13 describes all neighbourly environments of a λ_{3}-tile.

2) If λ_{2} = 2λ_{1}, then, up to congruence, there are exactly twelve neighbourly environments of a λ_{3}-tile, namely the six ones shown in Figure 11, and the six further ones shown in Figure 13.

Proof. Since any of the neighbourly environments in Figures 11 and 13 occurs in one of the tilings shown in this paper, it remains to prove that (except for those in Figures 11 and 13) no other neighbourly environments exist.

Let T be a λ_{3}-tile with the vertices a, b, c, d, taken according to an orientation of T. Clearly, every side of T can touch at most one λ_{1}-tile.

Figure 12

First we consider the case λ_{2} ≠ 2λ_{1}. From Lemma 3 it follows that no two λ_{1}-tiles can touch T as the squares S_{1} and S_{2} in Figure 11. (In fact, cases (a)–(e) below use only this consequence, but not the assumption λ_{2} ≠ 2λ_{1} itself.)

(a) Assume first that T is neighbourly to four λ_{1}-tiles. By the above arguments, these λ_{1}-tiles are placed as shown in Figure 13(i). By Theorem 2 and Corollary 1, it is easily seen that in this case there are four additional λ_{3}-tiles neighbourly to T.

(b) Let T neighbour three λ_{1}-tiles and, without loss of generality, these three λ_{1}-tiles be placed as shown in Figure 13(ii). Then two λ_{3}-tiles touch T at [a, d] and [a, b], respectively.

We claim that T neighbours a λ_{2}-tile along the side [b, c]. Indeed, assume that T neighbours a λ_{3}-tile along [b, c]. Then, since there are only three λ_{1}-tiles neighbouring T, the vertex c belongs to a λ_{2}-tile touching [c, d], and hence one additional λ_{3}-tile touches T at [c, d]. The last is impossible, since the λ_{1}-tile containing the vertex d and neighbouring T is a vortex.

Now we claim that along the side [c, d] the tile T neighbours one λ_{2}-tile and one λ_{3}-tile, as shown in Figure 13(ii). Indeed, if this λ_{2}-tile and this λ_{3}-tile were neighbourly to T in the inverse order, this λ_{2}-tile would not be a vortex, which is impossible by Theorem 2.

(c) Let exactly two λ_{2}-tiles neighbour T. First we consider the case when these two λ_{1}-tiles are placed as shown in Figure 13(iii) or Figure 13(iv).

If they are placed as shown in Figure 13(iii), then, as above, T neigbours a λ_{3}-tile along

Figure 13

[a, d], the side [c, d] touches one λ_{2}-tile and one λ_{3}-tile (in the order from d to c), [b, c] touches one λ_{2}-tile and one λ_{3}-tile and, finally, [a, b] touches one λ_{2}-tile and one λ_{1}-tile.

If two λ_{1}-tiles are placed as shown in Figure 13(iv), then, by similar arguments, we obtain the neighbourly environment depicted in this figure.

It remains to show that Figure 13(iii) and 13(iv) describe the only possible placements of the two λ_{1}-tiles. Indeed, the only other possibility would be that, e.g., these λ_{1}-tiles (S_{1} and S_{2}, say) have their lower right corners at b and d, respectively. Let [e, b] be one of the horizontal sides of S_{1}. Since the λ_{1}-tiles are vortices, T neighbours at [c, d] a λ_{2}-tile and a λ_{3}-tile (in some order), where one side of the lower tile contains c in its relative interior. Then [e, c] is the union of sides of an alternating sequence of λ_{2}- and λ_{3}-tiles neighbouring T, which is impossible by λ_{2} < λ_{3} < λ_{1} + λ_{3} < λ_{2} + λ_{3}.

(d) Let only one λ_{1}-tile touch T, as shown in Figure 13(v). As above, we have that [c, d] touches one λ_{2}-tile and one λ_{3}-tile in this order. Then, necessarily, we have the configuration depicted in Figure 13(v).

(e) Finally, let no λ_{1}-tile neighbour T. In this case, analogously to Theorems 2 and 4 (see Figure 10(i)) we have the neighbourly configuration depicted in Figure 13(vi).

Now let λ_{2} = 2λ_{1}. If no two λ_{1}-tiles touch T as the squares S_{1} and S_{2} in Figure 11, we can use the considerations from (a)–(e) above (as it has been mentioned at the beginning of the proof). On the other hand, the case when two such λ_{1}-tiles exist has been considered in Lemma 3; all the corresponding neighbourly environments are shown in Figure 11. □

3. Some Global Properties of U3-tilings

We will say that a tiling of the plane with squares is simple provided no proper subfamily of at least two tiles form a convex region, possibly unbounded. From the definitions it easily follows that any simple tiling is unilateral. At the same time, with the both-way unbounded strip formed by squares of four distinct sizes (cf. Figure 14) one can easily construct a unilateral tiling which is not simple. We show below that a unilateral tiling with squares of at most three distinct sizes is always simple.

From Theorems 1, 2, and Remark 1 we conclude the following assertion, implying that any unilateral tiling with squares of two sizes is simple.

Figure 14

Theorem 6. For any pair of real positive numbers λ_{1} < λ_{2} there is, up to congruence, a unique unilateral tiling of the plane with squares of sizes λ_{1} and λ_{2}, respectively (this tiling is depicted in Figure 1(i)).

Our next assertion shows that a similar fact holds for U3-tilings.

Theorem 7. Any U3-tiling of the plane is simple.

Proof. Assume the existence of a non-simple U3-tiling with squares of sizes λ_{1}, λ_{2}, λ_{3}. Then a proper subfamily of at least two tiles form a convex region R, possibly unbounded. The region R may be a rectangle, a strip (one- or both-way unbounded), a quarter-plane, or a half-plane. It is known (see [1]) that no rectangle can be simply partitioned into squares of at most four distinct sizes. Hence R is unbounded and contains a ray l in its boundary. We remark that no tile of size λ_{1} or λ_{2} has a side in the relative interior of l, since otherwise it would not be a vortex. Hence some subray of l is covered by infinitely many sides of λ_{3}-tiles, contradicting the unilaterality of H. □

Theorem 8. If H is a U3-tiling of the plane with squares of sizes λ_{1}, λ_{2}, λ_{3}, then tiles of each size occur infinitely many times in H.

Proof. Suppose that for some i ∈ {1, 2, 3} the number of λ_{i}-tiles in H is finite. We will show that in this case H does not contain any tile of this size, getting a contradiction.

Thus, assume that the number of λ_{i}-tiles in H is finite and positive. Let j and k, j < k, be integers forming the set {1, 2, 3} \ {i}. According to Theorem 6, there is, up to congruence, a unique tiling of the plane with squares of sizes λ_{j} and λ_{k}, as shown in Figure 1(i). Moreover, even any local picture of such a tiling is unique. This implies the existence of an m × n frame F formed by λ_{k}-tiles such that all λ_{i}-tiles of H lie within F (see Figure 15). Clearly, m, n ≥ 3. Without loss of generality, we may assume that F is a frame of minimal size containing all λ_{i}-tiles.

Consider the square S_{1} depicted in Figure 15 (S_{1} ∈ H by unilaterality and the assumption on F). It is obvious that S_{1} is a λ_{j}-tile. Let [a, b] be the horizontal segment consisting of a side of S_{1} and a side of V_{2}. In what follows, we distinguish two cases.

(a) k = 3, i.e., the frame F is formed by λ_{3}-tiles. Then the tile S_{2}, whose lower right vertex coincides with the upper right vertex of V_{2} is of size either λ_{1} or λ_{2}, and hence it is a vortex. The last is only possible if S_{1} and S_{2} are congruent.

Indeed, otherwise S_{2} would be a λ_{i}-tile, with λ_{i} > λ_{j}, implying i = 2 and j = 1. Consider the part of the segment [a, b] not covered by S_{2}, say L. This subinterval L is of length λ_{1} + λ_{3} − λ_{2} (= 2λ_{1} by Corollary 1). Then L would be covered from above either by one λ_{2}-tile or by two λ_{1}-tiles, both cases contradicting unilaterality.

Since S_{1} and S_{2} are congruent, the length of L equals λ_{3}. We claim that L is covered from above by a λ_{3}-tile. Indeed, otherwise it would be covered from above by a λ_{i}- and λ_{j}-tile (in some order), contradicting unilaterality.

Repeating these considerations by moving along the squares V_{1}, V_{2}, …, V_{m}, we obtain that F can be substituted by a smaller m × (n − 1) frame containing all the λ_{i}-tiles, a contradiction.

Figure 15

(b) k = 2, i.e., j = 1 and i = 3, and the frame F is formed by λ_{2}-tiles. Then V_{3} is a vortex. That implies that S_{2} as defined above is a λ_{1}-tile, and L as defined above is covered from above by a λ_{2}-tile. As in case (a), we can substitute F by a smaller m × (n − 1) frame, getting a contradiction. □

References

[1] Bowkamp, C. J.: On the dissection of rectangles into squares I, II, III. Indag. Math. 8 (1946), 724–736; 9 (1947), 43–56; 57–63.

[2] Croft, H. T.; Falconer, K. J.; Guy, R. K.: Unsolved Problems in Geometry. Springer-Verlag, New York 1991.

[3] Dawson, R. J. M.: On filling space with different integer cubes. J. Combin. Theory A36 (1984), 221–229.

[4] Daykin, D. E.: Space filling with unequal cubes. Bull. Amer. Math. Soc. 70 (1964), 340– 341.

[5] Gardner, M.: Some packing problems that cannot be solved by sitting on the suitcase, Scientific American 241 (Oct. 1979), no. 4, 22–26.

[6] Grünbaum, B.; Shephard, G. C.: Tilings and Patterns. Freeman and Co., New York 1987.

[7] Herda, H.: Tiling the plane with incongruent regular polygons. In: Convexity and Related Combinatorial Geometry (Eds. D.C. Kay and M. Breen), Lecture Notes Pure Appl. Math. 76 (1982), 225–228.

[8] D. Schattschneider, unpublished.

Received November 5, 1997; revised version February 22, 1998