Problem of the Month (November 2003)

This month we are interested in three problems involving packing or tiling squares.

1. A Hanoi Square Tiling is a tiling of a large square by smaller integer sided squares so that each square either lies on the bottom layer or lies on top of one or more larger squares. Some examples of Hanoi Square Tilings are shown below:

What is the smallest odd square that has a Hanoi Square Tiling? What is the smallest square that has such a tiling with 3 squares on the bottom layer? Can you show that arbitrarily large squares all have Hanoi Square Tilings? Which is the largest square that does not have such a tiling?

What about the same problem for cubes? Can you find a Hanoi Cube Tiling for a cube of side 44? How about a cube of side 2003? Which cubes have these tilings? Do arbitrarily large cubes have Hanoi Cube Tilings?

2. A bumpy square is the union of a square of side 2 or more and a unit square along one edge of the unit square. A Bumpy Square Tiling is a tiling of a rectangle with different sized bumpy squares. Some examples of Bumpy Square Tilings are shown below:

What Bumpy Square Tilings exist? Are there infinitely many of them? Can bumpy squares tile a square, or a bumpy square? Are there any Bumpy Square Tilings possible in 3 dimensions?

3. A Neighborly Square Packing is a packing of a square by smaller integer squares so that only squares whose sides differ by 1 touch along sides, and no squares touch only at corners. These are plenty of such packings, but the challenge is to find the packing using the largest area for a given square. For example, here is a packing of a square of side 10 with area 82:

What do the small optimal Neighborly Square Packings look like? If W(n) is the smallest wasted area for a square of side n, does W(n) approach ∞? Does W(n)/n approach 0?


ANSWERS

1. Hanoi Square Tilings

Bill Clagett wrote a computer program which showed that the smallest odd number with a Hanoi Square Tiling is 21. He also showed the smallest number with a tiling having 3 squares on the bottom row is 24. Robert Wainwright and Jon Wharf found these as well.

Philippe Fondanaiche sent several Hanoi Square Tilings, but missed a few. He, Jeremy Galvagni, and Sasha Ravsky noted that if n is a sum of some its proper divisors, then n has such a tiling. Sasha Ravsky noted that if a and b are numbers such each of them is a sum of different proper divisors of the other, then the square of side a+b has such a tiling.

Dean Hickerson succeeded in proving that all sufficiently large squares have Hanoi Square Tilings. His current lower bound is that this is true for all n≥221. I proved that all even n>8 have such tilings by doing n<36 by hand and finding a general pattern for n≥36. In both proofs, the key Lemma is that all rectangles (except 2 by odd) that are at least 5 wider than they are tall can be so tiled. Jon Wharf also sent me a proof that large squares could be so tiled, but his bound was enormous.

So it appears the only squares which do NOT have these tilings are: 1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 15, 17, 19, 23, and 33.

Small Hanoi Square Tilings

Philippe Fondanaiche and Jon Wharf found a Hanoi Cube Tiling for the n=44 cube. Sasha Ravsky noted that if a number has a Hanoi Cube Tiling, then it has a Hanoi Square Tiling as well.

The cubes that I found that have Hanoi Cube Tilings are multiples of 6, 20, 28, 44, 52, 68, 76, 92, 116, 124, 148,.... Here is the beginning of the Hanoi Cube Tilings of the cubes of side 44 and 52. On the left, the red cubes have side 22, orange 11, green 10, yellow 8, and blue 6. On the right, the red cubes have side 26, orange 13, blue 12, green 10, and yellow 8.

2. Bumpy Square Tilings

Patrick Hamlyn wrote a program to find Bumpy Square Tilings, and all but 3 of the tilings below. I found the 38x43 and the 41x46 tilings, as did Joseph DeVincentis. The 25x45 tiling was found by Berend Jan van der Zwaag. Patrick Hamlyn also searched for Bumpy Square Tilings of Bumpy Squares, up to 26x26, without finding any.

Small Bumpy Square Tilings
Patrick Hamlyn also found many Bumpy Square Tilings on projective planes:

3. Neighborly Square Packings

Berend Jan van der Zwaag assumed that squares could be located anywhere. His best solutions are:

Small Neighborly Square Packings

For odd n, Berend Jan van der Zwaag can prove W(n)/n<1.

Joseph DeVincentis thought that the corners of the squares must be located on the integer lattice. His best solutions are shown below. I found the packing of the 11x11 square.

Small Lattice Neighborly Square Packings
Joseph DeVincentis can prove W(n)/n<2 for these tilings.

This got me thinking about Neighborly Square Tilings, tilings of a square by smaller squares so that no squares whose sides differ by more than 1 meet edge to edge, and the squares are coprime. Here are the tilings Jeremy Galvagni and I have found with the smallest number of squares.

Small Neighborly Square Tilings

Robert Wainwright notes that there exists a Neighborly Square Tiling of 4 squares of side 1, 8 squares of side 2, ... 4n squares of side n inside a square of side n(n+1).

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 6/19/05.