Posts Tagged ‘packing’

More pentomino coloring problems on torus tilings

April 8th, 2018

Recently I revisited one of my old pentomino coloring problems, modified to apply to a tiling of a torus rather than a rectangle. That worked out well, so I might as well shamelessly continue to mine this vein.

There are 18 one-sided pentominoes. Six of them have reflection symmetry, and the other 12 are 6 sets of mirror pairs. A while back, I asked if there was a tiling with a three-coloring where the 6 with reflection symmetry share a color, and each mirror pair has one pentomino of each of the remaining two colors. Patrick Hamlyn found that there was no rectangle tiling that could be colored in this way, but there was such a tiling of the shape below:

The one-sided pentominoes have area 90, which is the area of a tilted square on a grid:

Problem #47: Find a tiling of a torus with this tilted square as its fundamental domain by the one-sided pentominoes with a three-coloring as described above. If possible, find a tiling with no crossroads.

Another older problem that could be adapted to a torus is the minimal 2-colored packing problem. Here’s my conjectured minimal 2-colored pentomino packing of a rectangle:

(I had forgotten that this was problem #1 on this very blog!)

Problem #48: Find a two-colored packing by the pentominoes of a torus with minimal area.

Obviously, you could just take the rectangular packing above and add a one unit “moat” around it to get a torus with a 14×6 rectangle as its fundamental domain, but surely we can do better.

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.)

http://www.puzzlefun.com.ar/