Archive for the ‘Recreational Mathematics’ category

Newer Entries »

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:

Why L-topia Is Awesome

December 7th, 2010

It’s the holiday shopping season, so I figured it couldn’t hurt to write a post or two on the puzzles I am selling.

Every mathematical puzzle designer worth his or her salt has an argument for their puzzle’s awesomeness using impressive sounding mathematical justifications. This, for L-topia, is mine.

There are 12 pieces in the set. Empirically, 12 is a good number of pieces for a mathematical puzzle. There are 12 pentominoes, and 12 hexiamonds.

The shape of the pieces, an l-tetromino, has some desirable properties. It is very highly tileable. Two factors that affect the tilability of a polyomino are its size and its symmetries. Smaller and less symmetrical polyominoes are the most tilable. The l-tetromino is the smallest asymmetrical polyomino, and the only asymmetrical tetromino, so it should be the most tilable of all.

A set of 12 l-tetrominoes tiles a 6×8 rectangle in 1114 ways. That’s probably the most for any set of 12 copies of a single polyomino tiling any rectangle, but it’s not that impressive compared to other sets containing multiple shapes. For example, the 12 pentominoes can tile a 6×10 rectangle 2339 ways. 

But because the shapes are all the same, if you mark all of them in some way to distinguish them from each other, (as the holes on the L-topia pieces do) every permutation of placements of the 12 l-tetrominoes can create a distinct tiling. Now the total number of tilings is roughly 1114 · 12!. (Actually, it’s slightly less because some of the tilings of the rectangle are symmetrical: about 55 of the 1114 solutions are symmetrical by reflection or 180° rotation, so the total is about 1059 · 12! + 55 · 12! / 2, or about 520 billion.)

Well, that’s a pretty impressive number, but having an impressively large space of possibilities does not, by itself, make for a great puzzle. In this case, however, I do think it is helpful, and I’ll explain why presently.

Suppose I think of a proposition that can apply to any of the holes in the set. For example, that the hole appears in an odd numbered row. Because there are two different kinds of holes, it may be elegant to use either the opposite of that proposition, or some proposition that is complementary in some way, to apply to the second kind of hole; in the problem illustrated by the solution above, we have the round holes in odd rows, and the square holes in odd columns. Suppose the probability of the proposition being true is ½, and suppose that the probability for each hole is independent from the others. (One must take care that the placement of holes on the pieces doesn’t fatally interfere with independence; if, for example, we had asked for circles on odd rows and squares on even rows, there would have been pieces that could not have been placed legally anywhere.) Then the probability that the proposition is true for all of the holes is 1/224. Given this piece of information, we can get an expected number of tilings where the proposition is true by multiplying that probability by the total number of tilings.

The result is about 31,000. That number is tiny compared to the size of the total space of tilings, but I can say from experience that it makes for puzzles that are challenging but solvable. And it gives us wiggle room to use propositions with probabilities that are a little smaller than ½, or for which the probabilities are not entirely independent. The result is that we can come up with a wide variety of propositions to use in designing puzzles with the expectation that they will provide a good puzzle solving experience. L-topia isn’t just a puzzle, it’s a natural puzzle creation kit!

Why L-Topia isn’t awesome, and Agincourt is

Unfortunately, to be perfectly honest, being a “puzzle creation kit” interferes with L-topia’s accessability as a puzzle. Because the circular and square holes have no inherent meaning, but have to have their meanings imposed by a puzzle’s directions, you can’t simply take the pieces out of the box and start solving.

Agincourt, on the other hand, with its 64 squares with an arrow in each, practically begs to be turned into four 4×4 layers with the arrows aligned. Of course, there are other challenges to be found, but the one that literally comes out of the box is both elegant, and has a reasonable level of difficulty. (Some of the L-topia puzzles are better for hardcore puzzle solvers.)

Once again, I have both puzzles available for sale. Order soon for delivery by Christmas!

No comments »

Posted in Recreational Mathematics, Zapped Puzzles

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:

Polystick Problems from Polyomino Solutions

September 7th, 2010

Polysticks (or polylines) are connected sets of segments in a square grid. (Polysticks on other grids are possible, but haven’t seen much attention.) The tetrasticks, of which there are 16, seem to be the most natural set for puzzle making. Donald Knuth has explored tetrastick problems, and posed the problem of tiling an Aztec Diamond with the 25 one-sided tetrasticks, which was solved by Alfred Wasserman. Here’s one I’ve come up with:

Problem #15: Tile the above shape with two sets of the five tetrominos and one monomino, and tile the borders of these polyominoes with the 16 tetrasticks. Here’s an attempt I made that fell short by a few tetrasticks, but it should give you an idea of the form a solution would take:

The observation that the lines formed by the pieces in a polyomino tiling could themselves be tiled by polysticks seems obvious, but I have not seen it elsewhere. After picking the 16 tetrasticks as my puzzle pieces for the polystick stage, I had to find a set of polyominoes to use. Since one of the tetrasticks is, in fact, the outline of a 1×1 square, or monomino, the monomino had to be present. A double set of tetrominoes plus the monomino gives a good quantity of segments for our tetrasticks to cover, and gives us an area of 2 * (5*4) + 1 = 41. The perimeter of the figure to be tiled is constrained by the following formula:

2 * total segments in the polystick set – sum of perimeters of polyominoes = perimeter of entire figure

In this case, (2 * (4 * 16)) – (4 + 2 * 48) = 28

So I needed a figure to tile with area 41 and perimeter 28, and came up with the shape above.

There are 136 solutions for the tetromino tiling with the monomino in the center as shown. (See these solutions in a Java solver applet.) I’ve experimented a little with the tetrastick stage of the problem by hand, and I’m convinced that there are no tetrastick solutions for most, if not all, of these tetromino solutions. But if it doesn’t work out in the case with the monomino in the center, I suspect there are enough solutions with the monomino elsewhere for it to be very likely that one will work. Many of the tetromino solutions fail to contain a site where the “+” tetrastick can be placed that doesn’t overlap the “□”.

Another issue that surfaces in this problem is horizontal-vertical segment parity. Eleven of the tetrasticks have even parity, that is, however you place them, they will always contain even numbers of both horizontal and vertical segments. Five of them have odd parity, and will always contain three segments of one orientation and one of the other. Because there are an odd number of pieces of odd parity, the parity of the set of tetrasticks as a whole must be odd. This means, without even starting to try placing tetrasticks on a tetromino solution, we can rule out the possibility of tiling it just by counting the number of horizontal or vertical segments. (Because the total is constant, we don’t need to count both.) If that number is even, the tetrasticks can’t tile the figure. The tetromino solution that I used in my attempt above has the correct (odd) parity.

I dredged this problem up from my archive of the polyforms mailing list, where I posted it in February, 2001. It got no takers then, but I thought it an interesting enough problem to deserve a second airing. I looked for other problems of this type in preparing this post, but I didn’t find anything good. Having both the area and the perimeter of the figure to be tiled constrained by the pieces used limits the possibilities a lot.

5 comments »

Posted in Recreational Mathematics

Tags:

Wanderings on a Six-Sided Die

August 27th, 2010

Here’s a little doodle on a grid based on a standard six-sided die:

I started by deciding that the pip positions should all connect North to south and East to West. It followed logically that I could have a puzzle where the solver could choose one of two possibilities for each empty cell: connecting North to West and South to East, or North to East and South to West. Because there are 33 non-pip squares, there would therefore be 233=8,589,934,592 ways to fill the grid. The lines on the outside of the grid show how the squares would connect when folded into a cube.

As an exercise, I found a way to make a single circuit, which is shown above. While that turned out to be about the difficulty of puzzle I can handle in something I am solving by hand, I’m sure there are more interesting specimens to be found.

Unfortunately, because the number of pips is odd, it’s impossible to have two circuits where each go through all of the pips. The circuits would have to cross each other an even number of times. But we could have one of the circuits cross itself once, and then have both circuits go through the remaining 20 pips. (Let’s call that problem number, oh what are we on, #12. By the way, the problem numbers are so that I can keep track of solvers of numbered problems and give them the fame they deserve. Nobody has solved any yet. You can be the first!)

Another possibility would be to use three circuits, each crossing itself once, and each visiting 12 pips in addition to the self-crossing. That’s #13.

I like big, wide ranging circuits here, so a constraint I like is to have circuits that visit all 6 sides. So bonus points on the preceding problem for having all three circuits do that. And that suggests #14: Maximize the number of circuits in a solution where all circuits present visit all 6 sides.

I thought early on that I could take this in the direction of a knot theoretical puzzle, but then one would have to keep track of which thread went under which in the crossings, which seemed like an unnecessary complication. I also think it would be interesting to make a multi-state maze (See Robert Abbott’s site for some good examples) using this template, but I haven’t yet had any good ideas for how that would work. If you have a good idea for a variation on this puzzle, I’d love to hear it. (This is of course true for all of my puzzles.)

For your solving convenience, I have an empty grid image here, and the Inkscape SVG file I used to produce it and the image above is here.

5 comments »

Posted in Recreational Mathematics

Tags:

Gordon Hamilton’s Polyanimal Zoo

April 6th, 2010

Here’s a problem that I heard from Gordon Hamilton at Gathering for Gardner 9, and tracked down to an article of his in issue #10 of Pi in the Sky, a western Canadian math magazine for high school students and teachers.

A polyomino animal can eat another polyomino animal (his perhaps overly cute term is “polyanimal”) if the second one can be placed inside the first. Find animals of sizes 4, 5, 6, 7, 8, 9, and 10 that can live together peacefully (none can eat any of the others) within a 7×7 square pen.

This is really a satisfying puzzle to solve. Usually in polyform tiling puzzles, you spend a fair amount of time feeling out the territory, learning which pieces like to go in certain places, and which you want to deal with first and which you want to save for the end. But then, the larger part of the solving time is spent in trial and error with various configurations attempted at random until at last you run into a solution.

Here, the whole solving process is learning about the territory of the puzzle, and none of it feels like random crunching. I highly recommend giving it a try, but if you just want to see a solution, mine is here.

Of course, the matter of polyominoes fitting inside other polyominoes is an area that I’ve dealt with in my Polyomino Cover material, which I summarized in my presentation for G4G9. And one of the problems in Hamilton’s Polyanimal problem set is the same as what I’ve called the minimal pentomino cover problem. But most of them are completely different, which only reinforces my belief that this is an area with a lot more waiting to be discovered. (His last problem is “Design a Polyanimal Game.” Now that’s open-ended and provocative!)

No comments »

Posted in Recreational Mathematics

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:

Holy Hyperbolic Heptagons!

February 19th, 2010

Recently, MathPuzzle highlighted a program called MagicTile for playing with Rubik’s Cube variants on various tessellations in spherical, Euclidean, and hyperbolic geometries. One interesting hyperbolic tessellation is the {7, 3} tessellation, composed of heptagons, with three meeting at every corner. Twenty-four of these heptagons can be wrapped up into a genus-3 (that is, topologically like a torus but with three loops instead of one) “Platonic solid” called Klein’s Quartic, which John Baez has a fascinating page about.

Polyforms based on hyperbolic tessellations appear to be a relatively unexplored area. I’ve come across a couple of references on counting the n-cell polyforms for a given tessellation, but I haven’t found evidence that anyone has actually used them for puzzles. So I set myself this one. There are ten tetrahepts on the {7, 3} tessellation. Could they tile two copies of the same shape?

An implicit constraint in my solution of this problem was that the shapes could extend no farther than the second ring around a central heptagon. I searched for a solution using plastic game counters that would not have fit on any heptagons farther out on the diagrams I used as solving boards. I also knew that I was going to make images to show on my blog, and they would be clearer if there were no relatively tiny heptagons in the solution. In fact, the decision to find a puzzle in two pieces was affected by the observation that using an extra Poincaré disk would remove the need to use the tiny outer heptagons.

This was a pretty difficult puzzle to solve by hand, so I feel like I’m being a little mean using an even harder, (and perhaps impossible) variant as the numbered puzzle for this post:

#8: Find a symmetrical shape for which two copies can be tiled by the ten {7, 3}-tetrahepts. In addition to mirror symmetry, 180° rotational symmetry around the midpoint of an edge could work. (The other modes of rotational symmetry of the tessellation won’t work for a 20 cell shape.)

I would also love to see what other puzzles people can come up with on this or any other hyperbolic tessellation.

No comments »

Posted in Recreational Mathematics

Tags:

Hexiamonds on an Octahedron

January 26th, 2010

Here’s an interesting problem that seems not to have gotten as much attention as I think it deserves. The twelve hexiamonds contain a total of 72 triangular units. A regular octahedron with edges 3 units long can fit 9 triangles on each of its 8 faces, exactly enough to tile with the hexiamonds. Some individual solutions to this problem have been found. A solution at Livio Zucca’s site bears the label “Adrian Struyk 1963?” so we may assume the problem has been around at least since then. Another solution by Michael Dowle is here.

Notice that you can unfold an octahedron to produce a net in the form of an octiamond. This provides another source for solutions. The octahedron has 11 different octiamond nets. Pieter Torbijn found that 24 enlarged octiamonds could be tiled with the hexiamonds; of these, 5 are nets of an octahedron.

As far as I know, nobody has made an exhaustive computerized search for solutions to this problem. You can be the first!

#4: How many distinct ways can the hexiamonds tile an octahedron?

The octahedron has a large amount of symmetry compared to any planar figure that these pieces can tile. It has 48 automorphisms, or ways to map the solid onto itself. This would indicate a relatively small number of different solutions, since many solutions will be mappings of each other over the various ways of rotating and reflecting the octahedron. On the other hand, the shape lacks external borders, which ought to greatly increase the number of possibilities.

Some solutions have a piece that wraps around and caps a vertex. This could be considered an aesthetic flaw, because it would be impossible to tell which hexiamond the capping piece is just from knowing what triangles it occupies; you must also know its edges.

There are 7 different pieces that can cap a vertex, one of which, the pistol, can cap it in two distinct ways. Notice that due to the symmetry of the shape it makes when it caps a vertex, only the orientation of the sphinx is a riddle; its identity is never in question.


#5: How many solutions have a capped vertex?

#6: What is the largest number of vertices that can be capped in a solution? The ideal would be for all six vertices to be capped with all of the above hexiamonds except the sphinx.

The octahedron has twelve edges, the same as the number of hexiamonds. This suggests another problem:

#7: Is it possible to tile the octahedron so that each of the twelve hexiamonds is folded across exactly one of the edges of the octahedron?

2 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: