# Archive for December, 2010

## Polysticks on a Regular Spanning Subgraph

December 24th, 2010

If any of you haven’t seen them yet, Vi Hart’s “Doodling in Math Class” videos are some of the best expressions I’ve seen of the joy of Recreational Mathematics. The Snakes and Graphs one is especially good, and it contains, despite all of the Internet Meme Years that have passed, a Snakes on a Plane reference.

Ed Pegg wrote a Math Games column in 2006 riffing on the notion of Snakes on a Plane. There’s some great stuff in there, but one could probably fill another column with material that didn’t make the cut. For example, he includes strip polyominoes, which have squares on each end that border only one other square, and are connected by a path of squares that border exactly two others. But linear polysticks, despite being at least as snakey, are absent. What can we do with linear polysticks? To me, they seem to cry out to be tiled onto some closed curve on the square grid. One could imagine some variant of Slitherlink (A Japanese puzzle type described in Ed Pegg’s column) where one would use linear polysticks to form the solution. (For another example of polysticks being used to tile figures on a square grid, see my previous post, Polystick Problems from Polyomino Solutions.)

I was, however, drawn to another source of closed curves. You can move a rook on a rectangular board in a series of single steps that visits every square once and returns to its starting point. Such a sequence is called a closed rook tour, and is the subject of an excellent article by George Jeliss. In graph theory terminology, a closed rook tour is a Hamiltonian of the graph with vertices that correspond to the squares on the board, and edges that connect vertices of neighboring squares. Closed rook tours have been enumerated for small rectangular boards, and it looked like there were enough of them to make it reasonable to hope that one of them could be tiled by a set of polysticks.

The nine linear tetrasticks seemed like a good place to start, and have a convenient total length of 36, which is just right for a 6×6 square. Sadly, the linear tetrasticks have a parity problem that prevents them from forming a closed curve. (A closed curve must have even numbers of both horizontal and vertical segments. Three of the tetrasticks have odd horizontal / vertical parity, and so the full set must have odd numbers of each.) But we can repair this parity problem by adding the 4 linear tristicks to the mix, giving us a total length of 48, which should work on a 6×8 rectangle. Adding the tristicks also improves the flexibility of the set and should make solutions easier to find, which was welcome as I was trying to solve the puzzle manually.

#17: Put these ——ing snakes on a ——ing closed rook tour of a 6×8 rectangular grid.

As you can see, I didn’t quite find a solution myself, but I got close! Perhaps you will be luckier, more persistent, or smarter than I.

Update, 2011-2-4: George Sicherman has found a solution!

Where to go next? Well, a reasonable extension would be to look at grids where every vertex has three edges instead of two. Unfortunately, any finite section of a square grid has to have corners which can only have two edges. We can get around this by looking at infinite repeating tilings instead, or equivalently, tilings of a torus. Here are the 5 tristicks tiling a 2×5 torus:

#18: Excluding (as we must) the “+” tetrastick, the remaining 15 tetrasticks have area 60. Place them on a 5×8 toroidal grid so that every point is connected to three others. (I don’t think the parity issue should be a problem in this context, but I could be wrong. See comments).)

Going back to graph theory terms, what we want is a 3-regular (each vertex has degree 3, that is, it has three edges connecting it to other vertices) spanning subgraph (a graph containing all of the vertices of the original, but not necessarily all of the edges.) A Hamiltonian could be called a 2-regular spanning subgraph, with the added provision that it must have a single connected component. I’m not worried about our solutions breaking into disconnected components in our 3-regular problems here. 3-regular graphs are also called “cubic”, but that term seems confusing in the context of polyforms, so I’ll avoid it.

Another way to make 3-regular spanning subgraphs of a grid is to use a triangular grid. Because corners can connect to three other points, we can use finite sections of the grid this time.

There are 12 tristicks on the triangular grid. The section of the triangular grid in the shape of the hexagon shown below has spanning 3-regular subgraphs with 36 edges.

#19: Find a tiling of the 12 triangular tristicks on a 3-regular subgraph of a section of the triangular grid bounded by a convex hexagon with side lengths 2,3,2,2,3,2.

Again, I got pretty close before I gave up; maybe you’ll have better luck. I’m pleased to have a problem that showcases the triangular tristicks. If the square polysticks don’t get the respect they deserve, this is doubly true for the triangular polysticks. Livio Zucca has a page with some triangular polystick solutions, (scroll most of the way to the bottom) but I can’t say that I’ve seen them elsewhere.

Got any other ideas for figures of segments in a grid that could profitably be tiled with polysticks? Any ideas for interesting triangular polystick problems? If you do, please share them in the comments.

## Hexiamond Minimal Covers

December 16th, 2010

I define a cover of a set of polyforms as a shape or shapes into which each polyform in the set can fit. I’ve written up an exploration of related problems on my recreational mathematics non-blog. Most of these problems use pentominoes or other polyominoes; it lately occurred to me that I had done a disservice to the hexiamonds, which are just as worthy of attention. So here’s a minimal (ten cell) cover of the twelve hexiamonds:

A proof of its minimality is simple. There are two ways that the bar and hexagon hexiamonds can be superimposed with maximal overlap:

Each of these contains nine cells, and neither is a cover of all of the hexiamonds. (The one on the left is missing the butterfly and chevron hexiamonds, the one on the right, just the butterfly. ) Therefore any cover must contain at least ten cells, so the one given above is minimal. (The nomenclature I’m using for individual hexiamonds is given on this MathWorld page.)

In fact, there are five ways to complete a cover by adding a single triangle (marked in blue below) to one of the figures above:

And these are the minimal covers produced:

The animation at the top of this post displays a cycle where a single cell is moved at each step. (I posted about this previously with the pentominoes in a minimal cover.) The hexiamonds have the handy property that their number is exactly twice their size, which leads naturally to the following problem:

Problem #16: Starting with a hexiamond with all cells labeled, find a sequence of single cell moves that cycles through all twelve hexiamonds, returning to the first hexiamond, and that moves each labeled cell exactly twice. Bonus points if the set of cells used is either a minimal cover or a 2×3 parallelogram. Bonus points as well for satisfying conditions like those of problems #10 and #11 in the post linked above. (All cells return to their starting positions, or all cells end up in a cyclic permutation of their starting positions.)

## 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.]

## 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!