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 1×2 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 4×4 rectangle. If not, a square between two of them must be bigger, so opposite corner squares must touch, and we get the 4×8 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:

1×24×44×8

1×42×22×62×10...4×64×84×167×12
8×818×54

1×62×34×124×246×13... (CW)
8×1218×42

2×36×86×17

1×82×44×164×328×16
12×3012×54...

8×8

2×48×88×88×1612×22... (CW)
12×28... (CW)16×24

1×102×54×20
4×408×20

2×58×10

2×58×10

2×63×48×128×2412×1312×1612×1712×2512×26
12×3312×3412×35...36×48

2×6 (CW)8×12 (CW)

2×6 (CW)3×4 (CW)6×16 (CW)8×12 (CW)

3×4 (CW)6×16 (CW)

3×4 (CW)8×12 (CW)

3×4 (CW)8×12 (CW)

1×122×64×24
4×488×24

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

1×1√8x√84×48×8

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 n×n square grows no faster than (n/4 – 2)2, since the most efficient way to tile the interior of the square is by 4×4 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 n×n 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 n×n 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.

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