The main goal of this pamphlet is to introduce a beginner to the fun and joy of a mathematical research project. The general question we will look at concerns whether one can cut a given rectangle into smaller rectangles having specified dimensions. When this is possible, we say that the larger rectangle can be tiled with rectangles having the specified sizes. For example, can a 25 x 25 square be tiled with 2x2 and 3x3 squares? (Later on, we will find that this is not possible).


Figure 0
Can a 25 x 25 square be tiled
with 2x2 and 3x3 squares?

The topic is not so simple as it might sound at first, and in fact there are some unsolved problems in this area. It is hoped that the reader will become interested and make some discoveries of his own. But more important is to experience an intellectual adventure—to try to understand and make clear for others something otherwise unknown or tangled in confusion.

Let us begin by being a bit more specific about the particular questions dealt with in this pamphlet. A block is k-dimensional rectangular solid, and to keep things tame, k will be 1, 2, or 3. Furthermore, the edges of a block are line segments with positive integer lengths; that is, one of the numbers 1, 2, 3, etc. One-dimensional blocks are just line segments with integral lengths. Two-dimensional blocks are rectangles with integral sides; for example, a domino is a 1x2 block. Finally, three-dimensional blocks are shapes like bricks whoses faces are two-dimensional blocks. Figure 1 shows a 3x4 block tiled with dominoes and 1x3 blocks. We say a block is tiled with other blocks when the larger block is covered with the other blocks and none of these have any interior points in common (they don't overlap).


Figure 1
A 3x4 block tiled with
three dominoes and two 1x3 blocks

We want to investigate the question "Which blocks can be tiled with blocks having any of a specified set of shapes?" To understand a general question it is usually a good idea to pose and solve a simple specific instance. For example, which blocks can be tiled with 2x3, 2x4, and 3x4 blocks? Some readers will want to stop reading, get out pencil and paper, and solve this problem for themselves. That is a good idea. Then come back to reading and compare your findings to what is explained here.

Notice that the blocks to be used in the tilings all have even integers for their areas. Since a sum of even numbers is always an even number, it follows that blocks with odd integer area cannot be tiled with 2x3, 2x4, and 3x4 blocks. What about blocks with even area? If an m x n block has even area, then either m or n (or perhaps both) is even. Say m = 2h, with h = 1, 2, ... It is easy to check that 2x3 and 2x4 blocks tile 2xn blocks for all but a finite number of values of n (n =1, 2, and 5 are the exceptional values). Hence, once could cut a 2h x n block into h 2 x n blocks, and then tile the 2 x n blocks with 2x3 and 2x4 blocks, provided n is not equal to 1, 2, or 5. It is impossible to tile a 2h x 1 block with the three given blocks. This leaves the problem of determining the values of h for which one can tile a 2h x 5 block. This can be done by combining tilings of 2h x 3 and 2h x2 blocks for h = 2, 3, 4, ... We observed already that a 5 x 2 block cannot be tiled with the three block sizes given. Thus, with the exception of blocks only one unit wide, all but a finite number of block with even area can be tiled with 2x3, 2x4, and 3x4 blocks. (The exceptions are 1 x 2h for h=1, 2, ... and 2x2, 2x5). No block with odd area can be tiled with these three blocks.

This constitutes a satisfactory answer to the problem just posed—just an instance of the general problem.

Maybe some critical readers noticed that a fairly substantial problem was glossed over in the last section. The following claim was made:

"It is easy to check that 2x3 and 2x4 blocks tile 2 x n blocks for all but a finite number of values of n (n=1, 2, and 5 are the exceptional values)."

This is really a one-dimensional tiling problem. We have to show that every positive integer n, except 1, 2, and 5, can be expressed as a sum of 3's and 4's. To see this, first note that every multiple of 3 is a sum of 3's. If n is not a multiple of three, then n has remainder 1 or 2 when divided by three. Say the remainder is 1. Then n = 3h+1 for some h=0,1,... Of course, h = 0 is one of the exceptional cases because then n=1. If h is greater than 0, then n=3h+1=4+3(h-1), so n is sum of one 4 and h-1 3's. If n has remainder 2 when divided by 3, we can write n =3h+2 for some h=0,1,.... If h=0, then n=2, again an exceptional value. If h=1, then n=5, again an exceptional value. If h > 1, then n=3h+2 = 4+4+3(h-2), and n is sum of 2 4's and h-2 3's. Thus, every positive number n except 1,2, or 5 can be expressed in the form 3x+4y with x and y non-negative integers 0,1,2,...

If one thinks about it, the problem just solved is typical of certain one-dimensional problems likely to come up in higher dimensional tiling problems.

The notion of packing or tiling a box with bricks carries over to three dimensions in an obvious way. Figure 3 shows how to pack six 1x2x2 bricks into a 3x3x3 box. Of course, this can be made into a tiling if we are also supplied with three 1x1x1 bricks to use in the packing (this makes a nice puzzle!).


Figure 3
A 3x3x3 box packed with six 1x2x2 bricks. There are three 1x1x1 holes in this packing; one of the holes is in the center of the box.

We are going to pursue various problems concerning tiling and packing boxes with bricks. A good exercise for the reader at this point is to stop reading and pose some problems on this topic. Asking good questions is a vital part of mathematical creation. By chance, some of the reader's questions might coincide with those taken up here, but more likely, they will be different. Our problems are used as illustrations of research methods, and the reader's questions might serve this purpose just as well or better!

Seeking general knowledge usually begins with particular experience. For example, Figure 4 shows a rectangle tiled with 2x3 bricks. Think of some general problems suggested by this example:

(1) Which m x n boxes can be tiled with 2 x 3 bricks?

(2) If an m x n box cannot be tiled with 2x3 bricks, what is the maximum number of 2x3 bricks one can pack into this box?

Asking good questions usually depends on having some experience with the subject. If we pursue one of the two questions just posed, more ideas will come to us.

Before reading what we have to say about this question, the reader ought to get a pad of engineering paper with a light grid of squares printed on it. This pad will act as a laboratory for doing experiments. In this case, start drawing arrays of 2x3 bricks and see what sort of boxes can be filled. Write down your conclusions and resume reading. No doubt you will find out just what is about to be explained here.

The most obvious sort of box one can tile with 2x3 bricks can be cut into rows 2 units wide, and columns 3 three units wide. If there are r rows and c columns, the box will have dimensions 2r x 3c, as shown in Figure 4. Of course, such a box can be tiled with 2x3 bricks.


Figure 4
Packing a rectangle with 2x3 bricks.

Now we have a big collection of boxes with various dimensions (2x3, 4x3, 6x3, ..., 2x6, 4x6, 6x6, ...., 2x9, 4x9, 6x9....) all tiled with 2x3 bricks. The good idea here is to realize that all these boxes could be used as bricks themselves to tile even larger boxes. For example, if two boxes have a side the same length, one could push the boxes together along this common side to form a larger box tiled with 2x3 tiles. For example, the 2x6 and 3x6 boxes both have an edge with length 6, so they can be put together to form a box with dimensions 5x6 as shown in Figure 5.


Figure 5
Five 2x3 bricks in a 5x6 box.

This box is something new in that it does not have one side a multiple of 2 and the other side a multiple of 3. When does one get something new by selecting two boxes tiled as in Figure 4, each having an edge the same length, and the pushing them together along this edge? If you did not think about this before now, stop reading this, and think about it!

If one puts together two boxes tiled as in Figure 4 and the bricks inside the boxes have the same orientation, one just gets another box of the same sort—that is, nothing new. See Figure 6 for examples.


Figure 6
Some combinations that produce nothing new.

Thus, if we hope to get something new, we have to combine boxes along a common edge so that the orientations of the bricks inside the two boxes are different. Say the two boxes we plan to combine have dimensions 2r x 3c and 2R x 3C with the bricks inside having orientation 2x3 (that is, vertical dimension 2, horizontal dimension 3). To get something new by joing these boxes, we want to turn one of them 90 degrees so that the boxes inside are oriented differently, and then join them along a common edge. In numerical terms, we want 2r = 3C say (See Figure 7).


Figure 7
Combining boxes to get something new.

The condition 2r = 3C = w on the width w of the side common to the two boxes tells us that w has to be a multiple of 2 and a multiple of 3. That is, w has to be a multiple of 6. The other side of the new box has to have the form l = 3C+2R. This situation is summarized in Figure 8.


Figure 8
A new sort of box tiled with 2x3 bricks.

Together, Figure 4 and Figure 8 show two simple strategies for tiling boxes with 2x3 bricks. Usually, if a box can be tiled with 2x3 bricks, there are many different ways to do it. Could there be boxes that can be tiled with 2x3 bricks but that cannot be tiled by the methods suggested by Figures 4 and 8? It turns out that no such boxes exist, and the reader is encouraged to stop reading and think of an explanation.

Here is our explanation. If an m x n box can be tiled with 2 x 3 bricks, then the area of the box mn must be divisible by 6, the area of each brick. In fact, if k bricks are used, the area of the box is 6k = mn.

There is a general principle involved here. If an m x n box can be tiled with a x b bricks, then the area of the box bm is divisible by the area of the brick. That is, when mn is divided by ab we get a whole number as the quotient. In fact, mn/ab is the number of bricks one would use in the tiling.

Returning to 2x3 bricks, we reason that since mn is a multiple of 6, we can have two cases:

(1) One side of the box is a multiple of 2 and the other side is a multiple of three,

(2) One side of the box is not divisible by 2 or 3, but the other side is a multiple of 6.

The method of Figure 4 is used in the first case, and the method of Figure 8 is used in the second case. One detail needs to be emphasized in the latter case. If some m x n box can be tiled with 2 x 3 bricks in any way whatsoever, then each side of the box, the one of length m say, must be composed of sides of the brick which have length 2 and 3. Thus, if u of the bricks along side m use the side of length 2 while v of the bricks along side m use the side of length 3, m = 2u+3v. This is an example of a general principle: if an m x n box can be tiled with a x b bricks, then both m and n can be expressed in the form

m = a x₁ + b y₁ and n = a x₂ + b y₂,

where x₁, x₂, y₁, and y₂ are counting numbers; that is, x₁, x₂, y₁, y₂ have to be selected from the set N = {0,1,2,...}.

If n = a x + b y with x and y counting numbers, we say n is a linear combination of a and b.

Getting back to tiling with 2 x 3 bricks, we are led to a new question. Which whole numbers are linear combinations of 2 and 3? Stop reading and solve this problem!

Maybe the reader's solution was something like this. The even numbers 2, 4, 6, 8, 10, ... are just the multiples of 2, so

n = 2 · x + 3 · 0 = 2 · x

is a linear combination of of 2 and 3 when n is even. If is an odd number greater than 1, ie, 3, 5, 7, 9, 11, ...., we can write

n = 2x + 3

for some x = 0,1,2,... . Hence, every positive integer greater than is a linear combination of 2 and 3.

We can sum up tiling boxes with 2x3 boxes as follows: If an m x n box can be tiled with 2 x 3 bricks, then both m and n must be linear combinations of 2, 3. That is, both m and n must be bigger than 1. Also, mn has to be a multiple of 6. There are two cases: if one side is a multiple of 2 and the other side is a multiple of 3, we can cut the box into 2x3 bricks at once. The second case involves having one side a multiple of 6, with the other side, of length n say, expressible as a linear combination of 2 and 3. That is n is greater than 1 and n=2u+3v where u and v belong to the set N={0,1,2,...}. Now we cut the mx box into two boxes, m x 2u and m x 3v and tile the m x 2u box with 3 x 2 bricks, and the m x 3v box with 2 x 3 bricks.

This result gives us an algorithm to solve any problem having the form "Can one tile an m x n box with 2 x 3 bricks? And if so, how?" where m and n are given whole numbers. First, if m and n are both greater than 1, we check to see if 6 divides mn without remainder. If not, stop, because there is no tiling. If so, we check to see if one side is a multiple of 2 and the other a multiple of 3. If so, cut the rectangle into 2 x 3 bricks at once. Otherwise, one side is a multiple of 6, and the other side is a linear combination of 2 and 3. The tiling is accomplished as explained above.

Exercise: Which of the following boxes can be tiled with 2x3 bricks?

(a) 30 x 17
(b) 26 x 20
(c) 100 x 33
(d) 36 x 36
(e) 1000 x 570

An obvious generalization of the problem treated in the last section is the following: Which m x n boxes can be tiled with a x b bricks? The reader should go back over the last section and try to identify anything there that might apply to this new general problem. We found three ideas which might be useful.

Observation 4.1: If an m x n box can be tiled with a x b bricks, then mn is a multiple of ab. Furthermore, mn/ab is the number of bricks used in the tiling.

Observation 4.2: If an m x n box can be tiled with a x b bricks, then both sides of the box (m and n) are linear combinations of a and b. That is, there exist nonnegative integers x₁, x₂, y₁, and y₂ belonging to the set N = {0,1,2,...} such that m = a x₁ + b y₁ and n = a x₂ + b y₂.

Observation 4.3: If both an m x r box and an m x s box can be tiled with bricks, then an m x (r+s) box can be tiled with a x b bricks.

Observation 4.4: If an m x n box can be tiled with u x v bricks, and if a u x v box can be tiled with a x b bricks, then an m x n box can be tiled with a x b bricks.

Observations 4.3 and 4.4 are both useful special cases of the more general observation that boxes tiled with a x b bricks can be used as bricks themselves. Larger boxes tiled with these new brick sizes can also be tiled with a x b bricks.

Let us try to pose some useful questions in light of the observations we have just listed. The first observation gives us a condition we can easily check. The second observation involves checking whether a given number, n say, is a linear combination of two other given numbers a and b. This is really a one-dimensional tiling problem: which intervals of length n can be tiled with intervals of lengths a and b? This is an interesting problem usually treated in elementary number theory. We are going to devote a whole section to this problem and show the reader how to discover some of the theory.

Another idea arises from the listed observations, but this is subtle. It is only fair to indicate to the reader that our knowledge of brick tiling theory prompts us to introduce this idea at this point, early in the game. We want to point out a consequence of the fourth observation. Obviously, 1 x a bricks tile an a x b box; thus, if an a x b brick tiles an m x n box, then a 1 x a brick tiles an m x n box. So, any box that can be tiled with a x b bricks is among the larger collection of boxes that can be tiled with 1 x a bricks. This gives rise to an interesting condition that we will discover later. Right now it is important to note that among all the problems we have set ourselves, tiling with 1 x a bricks is a special case that might help us with the general case. Whatever conditions have to be met for tiling a box with 1 x a bricks must also be met for tiling a box with a x b bricks. We will deal with 1 x a tilings in the next section, and look into linear combinations in the section after that.

To really understand the problem posed for this section, the reader should treat some cases and get a complete answer. Probably dealing with the cases a = 2, 3, and 4 will be enough. After you have some insight, start reading again.

Let us go over the cases a = 2, 3, 4. The first two cases are easy because of Observation 4.1. Namely, if an m x n box can be tiled with 1 x a bricks, then a must divide mn. But if a = 2 and 2 divides mn, then 2 divides m or 2 divides n. The same statment can be made with 3 in place with 2. In fact, the same statement can be made for any number a that is a prime number (such as 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, ...); that is, the number a is not a porduct of two whole numbers bigger than 1. Obviously, if one side of an m x n box is a multiple of a, then the box can be tiled with 1 x a bricks.

When a is not a prime, we have some additional problems. For example, if a is 4, there are boxes with neither side a multiple of a4, but the area is a multiple of 4. The smallest box like this is 2 x 2, but there are infinitely many others: 2 x 6, 2 x 10, 2 x 14, ..., 6 x 6, 6 x 10, 6 x 14, ...., 10 x 10, 10 x 14, ... (Such boxes have the general form 4m+2 x 4n+2). It turns out, however, that none of these boxes can be tiled with 1 x 4 bricks! Why not?!

Now we introduce an ingenious idea the author learned by other examples from Solomon Golomb.

We color the square cells of the plane red, white, bule, and green as indicated in Figure 9. There is a basic 4 x 4 pattern that is repeated periodically. This coloring of the plane has the property that no matter where we put down a 1 x 4 brick so that it covers 4 cells exactly, the cells will be colored with each of the four colors. Thus, any region composed of cells that is tiled with k 1x4 bricks will have exactly k cells red, k cells white, k cells blue, and k cells green. We say such a region is equi-colored. This means that a necessary condition for a tiling of a cellular region with 1x4 bricks is that the region be equi-colored.


Figure 9
A 4x4 periodic coloring of the cells in the plane.

A consequence of this idea is that a box cannot be tiled 1x4 bricks if it is not equi-colored. For example, consider the 6x6 box shown in Figure 10, which has been colored as in Figure 9. This 6x6 box has 9 red cells, 10 white cells, 9 blue cells, and 8 green cells. Since the 6x6 box is not equi-colored, it cannot be tiled with 1x4 bricks!


Figure 10
The 6x6 box is not equi-colored.

A further observation about the 6x6 box is this: If the 6x6 box were packed with 8 1x4 bricks, the region covered would be equi-colored, having exactly 8 cells of each color. Hence, the cells that are not covered with the 8 bricks must consist of 1 red cell, 2 white cells, 1 blue cell, and no green cells, no matter how the 6x6 box is packed.

The reader should now try to show that an m x n box having both m and n not multiples of 4 is never equi-colored by the coloring shown in Figure 9. This shows that such boxes cannot be tiled with 1x4 bricks. One way to attack this problem is to use the fact that if a region can be tiled with 1x4 bricks, then it is equi-colored. For example, consider a (4m+2) x (4n+2) box. If we cut the 2x2 lower left corner out of the box, the region left over can be tiled with 1x4 bricks in an obvious way (See Figure 11). Since a 2x2 box is not equi-colored, it follows that the entire (2m+2) x (2n+2) box is not equi-colored. (The disjoint union of an equi-colored region with a non-equi-colored region is not equi-colored). Hence, such a box cannot be tiled with 1x4 bricks.


Figure 11
A (4m+2) x (4n+2) box is not equicolored:
The number of green cells is exceeded by 1 red cell.

To show that a (4m+r) x (4n+s) box is not equi-colored when 1 <= r,s <= 3, we just have to show that an rxs box is not equi-colored. Of course, if rs is not divisible by by 4, the number of colors, then r x s box cannot be equi-colored (there have to be rs/4 cells of each color in an equi-coloring). This means one has only to deal with the case r=s=2, and this was done already.

Now we want the reader to generalize the coloring shown in Figure 9 so that no matter how one places a 1xa brick on a cells, one cell of each color is covered. Call this an a-coloring. An a-coloring has the property that any region tiled with 1xa bricks is equi-colored by an a-coloring. An argument has to be given that an (ma+r)x(na+s) box with 1 <= r,s < a-1 is not equi-colored by an a-coloring. This will prove that an m x n box is equi-colored by an a-coloring just when m or n is a multiple of a. This leads to a result first proved by the great Dutch mathematician N. G. deBruijn:

Theorem 5: An m x n box can be tiled with 1 x a bricks just when m or n is multiple of a.

Just to be sure the problem is understood, consider an example: say a=4, and b=7. Asking if a given integer n is a linear combination of 4 and 7 means: Do there exist non-negative integers x, y (in the set N = {0, 1, 2, ..}) such that n = 4x + 7y? Recall that we were interested in problems like this in connection with tiling boxes with 4x7 bricks. It turns out that every whole number not less than 18 is a linear combination of 4 and 7. The reader should look for a convincing argument that this is so. We will give one in the next paragraph.

We want to say something about the set of all linear combinations of 4 and 7; this means we form all numbers having the form 4x+7y where x and y range over N = {0,1,2,...}. If this is done in a systematic way, the set of values assumed by 4x+7y is easy to understand. We formed the array shown in Figure 12 as follows: In the first row, we put y=0 in the expression 4x+7y, and then let x take the values 0,1,2,... respectively. In the second row, we put y=1 in the expression 4x+7y and again let x range over N. In the third and fourth rows we put y=2 and y=3 respectively, and let x range over N. Also, the rows have been shifted so that the columns form blocks of consecutive integers.


Figure 12
The linear combinations of 4 and 7.

It is easy to see by looking at this array of linear combinations of 4 and 7 that every positive integer greater than 17 appears in the first 4 rows of the table. Also, the rows beyond the fourth row are superfluous becuase they are always part of one of the first four rows. For example, elembers of the fifth row have the form

4x + 28 = 4 (x + 7) + 7 · 0
where x ranges over N. But 4 (x + 7) + 7 · 0 is the form of a number in the first row. In general, an element in row y has the form 4x+7(y-1) with x in N. Every number y greater than 3 has exactly one of the forms 4q+1, 4q+2, 4q+3, or 4q+4 for some q in N. Let us say y = 4q+r where r is 1, 2, 3, or 4. This means an element

4x+ 7(y-1) = 4x + 7(4q+r-1) = 4(x+7q) + 7(r-1)
is in row y and row r for r = 1, 2, 3, 4. Hence, all the rows from the fifth onward are superfluous.

From now on, it simplifies matters to regard the array as being the first four rows of the old, larger array. We want to show that every number greater than 17 is in the array (that is, in the first four rows of the array). Notice that the seventh column of the array consists of a block four consecutive numbers, namely, 21, 22, 23, and 24. The eighth column consists of the next block of four consecutive numbers because the next element in each row is 4 great than its predecessor. Hence, the successive columns of the array present all the numbers from 21 onward in successive blocks of four consecutive numbers. Since 18, 19, 20 are in the sixth column, and 17 is not in the array, it follows that every number greater than 17 is a linear combination of 4 and 7.

We would like the reader to generalize the method used for the set of linear combinations of 4 and 7 to treat the set of linear combinations of an arbitrary pair of numbers a and b. Of course, we might as well assume a and b have no common factor greater than 1 because the set of linear combinations of d · a and d · b is d times the set of linear combinations of a and b. The result (left for the reader to prove) may be stated as follows:

Theorem 6: Let a and b be positive integers with no common prime factor. Then the set of linear combinations of a and b includes every positive integer not less than (a-1)(b-1).

It simplifies matters and there is no loss in generality if it is assumed that the sides of the brick, a and b, have no common factor greater than 1. If a and b have a common factor d with 1 < d, then an a x b box can be tiled with d x d bricks. Conversely, if an m x n box can be tiled with with d x d bricks, the both m and n are multiples of d. This means our basic unit cell could be replaced with a d x d cell and tileing with a x b bricks reduces to tiling with (a/d)x(b/d) bricks. So for now on, we suppose a and b have no common factor greater than 1.

We learned in earlier sections that necessary conditions for tiling and m x n box with a x b bricks are that mn be a multiple of ab, and both m and n must be linear combinations of a and b. Also, de Bruijn's theorem 5 tells us that either m or n is a multiple of a because an mxn box can also be tiled with 1xa bricks. For the same reason, either m or n is a multiple of b. Since a and b have no common factor greater than 1, the fact that both a and b are factors of one of the sides m and n implies mn is a multiple of ab.

There are two cases: either a and b divide different sides of the box, or they divide the same side. Say we have the first case, with m = Ma, n = Nb. Then the mxn box can be cut into an MxN array of axb bricks at once. If we have the second case, we can suppose that m=Mab and n=au+bv with u and v non-negative integers. Now we form m x au and m x bv boxes and tile them with bxa and axb bricks respectively. These two boxes can pushed together along their common edge of length m to form a tiling of an m x n box with a x b bricks.

Exercise 7.1: Can one tile a 133 x 1001 box with 35 x 42 bricks? Explain your answer.

Exercise 7.2: Can one tile a 22 x 30 box with 5 x 6 bricks?

Now we want to investigate tiling boxes with more than one shape of brick. A simple instance involves using two sizes of square bricks. We urge the reader to try to determine which m x n boxes can be tiled with 2x2 and 3x3 bricks. Use some of the ideas suggested by the 2x3 brick tilings and then return to this section.

With the 2x3 bricks, we first formed the simplest tilings possible, and then combined these tilings to make certain composite ones. It turned out no other boxes besides these could be tiled. What happens when this approach is tried with the 2x2 and 3x3 bricks? The simplest tilings involve boxes have both sides multiples of 2 or multiples of 3. Such boxes can be tiled with 2x2 bricks or 3x3 bricks, respectively.

Combining two boxes tiled with the same square brick along a common edge does not give anything new. However one usually does get something new when two boxes tiled with different squares are combined. Say a 2r x 2s box tiled with 2 x2 bricks is to be combined along a common edge with a 3u x3v box tiled with 3 x 3 bricks. Assuming the common edge is m = 2r = 3u, then m must be a multiple of 6, and the combined tiling is an m x (2r+3u) box. Conversely, an m x n box that has m a multiple of 6 and n a linear combination of 2 and 3 can be cut into two boxes with common side m, and one box tiled with 2x2 bircks and the other side tiled with 3x3 bricks.

The reader should check that no new box shapes are obtained by combining any of the boxes along a common edge that were discussed so far. That is, boxes tiled with 2x2 bricks, boxes tiled with 3x3 bricks, or a box tiled with 2x2 and 3x3 bricks formed by joining two of the former along a common edge, form nothing new. This makes us wonder if any other boxes besides these could be tiled 2x2 and 3x3 bricks. Such a box would have to have both of its sides linear combinations of 2 and 3 (but every number other than 1 is a linear combination of 2 and 3), and its area would have to be a linear combination of 4 and 9, the areas of the two bricks. For example, a 5x5 brick has area 25 = 9 + 4 · 4, but it is easy to check that one 3x3 brick and four 2x2 bricks do not tile a 5x5 box. One has to try several boxes not in the set we already know how to tile and determine if any can be tiled with 2x2 and 3x3 bricks. Probably only when failure has been met for small boxes and only when we are forced with trying to show that some hopelessly large box cannot be tiled with 2x2 and 3x3 bricks does it occur to us that a simple proof of the impossibility might be found. Let us consider some large box not among the ones we know how to tile, say a 37 x 41 box.

A 37x41 box has an area so large it can surely be expressed as a linear combination of 4 and 9. So if a 37x41 box cannot be tiled with 2x2 and 3x3 bricks, we will have to look for another reason. Why not try a coloring argument like what was used to show that 1 x a bricks only tile boxes having at least one side a multiple of a? The coloring that works this time consists of stripes as shown in Figure 13; every other column of length 37 beginning with the first one is colored black, and the rest of the columns are colored white. If the 37x41 box were tiled with 2x2 and 3x3 bricks, the 2x2 bricks would always cover 2 white cells and 2 black cells, whereas the 3x3 bricks would be of two types: those covering 6 black cells and 3 white cells, and others which cover 3 black cells and 6 white cells. Say there were x 2x2 bricks, y 3x3 bricks of the first type, and z 3x3 bricks of the second type in a tiling of the 37x41 box.


Figure 13
A coloring of a 37x41 box.

The total number of black columns in the stripe-coloring of the 37x41 box is 21, and there are 20 white columns. Hence, the number of black cells in the box is 37 · 21 and the number of white cells is 37 · 20. Now we count the number of black and white cells in the box in terms of the bricks covering them. The number of black cells is 2x+6y+3z because there are y 3x3 bricks, each cover 6 black cells, and there are z 3x3 bricks, each covering 3 black cells. Together, these three kinds of bricks cover all of the black cells, so 37 · 21 = 2x + 6y + 3z. By counting the white cells in the box in terms of the bricks covering them, we get 37 · 20 = 2x + 3y + 6z. The difference between the number of black cells and the number of white cells is

37 = 37 · 21 - 37 · 20 = 3(y-z) = 2x+6y+3z-(2x+3y-6z).

That is, we come to the conclusion that 37 = 3(y-z) if we suppose that a 37x41 box can be tiled with 2x2 and 3x3 bricks. Since 37 is not a multiple of 3, this means that a 37x41 box cannot be so tiled. What makes this argument work? Perhaps a similar argument could be used to show that other boxes cannot be tiled with 2x2 and 3x3 bricks.

In thinking over the impossibility of tiling a 37x41 box with 2x2 and 3x3 bricks, we might try some experiments such as changing one side or another of the box. If the side of length 41 is kept the same, and we replace 37 with a variable, m say, what happens? There will still be 21 black columns and 20 white columns in the stripe coloring. Hence the total number of black cells in the box is 21m, and the total number of white cells is 20m. Note that these numbers differ by m, the side of the box. Just like before, suppose the mx41 box has been tiled with x 2x2 bricks, y 3x3 bricks which cover 6 black cells and 3 white cells, and z 3x3 bricks which cover 3 black cells and 6 white cells. Counting the number of black cells in terms of the bricks which cover them, we get 21m = 2x+6y+3z; similarly, the number of white cells is 20m = 2x+3y+6z. Using these expressions, we find that the difference between the number of black cells and the number of white cells has the form m = 3(y-z). That is, m has to be a multiple of three. Is there anything special about 41, or would the conclusion that m has to be a multiple of 3 follow for other numbers as well? Almost as soon as this question is asked, one realizes that 41 can be replaced with any odd number because the number of black columns is always one more than the number of white columns in this case. This leads to an important observation.

Theorem 8.1: If a box can be tiled with 2x2 and 3x3 bricks and one side of the box is not a multiple of 2, then the other side is a multiple of three.

Suppose an m x n box can be tiled with 2x2 and 3x3 bricks; three cases are possible:

(I). Both m and n are multiples of 2.
(II). Both m and n are not multiples of 2.
(III). Exactly one of m or n is a multiple of two.

In case (I), the m x n box can be tiled with 2x2 bricks alone. In case (II), Theorem 8.1 implies that both m and n are multiples of 3, and the box can be tiled with 3x3 bricks alone. In case (III), suppose m is multiple of 2 and n is not. Then m is a multiple of 3 according to Theorem 8, so m is a multiple of 6. Since we are supposing the box can be tiled with 2x2 and 3x3 bricks, this means that n is a linear combination of 2 and 3. Say n = 2u+3v. Then we can tile an m x 2u box with 2x2 bricks (because m is a multiple of 2), and then tile an m x 3v box with 3x3 bricks (because m is a multiple of 3), and finally join these two boxes along their common edge to form a m x n box tiled with 2x2 and 3x3 bricks. Thus, we have solved completely the problem of which boxes can be tiled with 2x2 and 3x3 bricks.

Theorem 8.2: An m x n box can be tiled with 2x2 and 3x3 bricks if and only if (I) both m and n are even; (II) both m and n are multiples of 3, or (III) one of m or n is multiple of 6 and the other exceeds 1.

Now we want to generalize what was done in the last section. First, note that there is no loss in generality if it is assumed that the two side lengths of the square bricks, a and b, have no common factor greater than one. (If so, say d divides both a and b, then both the a x a box and the b x b box could be tiled with d x d bricks. This means any m x n box which can be tiled with a x a and b x b bricks can also be tiled with d x d bricks. That is, both m and n are multiples of d. Hence, we could make the basic unit cells a d x d square and deal with bricks having sides a/d and b/d instead).

So from now no, we suppose a and b have no common factor. A key role was played by Theorem 8.1; let's see if it generalizes.

Theorem 9.1: Suppose a and b have no common prime factor, and suppose an m x n box can be tiled with a x a and b x b bricks. If n is not a multiple of a, then m is a multiple of b.

Proof: We use a stripe coloring analogous to the one used previously. Color the first a columns with distinct colors c₁, c₂, ... c_a, and then repeat this coloring of the columns periodically. Since n is not a multiple of a, the number of columns colored c_a will be one less than the number of columns colored a₁ (see Figure 14).


Figure 14
A stripe-coloring with a colors.

This coloring was selected so that no matter where one places an a x a brick so that it covers cells, the number of cells with color c_i covered by the brick is always a for i = 1, 2, ... , a. How many cells of each color will be covered by the b x b bricks? The most important thing to notice about this is that all the cells in one column of the b x b brick are one color. Hence, the number of cells with color c_i covered by a b x b brick is necessarily a multiple of b. Furthermore, it turns out that only colors c₁ and c_a are relevant. If a b x b brick covers exactly u · b cells colored c₁ and covers exactly v · b cells colored c_a, we say the brick has type (ub,vb). Suppose there are exactly k types of b x b bricks in the tiling, say (bu₁, bv₁), ... (bu_k, bv_k), and the number of each type is x₁, ... , x_k, respectively. Also, suppose there are exactly x axa bricks in the tiling; such bricks have type (a,a). Finally, suppose n has quotient q and non-zero remainder r when divided by a; that is, n = aq+r with 0 < r < a. Now we count the number of cells c₁ and c_a in two ways, directly and in terms of the bricks covering them, with the result shown in Figure 15.


Figure 15
Counting cells in two ways.

Taking the difference of these two expressions gives

m = b(u₁ + ... + u_k - v₁ - ... - v_k),
which proves that m is a multiple of b. This completes the proof of the Theorem.

Suppose an m x n box can be tiled with a x a and b x b bricks. There are three cases possible.

(I). Both m and n are multiples of a.
(II). Neither m nor n is a multiple of a.
(III). Just one of m or n is a multiple of a.

In case (I), the m x n box could be tiled with a x a bricks. In case (II), since neither side is a multiple of a, Theorem 9.1 implies both sides are multiples of b, so the box could be tiled with b x b bricks. In case (III), say n is not a multiple of a, but m is a multiple of a. Theorem 9.1 implies m is also a multiple of b. Also, since the m x n box is assumed to be tiled with a x a and b x b bricks, it follows that n is a linear combination of a and b; say n = au + bv for non-negative integers u and v. Now we can split the m x n box into an m x au box and an m x bv box; the first of these boxes can be tiled with a x a bricks, and the second box can be tiled with b x b bricks since m is a multiple of a and a multiple of b.

This leads to the final result.

Theorem 9.2: An m x n box can be tiled with a x a and b x b bricks if and only if (I) m and n are both multiples of a; or (II) m and n are both multiples of b; or (III) one of m or n is a multiple of both a and b and the other is a linear combination of a and b.