Pentomino Layer Cake

February 27th, 2010 by munizao

On the Polyforms list, Erich Friedman posed a very interesting new pentomino tiling problem:

Tile a rectangle of minimal area with pentominoes so that for each pentomino there is exactly one stratum, or cluster of one or more copies of that pentomino that reaches from one side of the rectangle to the opposite side. Pentominoes in a stratum must form a single group, connected by edges, not just corners.

Michael Reid found this 3×30 solution: It’s not hard to prove that it is minimal. A natural extension of the problem is to find minimal solutions for 4×n and 5×n rectangles. Michael Reid found the first 5×n solution, but I improved on it with this 5×32 solution: The 4×n problem seems to be the hardest, and initially it was not clear that it would be possible. The X pentomino has only one possible stratum, which only can only be bordered by Y, I or N, and it is also difficult to find matches for a Z stratum. Additionally, only Y, L, and P can form straight line stratum boundaries usable for the top and bottom of the rectangle. (See wikipedia’s pentomino page if you don’t know the correspondence between letters and shapes.) I did eventually find this 4×50 solution: This solution seems rather prolifigate with its pentominoes, but finding any solution at all was a bit of a surprise.

Update: Erich Friedman’s Math Magic for April 2010 further explored this subject. 1. Jason Dyer says:

It’s not hard to prove that it is minimal

So (I have never done a pentomino proof on anything ever), how?

2. munizao says:

First, categorize the pentominoes by their bounding boxes: one (I) is 1×5, three (L, N, Y) are 2×4, and the rest are 3×3. In a 3×n rectangle, there must be three copies of I, two each of the 2×4 pentominoes, and one each of the rest. This gives an area of 17×5. But we need the area to be a multiple of 3 because it’s a 3×n rectangle, so we need one more pentomino, (the extra P in the 3×30 figure.) Thus, 18×5=3×30=90 is minimal for the 3×n case.

Now we should consider the 4×n case and the 5×n case, where we expect to make some gains by turning pentominoes sideways, but lose by needing extra copies of the other pentominoes to stretch across the rectangle. In the 4×n case, we need four copies of I, one each of the 2×4 pentominoes, and two each of the rest. That makes 23, and we need one more to make a multiple of 4, so 24×5=4×30=120 is a lower bound for 4×n. For 5×n, we need one I and two each of the rest: area 5×23=115. There are no gains to be made by going wider than 5, so the proof is done.

3. munizao says:

Er, of course, two of the pentominoes have 2×3 bounding boxes. Sorry, I’m not entirely awake. But you can still treat them the same as the 3×3 ones, so the proof still holds.