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?


ANSWERS

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

1

1 square
2

4 squares
3

6 squares
4

7 squares
5

8 squares
6

11 squares
7

9 squares
8

15 squares
9

13 squares
10

15 squares
11

15 squares
12

15 squares
(Berend van der Zwaag)
13

20 squares
(Maurizio Morandi)
14

20 squares
(Maurizio Morandi)
15

17 squares
(Jeremy Galvagni)
16

22 squares
17

23 squares
18

22 squares
(Berend van der Zwaag)
19

27 squares
(Berend van der Zwaag)
20

24 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
n1234567891011
Triangles146711141612191826


2. Here are the best known small square bridges:

1

area 1
2

area 4
3

area 9
4

area 12
5

area 18
6

area 22
7

area 30
8

area 35
(Corey Plover)
9

area 43
10

area 48
11

area 57
12

area 64
13

area 73
14

area 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:

1

side 1
2

side 2
3

side 3
4

side 4
5

side 6
(Maurizio Morandi)
6

side 8
7

side 11
8

side 13
9

side 16
10

side 18
11

side 21

12

side 23
13

side 26
(Maurizio Morandi)
14

side 30
(Maurizio Morandi)

15

side 34
(Vedran Glisic)
16

side 37
(Vedran Glisic)
17

side 41
(Maurizio Morandi)

18

side 44
(Maurizio Morandi)
19

side 48
(Maurizio Morandi)
20

side 52
(Maurizio Morandi)

21

side 55
(Maurizio Morandi)
22

side 59
(Maurizio Morandi)


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

2

2 wasted
3

3 wasted
4

5 wasted
5

5 wasted
6

8 wasted
7

5 wasted
8

9 wasted
9

8 wasted
10

8 wasted
11

11 wasted
12

13 wasted
13

12 wasted
14

13 wasted (VG)
15

16 wasted (VG)
16

14 wasted
17

17 wasted (MM)
18

21 wasted (MM)
19

19 wasted (MM)
20

17 wasted (MM)

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

100

124 wasted

In 2011, Vedran Glisic 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.