# 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?

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:

 1x2 4x4 4x8

 1x4 2x2 2x6 2x10... 4x6 4x8 4x16 7x12
 8x8 18x54

 1x6 2x3 4x12 4x24 6x13... (CW)
 8x12 18x42

 2x3 6x8 6x17

 1x8 2x4 4x16 4x32 8x16
 12x30 12x54...

 8x8

 2x4 8x8 8x8 8x16 12x22... (CW)
 12x28... (CW) 16x24

 1x10 2x5 4x20
 4x40 8x20

 2x5 8x10

 2x5 8x10

 2x6 3x4 8x12 8x24 12x13 12x16 12x17 12x25 12x26
 12x33 12x34 12x35... 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)

 1x12 2x6 4x24
 4x48 8x24

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

 1x1 √8x√8 4x4 8x8

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:

 0 0 0 4 1 4 4 4 5 6 6 8
 8 9 12 16 12
 20 16 21 24
 21 22 32
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:

 0 1/2 1/4 1/5 1/6 2/3 5/12 1/2 2/3
 7/12 1/2 5/6 17/24(Bryce Herdt)
 2/3 5/6 3/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.