# Problem of the Month (September 2005)

This month we consider 4 problems concerning squares.

1. Square Chain Tilings

We say a tiling of a square by integer-sided squares is a square chain tiling if every square of side s>1 shares part of a side with a square of s-1. For each n, we are interested in finding the square chain tiling of a square of side n using the fewest number of squares.

What are the minimal square chain tilings for various squares? In particular, what is the fewest number of squares you can find for a chain tiling of a square of side 100?

What are the best chain tilings of rectangles by squares? How about equilateral triangle chain tilings?

2. Square Bridges

A square bridge is a collection of integer-sided squares on a grid so that a) every square but one rests partly on another square, and b) the tops of the squares which do not have a square resting on them are level. The width of a square bridge is the length of the top edge. For each n, we are interested in finding the square bridge of width n whose combined area is as small as possible.

What are the minimal square bridges for various n? Do squares of side 5 or greater ever appear in the optimal bridges? What is the smallest possible area of a square bridge of width 100?

3. Covering Squares Without Overlap

The September 2000 problem investigated covering the largest square using squares of sides 1 through n. This month we are interested in the largest square that can be covered by non-overlapping squares of sides 1 through n.

What are the best coverings for various n? In particular, what is the smallest n for which non-overlapping squares of sides 1 through n can cover a square of side 100? What is the largest area rectangle that non-overlapping squares of sides 1 through n can cover?

4. Sorted Square Packings

A sorted square packing is a packing of a square with integer-sided squares so that all squares above and to the right of a square are strictly smaller. For each n, we are interested in the sorted square packing of a square of side n with the smallest wasted area.

What are the best packings for various squares? In particular, what is the best sorted square packing of a square of side 100?

1. Here are the best known small square chain tilings:

 11 square 24 squares 36 squares 47 squares 58 squares 611 squares 79 squares 815 squares
 913 squares 1015 squares 1115 squares 1215 squares(Berend van der Zwaag) 1320 squares(Maurizio Morandi)
 1418 squares(George Sicherman) 1517 squares(Jeremy Galvagni) 1621 squares(George Sicherman) 1723 squares
 1822 squares(Berend van der Zwaag) 1927 squares(Berend van der Zwaag) 2024 squares(Jeremy Galvagni)

Jeremy Galvagni developed the idea of an efficiency ratio r(n) for a chain tiling of a square of side n: the area divided by the number of squares. He notes that r(kn) is an increasing function of k, since we can just tile a square of side kn with chain tilings of a square of side n. Presumably r(n) diverges to ∞, but how quickly?

Jeremy Galvagni also found a chain tiling of a square of side 100 containing 230 squares. Then Emilio Schiavi found a tiling using only 186 squares. Then in 2009, Berend van der Zwaag found a tiling using only 128 squares:

100

128 squares (Berend van der Zwaag)

Finally, in 2011, Maurizio Morandi improved 2 parts of the tiling to reduce the number of squares:

100

125 squares (Maurizio Morandi)

Jeremy Galvagni also investigated triangle chain tilings. Here are his best results:

Minimum Number of Triangles in
Chain Tiling of Triangle of Side n
 n Triangles 1 2 3 4 5 6 7 8 9 10 11 1 4 6 7 11 14 16 12 19 18 26

2. Here are the best known small square bridges:

 1area 1 2area 4 3area 9 4area 12 5area 18 6area 22 7area 30 8area 35(Corey Plover) 9area 43
 10area 48 11area 57 12area 64 13area 73 14area 80(Corey Plover)

Corey Plover found this square bridge of width 100:

100

area 1106 (Corey Plover)

Corey Plover also sent me solutions for all n≤100 based on recursion. And he sent me an analysis of this problem when the squares do not have to lie on a grid. He used only unit squares to show that in this case, the area needed is no more than n+1+k2k where k=log2n-1.

3. Here are the best known small non-overlapping square coverings:

 1side 1 2side 2 3side 3 4side 4 5side 6(Maurizio Morandi) 6side 8.4744(Maurizio Morandi) 7side 11
 8side 13 9side 16 10side 18 11side 21

 12side 23 13side 26.5583(Maurizio Morandi) 14side 333/√122 = 30.1484(Maurizio Morandi)

 15side 34(Vedran Glišić) 16side 37.1557(Maurizio Morandi) 17side 41(Maurizio Morandi)

 18side 44(Maurizio Morandi) 19side 48(Maurizio Morandi) 20side 52(Maurizio Morandi)

 21side 55(Maurizio Morandi) 22side 59(Maurizio Morandi)

4. Here are the best known small sorted square packings:

 22 wasted 33 wasted 45 wasted 55 wasted 68 wasted 75 wasted 89 wasted 98 wasted
 108 wasted 1111 wasted 1213 wasted 1312 wasted 1413 wasted (VG)
 1516 wasted (VG) 1614 wasted 1717 wasted (MM)
 1821 wasted (MM) 1919 wasted (MM) 2017 wasted (MM)

Corey Plover sent the following sorted square packing of a square of side 100.

100

124 wasted

In 2011, Vedran Glišić improved the packing:

Then a few weeks later, Maurizio Morandi did even better:

100

92 wasted

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