Tiling Rectangles and the Plane Using Squares of Integral Sides ^†

Abstract

We study the problem of perfect tiling in the plane and explore the possibility of tiling a rectangle using integral distinct squares. Assume a set of distinguishable squares (or equivalently a set of distinct natural numbers) is given, and one has to decide whether it can tile the plane or a rectangle or not. Previously, it has been proved that tiling the plane is not feasible using a set of odd numbers or an infinite sequence of natural numbers including exactly two odd numbers. The problem is open for different situations in which the number of odd numbers is arbitrary. In addition to providing a solution to this special case, we discuss some open problems to tile the plane and rectangles in this paper.

1. Introduction

Problems of finding or computing special arrangements such as tiling, packing, stacking, tessellation, and Box-Rectangular Drawings of Planar Graphs [1,2] are categorized in the computational geometry field, with many applications in industry, science, and technology. Although most of the applications of tiling in image processing are related to different shapes of pixels and uniform polygons, tiling with non-uniform shapes also has many applications in this field. Lina Zhang and Jinhui Yu [3] present an approach for generating image mosaics with irregular tiles made up of patches taken from photographs, paintings, and texture images. They proposed a method to generate irregular tiling patterns using polygon tessellation in conjunction with a feature-based segmentation scheme, so that features in the input image can be better preserved in the generated mosaics. Edwin J. Tan et al. [4] presented a complementary image sensor with non-uniform pixel placement that enables a highly efficient calculation of the discrete cosine transform (DCT), which is the most mathematically intensive step of an image compression algorithm.

In this study, we discuss one of the cases, called perfect tiling with squares. For simplicity, we will refer to it as tiling in this paper. The main focus is on fully tiling a given rectangular area or the plane using squares of natural length that are pair-wise distinct. The tiling problem has a rich history; it was first introduced in 1903 by Dehn [5] who wanted to determine whether it is possible to find a square and cover it with smaller distinguishable squares of natural length or not, such that the squares do not overlap. It should be noted that while covering the area, there should not be any free space in between or any holes in the squares.

Moron [6] in 1925 found several rectangles that can be tiled with unequal squares. Later, in 1939, Sprague [7] solved other cases of the problem. Brooks et al. [8] associated a certain network flow of electric current through each perfect tiling of a rectangle. They showed a correspondence between the properties of the tiling and the electrical network. In 1975, Golomb [9] asked a new question, that is, whether the plane can be tiled with unequal squares or not. In 1978, Duijvestijn [10] showed that there is a unique perfect tiling for the minimum number of squares (which is 21) that can tile another square.

The question was answered positively by Henle [11] in 2008 and led to other questions being raised, such as the following:

• What subsets of the natural numbers (for the length of the squares) can be used to tile the plane?
• Can the half-plane and half-space be tiled with unequal squares and cubes, respectively?
• Is it possible to partition the set of natural numbers into two subsets, so that one subset is able to tile the plane and the other is not?
• Can infinite three-dimensional space be tiled with unequal cubes?

It has been proved by Henle [12] that it is impossible to tile the plane using a set of odd numbers, or a set of prime numbers. It has also been proved by Dawson [13] that a cube cannot be tiled with smaller cubes. However, there is no solution to tile the space with cubes. Sakait and Chang Gea [14] tried to solve some related two-dimensional packing problems using genetic algorithms. There are some special cases about the tiling squares using other squares that Tutte discussed [15]. Also, Hartman [16] in 2014 presented an algorithm for tiling the half-plane using unique integral-sided squares. In the most recent work, Panzone [17] proved some results about tiling the plane with equilateral triangles and regular hexagons with integer sides using exactly one of each family. The growth rate of the Fibonacci numbers is the golden ratio:

$$\varphi =\frac{F_{i+1}}{F_i}=\frac{1+\sqrt{5}}{2}.$$

It has been shown that a sequence with a higher growth rate than $\Phi$ cannot tile the plane. For an ascending sorted set $X=\{x_1,x_2,\dots \}\subseteq \mathbb{N}$ in which $\frac{x_{i+1}}{x_i}>\varphi$, for some i, it has been proved by Berkoff et al. [18] that it cannot tile the plane.

In this paper, the problems of tiling the plane and rectangles using a set of a few odd and many arbitrary even numbers (as the length of the squares) will be discussed. This problem has been introduced as an open problem by Henle et al. [11]. Section 2 explores the possibility of tiling the plane with a set of natural numbers with specific restrictions. Section 3 presents a solution for this problem for the rectangles, and finally, the last section concludes the paper with final remarks and future research directions.

2. Tiling the Plane

Henle [11] proved that the plane cannot be tiled with an infinite set of natural odd or prime numbers. Here, we discuss the feasibility of tiling the plane with a special set of natural numbers. The objective is to find a particular set of an infinite sequence with positive integers where the number of odd numbers is limited to $1,2,3$, or more squares.

2.1. A Subset of Even Numbers and One Odd Number

It has been proved that an infinite set of positive integers including exactly two odd numbers cannot tile the plane [11]. Consider the problem when the set contains exactly one odd positive integer.

First of all, we define two concepts, spoke and pinwheel, that we need in the rest of the paper. Extending each edge of a square from the corners makes a spoke. When four spokes turn around the square in the same direction (e.g., counterclockwise), it is called a pinwheel (see Figure 1).

Lemma 1. 

For any odd number x, there exists some set A of natural even numbers for which $A\cup x$ can tile the plane.

Proof. 

Suppose that an odd square s is given. We extend the sides of s in the form of the pinwheel. Four unbounded regions will be created around s. It would be enough to show that the regions can be tiled with four disjoint sets of even natural numbers.

Let us tile a 64 × 66 rectangle, as shown in Figure 2. The squares are considered as the following sequence:

$$Seq=2,8,14,16,18,20,28,30,36$$

Now, if we extend $Seq$ using the Fibonacci sequence, then each unbounded region around the constructed pinwheel can be tiled with

$$A=\left(a_n\right)=(2,8,14,16,18,20,28,30,36,\mathbf{64},\mathbf{130},\mathbf{194},\mathbf{324},\dots .)$$

for $n>0$. To complete the proof, we have to present four disjoint sets to tile the four constructed regions with the pinwheel around the odd number s. We apply A as a base and make four sets by multiplying A by $23,24,25$, and 26. Now it is required to prove that $23A,24A,25A$, and $26A$ are pair wisely distinct.

For $n<10$, we have $\frac{a_{(n+1)}}{a_n}<\varphi$ and all the elements of four sets should be checked one by one. According to

Table 1. Multiplications of $a_n$.

$a_n$	2	8	14	16	18	20	28	30	36	64	130	194	…
$23a_n$	46	184	322	368	414	460	644	690	828	1472	2990	4462	…
$24a_n$	48	192	336	384	432	480	670	720	864	1536	3120	4656	…
$25a_n$	50	200	350	400	450	500	700	750	900	1600	3250	4850	…
$26a_n$	52	208	364	416	468	520	728	780	936	1664	3380	5044	…

, it is clear that the multiplication of $23,24,25$ and 26 of $a_n$ are completely distinct.

Now, suppose $n\ge 10$. Then, $\frac{a_{(n+1)}}{a_n}>\varphi$ for all consecutive elements of four sets. Also, $\frac{a_{(n+1)}}{a_n}>\frac{26}{23}$ and therefore, $26a_n<23a_{(n+1)}$.

As can be seen, this is valid for $n\ge 10$:

$$26a_{(n+1)}=26a_n+26a_{(n-1)}<23a_{(n+1)}+23a_n=23a_{(n+2)}.$$

Similarly, for $n\ge 10$, we have $24a_{(n+1)}>25a_n$

Now, it can be observed that the following relation holds:

$$25a_n<26a_n<23a_{(n+1)}<24a_{(n+1)}<25a_{(n+1)}.$$

So, for $n\ge 10$, all four sequences are distinct, which shows the proof is complete. □

2.2. A Subset of Even Numbers and Three Odds

Previously, it has been proved that tiling the plane is not possible using an infinite sequence of natural numbers including exactly two odd numbers [11].

Lemma 2. 

If $X\subseteq \mathbb{N}$ includes only two odd numbers, X cannot tile the plane.

Proof. 

See proof in [11]. □

In this section, tiling the plane with an infinite set of natural numbers that includes exactly three odd numbers will be discussed.

Lemma 3. 

There exists an infinite set of natural numbers including exactly three odd numbers to tile the plane.

Proof. 

Consider three particular odd numbers $3,5$, and 11 and their arrangement, shown in Figure 3. The plane is divided into four areas. There should be four infinite sets of even numbers with no mutual tile. Two sets are available by multiplying 23 and 24 by the $\left(a_n\right)$ sequence that was used in Section 2.1. Also, as can be seen in Figure 4, the first area can be tiled using a square that has a length of 14. Then, the tiling set by the Fibonacci pattern for the first area is

$$B=\left(b_n\right)=(14,20,34,54,\dots ).$$

The third area can be tiled with squares as well with length

$$C=\left(c_n\right)=(16,24,40,64,\dots ),$$

and each sequence is continued according to the Fibonacci pattern. Now, we need to show that the four sets are mutually separated. According to the extension of the sequences and based on the Fibonacci pattern, we have:

$$B=\{14,20,34,58,88,142,230,372,602,974,1576,2550,4126,6676,10802,17478\dots \}$$

$$23A=\{46,184,322,368,414,460,644,690,828,1742,2990,4372,7362,11734,19096\dots \}$$

$$24A=\{48,192,336,384,432,480,672,720,864,1536,3120,4656,7776,12432,20208\dots \}$$

$$C=\{16,24,40,64,104,168,272,440,712,1152,1864,3026,4870,7896,12766,20662\dots \}$$

For these four sequences, it is clear that for all n, the following relations hold: $23a_n<24a_n$ and $b_n<c_n$. Also, $n\ge 12$, since $b_n<23a_n$ and $b_{(n+1)}<23a_{(n+1)}$, then $(b_n+b_{(n+1)}<23a_n+23a_{(n+1)})$ and so, $b_{(n+2)}<23a_{(n+2)}$.

For the same reason, $n\ge 12$, $24a_n<c_n$ and so clearly, $n\ge 12:b_n<23a_n<24a_n<c_n<b_{n+1}$.

It can be concluded that four sets $23A,24A,B,C$ are pairwise distinct and we can tile the plane using these sets and $\{3,5,11\}$. □

Corollary 1. 

Lemma 3 illustrates a set of infinite even squares and three odd squares $\{3,5,11\}$ that are able to tile the plane. However, by scaling all the squares, it is possible to provide many tiling sets containing exactly three odd numbers. Scaling means to multiply the length of all tiles by any desired odd and fixed number. In this case, we will find another answer to the problem, in which we will have exactly three odd tiles, different from the previous answer.

So, this section is concluded with the following theorem.

Theorem 1. 

Tiling the plane using an infinite set of natural numbers, including exactly k odd numbers, is possible for $k=1$ and $k=3$, and is impossible for $k=2$.

3. Possibility of Tiling a Rectangle

The main purpose of this section is to explore specific sets of natural numbers in which the number of odd numbers is limited. Let us begin with verifying whether or not a set of natural numbers including one odd number can tile some rectangles. Afterward, the problem will be examined for sets including $2,3,4,\dots$ odd numbers.

3.1. A Subset of Even Numbers by Considering One, Two, or Three Odd Numbers

In this subsection, the tiling area is a rectangle and there are one, two, and three odd tiles in addition to arbitrary even numbers. The results in some cases are different when tiling the plane. The rest of the section will explore each case separately.

Lemma 4. 

If $X\subseteq \mathbb{N}$ includes exactly one odd number, X cannot tile any rectangle.

Proof. 

The rectangle which may tile X has both odd length and odd width. So, for any case, there is a rectangular area A with an odd length (as shown in Figure 5) and it is not possible to tile it with even squares. □

Lemma 5. 

If $X\subseteq \mathbb{N}$ includes exactly two odd numbers, X cannot tile any rectangle.

Proof. 

Suppose $m,n\in X$ are two odd numbers. It is clear that the final covered area will be even, which means that at least one side of the rectangle must be even. Therefore, n and m must necessarily be placed in the same direction. According to assumption, $n\ne m$; therefore, an area will remain as a gap or hole (see Figure 6) whose length (like “a” or “b”) is odd and cannot be tiled with the remaining even squares. Thus, there is no rectangular area that can be tiled using a set of natural numbers including exactly two odd numbers. □

Lemma 6. 

If $B\subseteq \mathbb{N}$ includes exactly three odd numbers, then B cannot tile any rectangle.

Proof. 

Suppose $X,Y$, and Z are odd squares in B. Since the sum of every set of natural numbers that contains exactly three odd numbers is also odd, the area of the rectangle will be odd. As a result, both the length and width of the rectangle will be odd. Now, different states of placement of three odd squares can be discussed, as follows.

• All three squares are in the same direction: In this case, it is impossible to tile any rectangular area again. If all three odd squares are adjacent, the other squares will be all even, so the length of the rectangle and therefore the length of $A-(X+Y+Z)$ will be odd, which shows it cannot be tiled with even numbers (see Figure 7).
• No two squares with odd length are in the same direction, and the length of the rectangular area is greater than the sum of three squares: In this case, the dashed area will be preserved (see Figure 8). It is proved that it cannot be covered with the remaining squares, which are all even. Since there exist only three odd squares, while the rectangular area is odd, the length or width of the rectangle will necessarily be odd. Thus, the marked area cannot be covered with even tiles.
• No two odd squares are in the same direction and the length of the rectangular area is equal to the sum of three squares: In this case, the rectangular area becomes a square whose length is equal to the sum of three odd square’s edges (see Figure 9). As mentioned earlier, the total area is odd and thus both edges of the rectangle (here square) will be odd. It is clear that the marked areas in Figure 9 cannot be tiled with even squares, because the length or width of the marked area will be odd (equal to the length of its adjacent tile).
• One of the odd squares completely tiles one corner of the rectangle (Figure 10): In this case, a surface with length X and width b will remain such that, according to the problem’s assumption, the length of X is odd, and according to Lemma 5, it cannot be covered by a set that includes two odd numbers.

Finally, by considering all of the above five cases, it can be concluded that the theorem is proved and no rectangular area can be tiled with a set of natural numbers including exactly three odds. □

3.2. A Subset of Even Numbers and $k\ge 4$ Odd Numbers

In the previous subsection, the possibility of tiling a rectangle with a set of natural numbers including one, two, or three odd numbers was discussed. In this section, the question for $k\ge 4$ odd numbers will be considered.

Lemma 7. 

There is a set $X\subseteq \mathbb{N}$ including exactly four, five, or six odd numbers that will be able to tile some rectangle.

Proof. 

To prove the theorem, it is enough to find a feasible example, i.e., a set of natural numbers including four, five, or six odds which can tile a rectangle. Figure 11 shows a 32 × 33 rectangle which is tiled by the set $\{1,4,7,8,9,10,14,15,18\}$ with four odds $1,7,9,$ and 14.

To show how to tile some rectangles with a set of natural numbers that includes five odd numbers, it is enough to add a square with edge size 33 to Figure 12 and then the set $\{1,4,7,8,9,10,14,15,18,33\}$ with five odd numbers can tile the rectangle (see Figure 13). Additionally, for six odd numbers, it is enough to add a square with edge 65 to Figure 12 and the set $\{1,4,7,8,9,10,14,15,18,65\}$ can be found to tile rectangle 98 × 65 (see Figure 13). □

Lemma 8. 

There is a set A of natural numbers including $k>6$ odd numbers such that it tiles some rectangles.

Proof. 

Consider Figure 13, a set of squares with the following lengths for edges:

$$A=\{1,4,7,8,9,10,14,15,18,33,65\}$$

which can tile a 65 × 98 rectangle. The theorem with the extension of A based on the Fibonacci pattern can be proved. The last two numbers of this set are called L and R, respectively. In each step, the rectangle is extended based on the Fibonacci sequence, and so two cases may happen:

• $R+L$ is odd: Exactly one of R and L is odd. In this case, it is enough to add $L+R$ to set A (according to the Fibonacci sequence), and so the new set has one more odd number and can tile some rectangles.
• $R+L$ is even: Both R and L are odd. In this case, by adding $R+L$ to the set, the number of odd numbers does not increase and $L+R+L$ should be added to the sequence which is a new odd.

Using this approach, after tiling a rectangle with

$$A=1,4,7,8,9,10,14,15,18,33,65$$

including six odd numbers, and applying the Fibonacci pattern, the next tiling squares can be obtained as follows:

$$A=1,4,7,8,9,10,14,15,18,odd,odd,even,odd,odd,even,\dots$$

So, there is at least one rectangle which can be tiled with a set of natural numbers including exactly $k>6$ odd numbers. □

Corollary 2. 

Lemma 7 and Lemma 8 illustrate that a set of infinite even squares and particularly $k\ge 4$ odd squares can tile some rectangles. However, by multiplying (or scaling) all the squares in an odd number, it is possible to provide many tiling sets including exactly k odd numbers.

4. Conclusions and Future Work

It has been previously proved that perfectly tiling the plane is impossible when there are exactly two odd squares in the tiling set. The problems of a different number of odd squares as well as tiling a rectangle had been remained as open problems until now; these problems have been studied in this paper. It has been proved that tiling the plane using exactly one or three odd squares is possible. Additionally, it has been proved that no rectangle can be tiled with a set of natural numbers including exactly one, two, or three odd numbers. For a future direction, one can discuss the feasibility of tiling the plane for a given set of arbitrary odd numbers as well as for a set of exactly $k>4$ odd numbers. As another direction, using a given rectangle and a set of squares, it has been proved that sometimes there is no perfect tiling to cover the rectangle; one can explore the maximum coverage of the given rectangle by using squares as another direction for future works as well.