Using your Head is Permitted

March 2012 solution

Part 2:

Proof:
The following are explicit non-decomposable tilings for the lowest three N values.

N=2	N=5	N=7
1 2	3 2 4 1 5	7 6 3 2 4 1 5

Note that all of them (most notably the solution for N=7) can be viewed as the beginnings of a spiral. We begin with the rectangle labeled "1", then add "2" to its right, "3" above them, "4" to the left, and so on, going in a counter-clockwise circle around the original "1". In order to provide a solution for N>7, simply continue this spiral as many steps as are needed. (For example, when N=8, one needs to extend rectangle "7" to the left, then complete the tiling with a new rectangle.)

In order to prove that a non-decomposable tiling is not possible for any other N, let us consider the rectangles in terms of the coordinates of their top, bottom, left and right. Consider only the tops and bottoms. Let E be the number of distinct values taken by the tops and bottoms, not including the top and bottom of the original rectangle. We'll call these values "internal edges". The top and bottom of the original rectangle, we'll call "external edges".

Note the following:

1. For N>2, no non-decomposable tiling can have an entire external edge covered by a single rectangle. Therefore, the number of rectangles incident to an external edge is at least 2.
2. For a non-decomposable tiling with N>2, each internal edge must be incident to at least 3 rectangles. If it had exactly 1 rectangle above it and 1 rectangle below it, these would both share this edge, and together will form a rectangle, contrary to the assumption of non-decomposability.

On the other hand, in a non-decomposable tiling with N>2 no rectangle can go all the way from the bottom to the top, so if E=1, this internal edge separates the tiling into two sub-tilings, again refuting non-decomposability.

The only remaining case is E=2 with N=6.

Repeating the same reasoning as above, we conclude that not only are there exactly two distinct internal values for "top" and "bottom", but there are also exactly two such values for "left" and "right", as well. The tiling is therefore a super-tiling of

A	B	C
D	E	F
G	H	I

We want to distribute these 9 positions among 6 rectangles, so at least 3 of the 6 rectangles must span exactly 1 position. So, we can assume, without loss of generality, that either "B" is such a rectangle or "A" and "C" are both such rectangles. (It cannot be that "A"+"E"+"I" or "C"+"E"+"G" are the 3 rectangles spanning 1 position, because this divides the remaining area into two non-rectangular areas, meaning that the total number of rectangles needed is at least 3+2+2=7>6.)

If "B" is such a rectangle, and it does not form a separable tiling with "A" or with "C", then this is because the rectangle spanning "A" also spans "D" and the rectangle spanning "C" also spans "F". This indicates that "B" forms a separable tiling with the rectangle spanning "E".

If, on the other hand, both "A" and "C" are rectangles in the tiling, then "B" and "E" must be spanned by the same rectangle, so "A" and the rectangle spanning "D" form a separable tiling.

Q.E.D.

Part 1:

First, let us prove that no tilings exist for N<7.

The tiling with minimal N must be a non-decomposable tiling. If it had been a decomposable tiling, the M rectangles that form a separate tiling are already a solution. However, the non-decomposable solutions for N=2 and N=5 shown above are unique up to rotation and mirror reflection, and solving their parameters shows that neither has all-distinct rectangle perimeters.

For completion: here is a way to show that the solution for N=5 is unique up to reflection. Consider, again, that E=2, and therefore the tiling is a super-tiling of the 3x3 tiling shown in the diagram above.

Each rectangle must choose its top and its bottom from a set of size 4, for a total of 6 possibilities, minus 1 possibility because the global top and global bottom do not form a usable pair in a non-decomposable tiling. We therefore have exactly 1 representative of each possible choice.

Because each of the four corners must be covered by a different rectangle, this leaves the rectangle with its top and bottom both in internal edges as the fifth. For the same reason, it is also the rectangle with the internal left and right edges. So, "E" must be its own rectangle. However, now "B", "D", "F" and "H" cannot be their own rectangles. The rectangle covering each must also cover a corner. This leaves exactly the two choices equivalent to the non-decomposable tiling drawn for N=5 above.

Q.E.D.

A tiling with N=7 can be produced as is shown above. When tiling the unit square, the dimensions of the rectangles are as follows.

Rectangle number	Width	Height
1	(√19+1)/15	(5√19-5)/42
2	(√19-1)/15	(5√19+5)/42
3	3/5	5/21
4	(8-√19)/15	(√19+8)/21
5	(√19+7)/15	(7-√19)/14
6	(7-√19)/15	(√19+7)/14
7	(√19+8)/15	(8-√19)/21

I am leaving it as an exercise for the reader to verify the correctness of this tiling.

For N=8, extend the 7-tiling by adding a new rectangle of the same area that spans the entire top part of the rectangle.

For N=9, extend the 8-tiling by adding a new rectangle of the same area that spans the entire left part of the rectangle.

By repeating this procedure of adding to the top and adding to the left, one can extend this tiling to arbitrarily many rectangles.

In each such extension, the new rectangle is taller/wider than any previous rectangle, so its dimensions are not identical to any previous rectangle. The only possibility that two rectangles are of the same perimeter is therefore if the height of one equals the width of another. However, because one can scale the original rectangle to be tiled at will, this can always be avoided.

Two remarks:

1. In this construction for each N we tile a rectangle of different dimensions. However, the question does not become more difficult if we require that for all N the same rectangle be used. We do this by scaling down the solution. All we need is to avoid that the height of one internal rectangle be the same as the width of another. Because all heights and widths in the original construction are of sizes that are within the extension field of the rationals by √19, all we need is for the height-to-width ratio of the rectangle-to-be-tiled not to be in this field. For example, a 1-by-√2 rectangle will do.
2. An even stricter constraint is to require all tilings to be done on the unit square. In this case, in the presented construction there are many rectangles whose height will have a rational ratio to the width of other rectangles. In order to see that even in this case all perimeters are different, one must simply consider, in this rational ratio, when one writes it out in fully reduced form, whether the numerator or the denominator are even. In our construction, it is always known regarding one of them that it is even and regarding the other that it is odd. Therefore, the ratio can never be 1, and the construction remains valid even when tiling the square.

Credits for this month's riddle and its original solution are as follows.

On the 26th of March, over 3 weeks after this riddle was published, R. Nandakumar, who sent me the original e-mail query regarding this problem, discovered that the problem had already been studied in the past. Here's a link. The rest of the credits are for recent work, done independently from Descartes's. (This last link is a highly recommended one.)

R. Nandakumar's original question to me was whether there exists a tiling into rectangles of equal area but different perimeters. (To the best of his knowledge at the time, this question's first public appearance was in his blog.) This question was solved initially by myself. (And here I should add that I am indebted to the Discrete Math Research Group at Monash University for pointing me in the right direction for this solution, and especially to János Barát. I announced my solution, an explicit construction for N=7, shortly after consulting with the group.) Within twenty-four hours, János Barát also reached the same construction, followed by N. Ramana Rao.

Questions regarding the minimality of the N=7 construction, as well as its extendability to arbitrary N (and its relation to non-decomposable tilings) are my own results, as are results regarding tiling squares.

Here's a question posed by R. Nandakumar (also on the same blog post), which I do not know the answer to:
Can a rectangle be tiled by different-perimeter same-area rectangles, when all rectangle sides must be rationals?

To this I add "Will this ever happen if we simply continue the spiral structure indefinitely?"

If any reader wants to continue exploring these questions, I'll be very happy to hear of progress.

Back to riddle

Back to main page