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 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 20 squares (Jeremy Galvagni)

13 21 squares

14 22 squares

15 17 squares (Jeremy Galvagni)

16 22 squares

17 23 squares

18 29 squares (Jeremy Galvagni)

19 30 squares (Jeremy Galvagni)

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. But Emilio Schiavi found this tiling using only 186 squares:

100

186 squares (Emilio Schiavi)

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

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+k2^k where k=log₂n-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 5

6 side 8

7 side 11

8 side 13

9 side 16

10 side 18

11 side 21

12 side 23

13 side 25

14 side 29

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 17 wasted

15 19 wasted

16 14 wasted

17 21 wasted

18 22 wasted

Corey Plover sent the following sorted square packing of a square of side 100. His method is to recursively include the solution for (n-1)/3.

100

124 wasted

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