Problem of the Month (December 1998)

A square can be cut into smaller squares in many ways. This month, we consider integer square tilings, a tiling of a square into smaller squares with integer sides. For every n>1, consider all integer square tilings of an n x n square, and define:

f(n) = the largest possible size of the smallest square

g(n) = the smallest number of squares

h(n) = the smallest value of the largest multiplicity of any square needed

What are the best results you can find for various n? Can you prove your results? Some particular questions:


ANSWERS

Joseph DeVincentis gave several interesting results. First he proves that when n≥8, f(n)>1. His proof: You can group 2×2's and 3×3's into 2×6 and 3×6 rectangles, which can then form long 6×m rectangles for any sizes besides 6×1, so for any squares of sizes larger than 7×7, you can split them into 4 blocks: a 6×6 square, an (n-6)×(n-6) square, and two 6×(n-6) rectangles, which are filled with lots of rows of three 2×2's and one row of two 3×3's when n is odd. He generalizes the proof to prove that if n≥2k2, then f(n)≥k.

He mentions this is similar to a problem which he discussed on the rec.puzzles newsgroup in March 1998. He proved that any square besides a 2×2, 3×3, 5×5, 7×7, and 13×13 can be cut into squares with sides 2, 3, and 5. Later on, this discussion turned to tiling squares with smaller squares of sides which were not factors of the larger square. They eventually agreed the largest square which could not be tiled in this way has side 60.

Another of his observations is that many of the best fewest square tilings of prime sided squares use exactly 5 odd-sided squares. He proves that 5 is the minimum possible: Each row and column must contain an odd number of odd-sided squares, and 1 isn't enough. Since the area of odd-sided squares is 1 mod 4 and the area of even squares is 0 mod 4, we need a number of odd-sided squares that is 1 mod 4. Since 1 is not sufficient, at least 5 are required.

Brendan Owen proved that f(n)>1 eventually. He also wrote a computer program to find the values of f(n) for n≤82. He found many tilings which beat the previous bounds.

Olexandr Ravsky found all the data in the table below.

John Hoffman wrote a computer program to find f(n) for n≤102. He also showed that f(n) can be larger than n/p, where p is the smallest prime factor of n. In fact, since f(11)=2, f(121)≥22. He conjectured that for composite n, f(n) = maxk {n/k f(k) : k | n, k<n }. This is true for all but two values of n≤120. It fails for f(49)=9>7f(7) (shown here) and f(119)=18>17 f(7) (shown here).

Hoffman also notes that f(p) is not increasing, since f(37) = 7 and f(41) = 6.

Here are the values of f(p) for prime p:

Largest Possible Minimum Square

p 23571113 171923293137 414347535961 677173798389 97
f(p) 1 1 1 1 2 2 2 3 4 5 5 7 6 7 7 8 9 10 10 11 11 13 12 14 14

p 101103107109113 127131137139149 151157163167173179181191193197199
f(p) 16 15 16 16 19 19 21 20 21 23 23 24 25 23 27 25 27 26 29 31 31

The sequence of values of f(n): 1, 1, 2, 1, 3, 1, 4, 3, 5, 2, 6, 2, 7, 5, 8, 2, 9, 3, 10, 7, 11, 4, 12, 5, 13, 9, 14, 5, 15, 5, 16, 11, 17, 7, 18, 7, 19, 13, 20, 6, 21, 7, 22, 15, 23, 7, 24, 9, 25, 17, 26, 8, 27, 11, 28, 19, 29, 9, 30, 10, 31, 21, 32, 13, 33, 10, 34, 23, 35, 11, 36, 11, 37, 25, 38, 14, 39, 13, 40, 27, 41, 12, 42, 17, 43, 29, 44, 14, 45, 14, 46, 31, 47, 19, 48, 14, 49, 33, 50, 16, 51, . . . is now sequence A036445 of the Encyclopedia of Integer Sequences.


Joseph DeVincentis found the best-known bounds for g(p) for p prime≤47.

Brendan Owen confirmed these with a computer program for n≤36.

John Hoffman found g(n) for n≤28.

Olexandr Ravsky found g(43)=16 in 100 minutes on his Pentium 466.

There is some evidence that if p is the smallest prime dividing n, then g(p)=g(n). There are no known counterexamples. Hoffman showed that g(2n) = 4, and g(6n+3) = 6. The proofs are based on the observation that 4 different squares must cover the corners of the larger square. This means the conjecture is true for p=2 and p=3. I managed to generalize his result to cover p=5 as well.

Here are the values of g(p) for prime p:

Fewest Number of Squares

p 23571113 171923293137 414347535961 677173798389 97
g(p) 4 6 8 9 11 11 12 13 13 14 15 15 15 16 16 16 17 17 17 18 18 18 18 18 19

p 101103107109113 127131137139149 151157163167173179181
g(p) 19 19 19 19 19 20 20 20 20 20 20 20 21 21 21 21 21

The sequence of values of g(n): 4, 6, 4, 8, 4, 9, 4, 6, 4, 11, 4, 11, 4, 6, 4, 12, 4, 13, 4, 6, 4, 13, 4, 8, 4, 6, 4, 14, 4, 15, 4, 6, 4, 8, 4, . . . is sequence A018835 of the Encyclopedia of Integer Sequences.

There is a closely related problem that has been well-researched. Define G(n) to be the smallest number of co-prime squares (squares whose sides have no common divisor except for 1) that can tile a square of side n. Then G(n)≥g(n) and G(p)=g(p) for prime p. In 1964, John H. Conway proved that G(n) ≥ log2 n, and in 1965, G. B. Trustum showed that G(n) ≤ 6 log2 n. Several solvers guessed that this was the correct order of magnitude. The sequence of values of G(n): 1, 4, 6, 7, 8, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, . . . is sequence A005670 of the Encyclopedia of Integer Sequences.

Most of the tilings of Joseph DeVincentis, are symmetrical, which led him to investigate gi(n), the smallest number of squares needed to tile an n × n square with a i × i square missing from a corner. Below are his best known bounds on gi(n).

Olexandr Ravsky corrected one error below and found g1(20)=13.

Fewest Number of Squares Needed for
an n × n Square Minus an i × i Square

i \ n 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 356788 9910101011 111112121212 1213131313
2 -53758 69710811 811912912 101310    
3 --7738 951010610 11712                
4 ---958 39710511 811612912 71310138

Olexandr Ravsky defined G1(n) to be the fewest number of squares needed to tile an n × n square if one if the squares is 1 × 1. His data is shown below. He conjectures that g(p)=G1(p) for primes p.

Fewest Number of Squares Including a 1×1 Square

p 123456-7 8-910-1314-1718-2324-29 30-39404142-43
g(p) 146789 1011121314 15161516


Joseph DeVincentis showed that h(n)≤3 for 11≤n≤52, and for many more larger n.

Brendan Owen used these bounds in his computer program to find h(n) for n≤50. In particular, he found that the smallest n for which h(n)=2 is n=19.

Ed Pegg and John Hoffman mention that if h(n)=m, h(kn)≤m, so there are infinitely many n with h(n)=1.

Ed asks whether similar triangles can be packed with different sized congruent copies of themselves. The answer for equilateral triangles is no. To see this, consider a triangle in a corner. There must be a smaller triangle which shares a face. This new triangle must have a yet smaller triangle which shares a face, and so on. Since this progression cannot last forever, no such tiling can exist.

But such unique tilings of right triangles and isosceles triangles exist. The tiling of an isosceles right triangle is here. For a non-isosceles right triangle, an altitude to the hypotenuse divides the triangle into two similar triangles. The tiling of a non-right isosceles triangle is here.

Hoffman managed to show that h(n)≥2 for n≤40. He did n≤20 by hand!

Hoffman also asked for which values of n can n squares tile a square? The answer is all n except n=2, 3, and 5. For n≥2, 2n squares can tile a square of side n (1 square of side n-1 and 2n-1 squares of side 1). For n≥3, 2n+1 squares can tile a square of side 2n-2 (4 squares of side n-2 and n-3 squares of side 2).

Here are the values of h(n):

Smallest Possible Maximum Multiplicty

n 234567 8910111213 141516171819 2021222324 2526
h(n) 4 5 4 4 4 3 4 3 4 3 3 3 3 3 3 3 3 2 2 3 2 2 2 2 2

n 272829 3031323334 3536373839 4041424344 4546474849
h(n) 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

By modifying the tilings of Owen, I can show that h(n)≤2 for 22≤n≤102. The key observation is that if there is a h(n)=2 tiling with a k×k square in the corner, removing that square and adding 3 others gives a tiling which shows h(2n-k)≤2. In 1993, Skinner proved that the smallest n for which h(n)=1 are 110, 112, 120, 139, 140, . . . . The sequence of values of h(n): 4, 5, 4, 4, 4, 3, 4, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, . . . is now sequence A036444 of the Encyclopedia of Integer Sequences.


The question of tiling rectangles with integer-sided squares is also interesting. For most small rectangles, f(m,n)=gcd(m,n), the greatest common divisor of m and n. The smallest counterexample is f(5,6)=2. For most small rectangles, g(m,n) can be found by the greedy strategy of always using the biggest square possible at every stage. Again, the smallest counterexample is g(5,6)=5.

In October 2007, Stewart Hinsley sent me the following page of his predictions for values of g(m,n). The values with a red background are the values where the greedy algorithm would correctly predict g(m,n). These guesses assume g(km, kn) = g(m, n), for which there is experimental evidence, and some other things, for which there is less evidence.


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