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.
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.
| m \ n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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 |
| n | k(1,n) |
|---|---|
| 18 | 2 |
| 19 | 2 |
| 20 | 2 |
| 21 | 2-5 |
| 22 | ?-? |
| 23 | ?-? |
| 24 | 2 |
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):
| m \ n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 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):
| m \ n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 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 |
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.
