Posts Tagged ‘packing’

2-coloring Pentomino Packings

January 24th, 2010

I like to collect pentomino coloring problems.

So it should come as little surprise that I was intrigued by the cover of Puzzle Fun 16. Puzzle Fun was a ‘zine produced by Rodolfo Marcelo Kurchan in the ’90s covering a variety of polyomino problems. I missed out on subscribing to it myself, and the Puzzle Fun website languished for a decade after new issues stopped appearing.

A few months ago, Kurchan put the content of all of the back issues of Puzzle Fun online.

Puzzle Fun 16 focused on pentomino packing problems. Packing problems differ from tiling problems in that empty space is allowed, and the goal is to minimize the amount of empty space required. Packing, usefully, makes some kinds of problems possible to solve that would not be solvable as tiling problems.

One such puzzle type is packing polyforms that are 2-colorable, (that is, one can use two colors to color every piece such that no piece touches another of the same color.) This is the puzzle type I saw on the cover of Puzzle Fun 16.

The problem itself was this: Place two sets of pentominoes in the smallest possible rectangle such that no pentomino touches another in the same set. [PF problem #549]

A solution was printed in Puzzle Fun 18:

(Solution by Hector San Segundo.)

I should note that this problem implies strict coloring: pieces are not allowed to touch even at corners. I am more interested in non-strict coloring, which is generally the default in coloring problems, and I am interested in colorings of a single set of pentominoes. (Which all of the problems on my pentomino coloring page are.)

#1: Place a 2-colorable (non-strict coloring) set of pentominoes in the smallest possible rectangle. My best attempt has 65 squares:

Filling out the matrix of variations gives two more problems:

#2: As #1, but with a strict coloring.

#3: As in PF #549, but with a non-strict coloring.

(The following problem in PF 16 (#550) was a variation on #549 minimizing perimeter rather than area, but this is less interesting to me.)