Polysticks on a Regular Spanning Subgraph

December 24th, 2010 by munizao Leave a reply »

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.

3 comments

  1. Bryce Herdt says:

    About #18, I’m afraid that parity does indeed come into play, and the answer is therefore negative.

    First, if we pick a subgraph on a 5×8 torus where each of the 40 points has three edges, then the (suitably-defined) complement where each point has one edge is equivalent to a domino tiling. Now, the chessboard coloring won’t be helpful here (beyond perhaps showing that a domino tiling exists); instead we should color alternate 5-square columns white and black. Then every vertical domino covers an even number of black squares, and every horizontal one covers an odd number. Over 20 black squares, that means an even number of dominoes will be horizontal and another even number will be vertical.

    That may be a bit of the long way around, but it follows that the original has-three-edges graph (the term is “cubic graph,” but that’s just confusing here) also has even numbers of vertical and horizontal edges. And unless I missed my count, exactly five of the tetrasticks have odd numbers of edges going each way.

    Well, maybe there’s greener pastures on a 41-point torus minus one point. I can’t work out a coloring right now that says this should fail, so here’s hoping.

  2. munizao says:

    Another way out would be to skew the tiling of the 8×5 rectangles so that each column of rectangles is one step down from its neighbor on the left. Now the bottom two rows can be tiled by five horizontal dominoes (one wraps around from the bottom row to the one above.) The remaining space is a 6×5 rectangle which can be tiled by (for example) 15 vertical dominoes. So both can be odd, and our tetrasticks should work.

    I suppose the more elegant way to phrase the weakened version of this problem is, “Find an arrangement of the tetrasticks excluding ‘+’ that ’tiles’ the square lattice by translation such that every point is on three segments.”

  3. You’ll be happy to know that the triangular polysticks are finally getting some respect and attention. I recently published a set of polytrig puzzles (“polytrigs” is my name for triangular polysticks, from “TRIangular Grid”).

Leave a Reply