Problem of the Month (December 2004)

There are lots of ways to tile a rectangle with squares. But there are only 3 ways to do it so that the number of neighbors of each square is equal to its side length. Can you prove that these are the only ways?

This month we generalize this problem to polyominoes. Given a polyomino P, what rectangles can be tiled with various sized copies of P so that the scaling factor of each polyomino is equal to the number of (horizontally and vertically) adjacent copies of P?


ANSWERS

Joe DeVincentis and Emilio Schiavi proved that there are only 3 neighborly tilings of squares. Here's Emilio's proof:

In such a rectangle, the smallest tiling square must have size 1 or 2, since if a corner square has more than 2 neighbors, at least one of its neighbors must be smaller than size 3. If the smallest square has side 1, this is only possible in a corner, and leads to the 1x2 rectangle. If the smallest square has side 2, again these squares must be in the corners. If these are the only squares we get the 4x4 rectangle. If not, a square between two of them must be bigger, so opposite corner squares must touch, and we get the 4x8 rectangle.

Clint Weaver found many new solutions.

Joe DeVincentis analyzed lots of cases of wrapping large rectangles with small ones, but didn't find any new tilings.

Here are the known neighborly tilings of various polyominoes:

1x24x44x8

1x42x22x62x10...4x64x84x167x12
8x818x54

1x62x34x124x246x13... (CW)
8x1218x42

2x36x86x17

1x82x44x164x328x16
12x3012x54...

8x8

2x48x88x88x1612x22... (CW)
12x28... (CW)16x24

1x102x54x20
4x408x20

2x58x10

2x58x10

2x63x48x128x2412x1312x1612x1712x2512x26
12x3312x3412x35...36x48

2x6 (CW)8x12 (CW)

2x6 (CW)3x4 (CW)6x16 (CW)8x12 (CW)

3x4 (CW)6x16 (CW)

3x4 (CW)8x12 (CW)

3x4 (CW)8x12 (CW)

1x122x64x24
4x488x24

Okay, this isn't a polyomino, but I couldn't resist trying isosceles right triangles:

1x1√8x√84x48x8

Jeremy Galvagni sent me several tilings of squares with lots of neighborly squares.

Emilio Schiavi, Claudio Baiocchi and I were convinced that the number of neighborly squares in a tiling of an nxn square grows no faster than (n/4 - 2)2, since the most efficient way to tile the interior of the square is by 4x4 neighborly squares. Claudio Baiocchi pointed out that there are counterexamples for small n.

Sasha Ravsky managed to prove a slightly weaker bound: Let n ≥ 4. Fix a tiling of an nxn square. Let S2 be the set of neighborly squares placed in the corners, let S3 be the set of neighborly squares placed along the sides, and let S4 be the set of all other neighborly squares. Each square from the set Si has a side at least i. So, we have: 4|S2|+9|S3|+16|S4| ≤ n2 (condition on the area), 4|S2|+ 3|S3| ≤ 4n (condition on the perimeter), and |S2| ≤ 4. (the square has four corners). Combining these gives |S2|+|S3|+|S4| ≤ (3n2+28n+32)/48.

Here are the most neighborly tilings of squares by squares:

000414445668
89121612
20162124
212232
Claudio Baiocchi remarked that cylinders, tori, Möbius strips, and Klein bottles have nice neighborly tilings without edge problems. He also gave some lower bounds for the number of neighborly squares that would fit in a square. If we let N(n) be the maximum number of neighborly squares that will fit inside an nxn square, he showed N(n) ≥ (n/4)2 - 2n/3 + 4 for n=12m, N(n) ≥ (n/4)2 - 5n/6 + 13/3 for n=12m+4, N(n) ≥ (n/4)2 - 2n/3 + 16/3 for n=12m+8, and N(n) ≥ (n/4)2 - 7n/12 + 41/4 for n=12m+18. The tilings can be seen below.

For rectangles that are long and skinny, the most neighborly tilings by squares repeat pieces that are neighborly as possible. Here are the most neighborly strips of a given width:

01/21/41/51/62/35/121/22/3
7/121/25/617/24
(Bryce Herdt)
2/35/63/4
(Bryce Herdt)
5/6
(Bryce Herdt)
1

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