## Trinity (Solitaire XI)

The puzzle from over a month ago is based on a curios 3-coloring of the edges of the dodecahedral graph:

Whenever you delete the edges of one color, the remaining edges form a Hamiltonian cycle. Incidentally, on the dodecahedral graph there are two different such paths, up to symmetries of the graph. The question arises whether there are more such graphs.

One such example is the Heawood graph drawn on a torus above (i.e. you identify opposite edges of the big shaded hexagon like in hexagonal astroids). There is a very symmetrical (and boring) edge coloring that colors all parallel edges the same way that is triply Hamiltonian, but there is a different one as well. You can think of this as living on the vertices of a map drawn inside a big hexagon, so that you can travel across a hexagon edge by continuing at the same position of the opposite edge. There are three types of roads, color coded, and each inhabitant of your country is issued two colored passes allowing them to travel on roads of those two colors only. Luckily, the colorings above allow each inhabitant to still travel everywhere, regardless of the passes they have been issued.

To turn this into a puzzle, we use the dual tiling by triangles, that gives us a single triangular puzzle piece (and its mirror) to place on the vertices of the graphs. For instance, below we place one triangle (with its translated copies) on three of hexagon vertices, choose another triangle elsewhere, and are tasked to complete this to a triply Hamiltonian tiling. The solution on the right corresponds to the first coloring of the Heawood graph up above.

For a decent puzzle, the Heawood graph is a little bit too small. Now, Hamiltonian cycles on trivalent graphs have been extensively studied (partially because of Tait’s conjecture, which turned out to be incorrect), so I suspect this phenomenon is known. There is a list of small symmetric cubic graphs, the Foster census, and it is no hard to write code that searches for more examples. Below is thus today’s puzzle, on Foster26A, also a map on a larger hexagonal torus. Complete it to make it triply Hamiltonian.

## Instant Insanity

This post is about a mathematical puzzle and not the current state of daily affairs. The puzzle consists of four cubes, with faces colored in four colors:

If you want to make your own, you can print out the nets below and fold.

The goal is to stack the four cubes together so that each of the four long faces of the 4 x 1 x 1 tower show all four colors.

According to Jerry Slocum, this puzzle goes back to 1900 when Frederick A. Schossow marketed a version of it under the name Katzenjammer Puzzle. Katzenjammer is German for hangover…

It has since appeared in many variations. Its latest incarnation under the current name Instant Insanity was discovered by Frank Armbruster and has been marketed by Parker Brothers since 1967.

We will solve he puzzle using graph theory. Each cube will get encoded in a graph. To do so, we use as vertices the colors (yellow, orange, purple, and green), and connect two colors by an edge if the two colors occur on opposite faces of the cube. Thus we obtain for each colored cube a graph with four vertices (colors) and three edges (opposite faces).

Before we continue, let’s see why these arbitrary looking graphs contains all the information about the cubes that is necessary to play the puzzle: If the graph of a cube is given, we know all colors of pairs of opposite faces for that cube. Using a blank cube, we can first color the front and back face with a pair of these colors. It doesn’t matter which color we pick for the front, because we could turn the cube over. Using a second edge of the graph, we then color the left and right face with the two colors of the end points of the edge. Again it doesn’t matter which color we use for the left side, because there is a rotation fixing front and back that flips left and right. Finally, there are two possibilities remaining for coloring the top and bottom face of the cube. These lead to truly differently colored cubes, but both are equivalent for solving the puzzle, as the top and bottom colors of the tower don’t matter for the puzzle.

Coming back to solving the puzzle, we combine the four graphs we have created for each cube into a single graph with multiple edges. The edges are now labeled from 1 through 4 to indicate from which cube they come. How does this graph help us to solve the puzzle?

Suppose we have stacked the cubes together so that both the front and back side of the tower show all four difference colors. The four front and back sides of each cube represent each an edge in our graph, which we give a direction so that they always point to the color of the back edge. Let’s mark these edges say blue. Thus we get four blue edges that begin at four different colors and end at four different colors. As there are just four colors, each vertex has an edge ending and an edge beginning there. This means that following the blue edges, we have found a doubly Hamiltonian circuit – a cycle or collection of cycles that pass through all four vertices (colors) of the graph, and uses edges with each of the four labels (cubes).

Vice versa, any such path can be used to stack the cubes so that front and back side of the tower show all four colors.

Next we will show that any such system of circuits must go once around the square marked by the four colors.

If this were not the case, it would decompose into several components of lengths 1+3, 1+1+2, or 2+2.
While in each case there are Hamiltonian circuits, none of them are doubly Hamiltonian.

Thus we only need to look for Hamiltonian paths that go around the square, and can ignore the loops at orange and green as well as the diagonal connection from purple to orange.

Consider the top and bottom edge, which both have an edge labeled 4. As each edge label can only occur once, one of these two edges must use an edge with a label other than 4. We make a case distinction: First, let’s assume the bottom edge uses label 3. Necessarily then, the right edge then must use label 2, the left edge label 1, and the top edge label 4, and we get the Hamiltonian path marked red.

Now let’s assume that the top edge is using label 1. Thus we have to use for the left either label 2 or 3, and the other label 3 or two for the right edge. Either choice leaves us with label 4 for the bottom edge. One of the choices is the path marked blue, the other one has labels 2 and 3 exchanged in the left and right connections. Thus there are only three different possible Hamiltonian paths.

To finally solve the puzzle completely, we will need to take care of the left and right faces of our tower. By associating a directed edge for each cube from every left face to every right face, we get a second doubly Hamiltonian path in our graph.
This second path must be edge disjoint with the first, as we cannot use a pair of opposite faces of the same cube twice.

As the second and third of our three Hamiltonian paths are not disjoint, one of the paths we seek must be the red path. This uses edge 2 on the right hand side, so that the second Hamiltonian path can only be the blue one. They are indeed edge disjoint, and thus solve the puzzle.

## Arrows (From the Pillowbook IV)

So far, we have looked only at pillows with concave and convex edges. Today, we begin also to allow straight edges. To keep it simple, let’s look at the three different pillows that have two straight edges, one concave, and one convex edge. Here they are. I call them the arrow pillows.

Because they have straight edges, we can finally tile rectangles that have straight edges, too, like so:

There are a few immediate questions: Is this always possible? Can we say something about the number of arrows of each type we need? The key to the answers is indicated in the right image. The convex edge of one arrow pillow (the predecessor) fits snugly into the concave edge of a second arrow pillow (the successor), thus providing us with a recipe to move from one pillow to a neighbor. If we have a tiling of a rectangle just by arrow pillows, this sequence of consecutive successors must form a closed cycle. Therefore, the entire rectangle will be covered by possibly several such closed cycles, so we have what is called a Hamiltonian circuit. Readers of my blog have seen these before.

Vice versa, given any Hamiltonian circuit and a direction for each component, we can lay out the arrow pillows along each path to obtain a tiling. Below are two more examples with two components each that use only right and straight arrow pillows.

Can you tile a 5×5 square with arrow pillows? If you checkerboard color the rectangle black and white, any path alternates between black and white squares, so a closed path will cover the same number of white and black squares. Thus in particular Hamiltonian circuits must have an even length on rectangles.

Let’s look at a single closed cycle, and let’s assume we follow it clockwise. Then there must be four more right turns than left turns. We have seen examples with no left turn arrow pillow, and with two left turns. Below are examples with just one and just three left turns.

These little insights not only help to show that some tiling is impossible, they also give hints to design tilings. For instance, suppose you want to tile a square using the same number of straight, right, and left arrow pillows. Then the smallest square for which this could work is the 6×6 square. We also see that we need an even number of cycles in our Hamiltonian circuit in order to balance the left and right arrow pillows. The simple solution below uses two mirror symmetric tilings of 3×6 rectangles.