Posts Tagged ‘pentominoes’

Maximal Irreducible Contiguous Covers

April 28th, 2011

A cover of a set of polyforms is a shape (or set of shapes) into which each member of the set could fit. Mostly I’ve looked at problems involving minimizing the size of a cover. This problem goes the other direction.

A reducible cover is one where a cell can be removed and the remaining figure is still a cover. An interesting problem then is to find an irreducible cover in a single piece that is as large as possible. (Why a single piece? Well, without specifying that, the largest irreducible cover will simply be all of the shapes in the set in separate pieces.) Here’s a (conjectured) maximal irreducible contiguous cover (MICC) of the pentominoes:

The above solution has been on my polyomino cover page for a while. Here are a couple of new results, (still just conjectured since I found them by hand rather than exhaustive computer search, and I am not able as yet to prove they are maximal.)


An MICC (?) of the hexiamonds


An MICC (?) of the pentaedges (shown in two copies for clarity)

Between these solutions, we see some patterns emerging. Certain polyforms are in some sense distinctive: they have features that do not occur in other polyforms in the set. This makes it easy to make a large cover that includes exactly one copy of them. Other polyforms end up serving a connective function. For example, there are quite a few occurrences of the L pentomino in the first figure, so removing a cell will never make the cover cease to include an L. By using a few pentominoes as many times as possible in this connective function, more pentominoes are left over to occur singularly.  In some cases multiple polyforms that occur only once are forced to overlap, so we don’t get their full number of cells to add to the cover, but we do get a few. This is shown with the outlined hexiamonds above. In the case of the pentominoes, we have one cell where two T pentominoes overlap; since these are the only two T pentominoes in the figure, the cell can’t be removed from the cover.

Problem #25: Find maximal irriducible contiguous covers of anything and everything! This problem ought to yield interesting results for any kind of polyform you can throw at it.

One final note: It was slightly unfortunate that I chose the word “cover” to represent a concept in polyforms when it already had an unrelated meaning in graph theory; it’s even more problematic now that I’m using graphs themselves as polyforms. It appears that in graph theory, the appropriate term is “common supergraph”. I could use “common superform”, although one problem is that polyforms, unlike graphs, are generally not allowed to be disconnected, and for some problems (though not this one) we want sets of polyforms that aren’t connected to each other. Perhaps “common superformsets” in that case, as ugly as it sounds.

No comments »

Posted in Recreational Mathematics

Tags:

3×3 block Pentominoes and Hexominoes

January 21st, 2011

There are 8 pentominoes and 8 hexominoes that fit in a 3×3 cell. The combined set seems to cry out to be presented in a 4×4 grid of 3×3 blocks, with the pentominoes and hexominoes in checkered positions:

The best I could think to do was make a figure that is connected, hole-free, and has a rotationally symmetrical pattern of connections between blocks. I had hoped to make them into a geomagic square, but now I’m pessimistic about that working. And the trick from my magic 45-ominoes of making all rows and columns have the same number of cells in polyominoes won’t work here because the total number in each row of 3×3 blocks is 22, which isn’t divisible by 3.

I’ve looked before at problems involving moving a single cell at a time to cycle through a set of polyforms. Because this set has equal numbers of pieces at two consecutive sizes, it invites using adding and removing single cells, rather than moving them, as the action for taking one piece to the next in a path:

Because the X pentomino has only one possible predecessor or successor, it cannot be part of a cycle, but it is still possible to make a path through all of these pentominoes and hexominoes with the X as one of its endpoints.

1 comment »

Posted in Recreational Mathematics

Tags:

All Pentominoes in 5

December 13th, 2010

I’ve been thinking about variations on the problem of cycling through all twelve pentominoes by moving a single cell at a time. (I wrote about this in a previous post.) Constraining the way that the squares are allowed to move led to something almost like a chess problem.

The problem:

Starting with the above position, take five turns as follows:

A turn consists of moving one white knight, then moving one black knight, according to standard chess rules.

After each turn, the squares occupied by the ten knights must form two separate pentominoes.

After the fifth turn, all twelve pentominoes must have appeared exactly once. (This includes the two that are present in the starting position.)

[I may make a separate post discussing and spoiling the puzzle later.]

2 comments »

Posted in Recreational Mathematics

Tags:

Rectangular Pentominoes

October 29th, 2010

When I had Agincourt made, I purchased a bulk order of 4″ × 4″ × 1″ white cardboard jewelry boxes. They look quite nice, and they fit both Agincourt and L-Topia, but I have enough of them that I’m on the lookout for ideas for polyform puzzles that fit nicely into a few square layers. And now I’ve found one:

I stumbled upon this by noticing that there are 21 pentominoes of this symmetry type, which could make three 5 × 7 layers. I wanted square layers; usefully, squashing the cells into rectangles with a 5 : 7 ratio of width to length simultaneously gave me the square layers and gave the cells the right type of symmetry.

It’s been observed that any of the subgroups of the symmetries of the square can be used as the basis for a type of polyomino puzzle. (See Peter Esser on pentomino variations, and particularly the page on parallel polarized pentominoes, which are equivalent to rectangular pentominoes.) For Agincourt, I physically realized one of these types by laser-cutting symmetrical, arrow-shaped holes in every square cell. Other types have been made by changing the shape of the cells themselves. Rhombic pentomino sets have been produced by Kadon as Rhombiominoes. Sets of rectangular polyominoes, shaped like Meiji chocolate bars, have been produced by Hanayama. (These may not be equivalent to the rectangular polyominoes above, if the top is distinct from the bottom, which isn’t clear from the pictures there.) I’m not aware of anyone who is producing complete sets of rectangular pentominoes, so there’s a gap I’m willing to step into.

If you take out the pentominoes with a diagonal line of symmetry in their non-squashed form, (the green ones above) the remaining 18 pentominoes come in 9 pairs, where each pair contains two different squashed versions of the same pentomino. With these pieces it is interesting to try to tile a pair of shapes with the same orientation such that one piece from each piece pair is in each shape. (Note that if the two shapes had different orientations, you could always make the second shape with corresponding pieces in the same position as the first, but squashed in the other direction.)

Since the set has area 90, the obvious thing to try is two 9×5 rectangles. The next most obvious thing to try is two 7×7 squares with corners removed. Neither of these seem to work, although I have no proof.

One thing that does work is a 7×7 square with a 4×4 square cut out of one corner. But this is again just the case where you can trivially get the solution to the second piece by squashing the pieces differently, because this shape has diagonal “mirror symmetry”.

Another problem is finding three congruent shapes, each of which has the following property: three of its pieces have their twin in one of the other two shapes, and three have their twin in the remaining shape:

I’m looking into having some sets of the rectangular polyominoes made, and if I can do so economically, I’ll sell them through the store. (Sadly, TechShop Portland, the facility where I made Agincourt, has gone away, so I will need to look at other options.)

No comments »

Posted in Recreational Mathematics, Zapped Puzzles

Tags:

Pentomino Cover Cycles

March 17th, 2010

What’s the smallest shape into which any of the 12 pentominoes can be placed? I call this old chestnut the “minimal pentomino cover” problem, and I’ve spent a lot of time working on a number of variations on it. For the purpose of introducing and illustrating the basic problem to my dear readers, I wanted to use an animated GIF file showing all of the pentominoes in turn being placed on a minimal cover.

An aesthetically pleasing way to cycle through the pentominoes would be to move one square at a time. This is in fact possible:

A couple of variations on the problem of finding such a cycle suggest themselves:

#9: Minimize the total distance the squares move per cycle. The taxicab metric seems to be more sensible and simpler than Euclidean distances here. I made no attempt to do any minimization in the above solution, so I’m sure there is room for improvement.

#10: If you gave every square in the pentominoes a distinct color, and kept the color the same when a square moved, you could keep track of where the squares end up at the end of a cycle. During the cycle illustrated above, two pairs of squares switch places. Is there a cycle of single-square moves through the pentominoes that ends with each square in the same place it began?

Notice that the central square can never move, because the only pentomino placement without the central square is one of the P pentomino, for which the only valid square movements turn it into a U pentomino. It would need movements to two different pentominoes to be part of a cycle.

For both of the above problems, the other 9 square pentomino cover would also be a valid substrate:

Since this one has no immobile squares, another problem using it may be solvable:

#11: Find a cycle where the permutation of the squares from one cycle to the next is cyclic (in the second sense in the linked article.) That is, successive iterations of the cycle will eventually take each square in a pentomino to all of the other positions in that pentomino.

Some very good news: I’ve been invited to the 9th Gathering for Gardner conference in Atlanta later this month. The Gathering for Gardner is an invitation-only conference  held in honor of Martin Gardner, who brought recreational mathematics to a generation through his columns in Scientific American. That generation was not my generation, but it was impossible to miss his imprint on later writers, and I’ve picked up used copies of several of the collections of his columns. A large proportion of the names on the spines on my recreational mathematics bookshelf are represented among the invitees, so this will be really special for me.

2 comments »

Posted in Recreational Mathematics

Tags:

Pentomino Layer Cake

February 27th, 2010

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.

3 comments »

Posted in Recreational Mathematics

Tags:

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/

2 comments »

Posted in Recreational Mathematics

Tags: