Problem of the Month (May 2005)

We call a tiling of a rectangle with integer-sided squares balanced consecutive (BC) if it contains squares of consecutive sizes, and contains the same number of squares of each size. This month we investigate BC tilings. In particular, for m ≤ n we are interested in the question ``What is the smallest number k(m,n) so that k copies each of squares of side m through n can be tiled in a rectangle?''

The problem with m=1 has been studied previously. It is known that k(1,1)=1, k(1,2)=2, k(1,n)=4 for 3≤n≤9, k(1,n)=3 for 10≤n≤13, and k(1,n)=2 for n=15 and 16. Many of these tilings were found by Patrick Hamlyn a few years ago. It is thought that k(1,14)=4, but it might be 3, or even 2. Can you improve on the tiling below?

Since prize money worked well last month, I'll offer another prize this month. At the end of the month, if you were the first one to find the best upper bound for k(m,n) (for m≤5 and n≤16), you get 1/k(m,n) points. If you can show that a lower bound is equal to the upper bound, thereby proving a value of k(m,n), you also get 1/k(m,n) points. The most points wins the $10 prize.


ANSWERS

Patrick Hamlyn showed that k(1,14)=3:

Patrick Hamlyn also showed k(2,9) ≥ 6, and many upper bounds below.

Joseph DeVincentis proved that usually k(n,n+1)=n(n+1), except for when n2+(n+1)2 can be factored into the product of two numbers, each larger than n. Aside from n=3, the next smallest exceptional case is k(10,11)=100.

Joseph DeVincentis also showed k(4,9) ≥ 22.

Bertram Felgenhauer showed most of the non-trivial lower bounds, in addition to many upper bounds below.

Gunter Stertenbrink sent me links to two recent papers about rectangle packing: here and here.

Known Bounds for k(m,n)
m \ n1234567891011121314151617
1 1 2 4 4 4 4 4 4 4 3 3 3 3 3 2 2 2
2 1 6 12 6 5 12 4 6 3 4 3 11 3 3 3 4
3 1 9 9 10 4 15 5 4 7 4 4 4 3 3 3
4 1 20 8 8 8 22 4 4 4 4 4 12-14 4 3
5 1 30 24 16 10 9 6 6 9-11 7 4 13-21 4
6 1 42 38-56 12 8 8 6 9 6 5-6 5 5
7 1 56 40-66 20 14 12 8 7 11-12 8-11 5
8 1 72 36-40 24 12 12-16 8 7 7-8 6
9 1 90 50-82 32-44 18-20 33-48 8 8 7-8
10 1 100 40-72 31-40 16 13 12-13 7
Patrick Hamlyn
Bertram Felgenhauer
Jean-Charles Meyrignac and Gunter Stertenbrink

Values of k(1,n)
nk(1,n)
182
192
202
21?-?
22?-?
23?-?
242

Patrick Hamlyn showed that k(1,n)=2 for small n if we are tiling on a Möbius Strip or Projective Plane:

For the second straight month, Bertram Felgenhauer wins the $10 prize, though Jean-Charles Meyrignac and Gunter Stertenbrink deserve honorable mention.

What are the answers c(m,n) if we consider cubes instead of squares?

Michael Beeler showed that c(1,3)=8, and c(1,4)>10.

Here are the best known upper bounds on c(m,n):

Best Known Bounds for c(m,n)
m \ n12345
1 1 4 8 10-24 2-32
2 1 36 2-16
3 1 144
4 1 256

What are the answers t(m,n) if we consider triangles, and require them to tile a convex region? Claudio Baiocchi noted that t(m,n) ≤ 2k(m,n), since we can shear a square into a diamond tiled by two equilateral triangles. Here are the best known bounds on t(m,n):

Best Known Bounds for t(m,n)
m \ n12345678
1 1 3 2-3 1-3 1-5 1-3 1-8 1-3
2 1 5 2-3 1-7 1-4 1-3 1-8
3 1 7 2-9 1-8 1-8 1-30
4 1 9 2-6 1-16 1-3
5 1 11 2-14 1-32
6 1 13 2-7
7 1 15
8 1
Claudio Baiocchi
Andrea Concaro


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