Proof by Example (Push & Pop I)

Here is Push & Pop, a puzzle with a very simple mechanics. It is played on a single strip with a fixed number of fields, occupied by tokens that are stacked on top of each other (as in checkers)


Position 01

A move consists of taking some of the top tokens of a tower, and moving them onto a field that is as many steps away as you are taking tokens, within the limits of the game board. If the target field is occupied, just place your tokens on top. Note that you can take only pieces from the top, and are not allowed to change their order. In the position above, the possible moves are indicated by the arrows, and you can see the possible new positions below. 

Moves 01

You will gladly notice that the color of the tokens does not matter at all at this point. You will also notice that moves are reversible, because undoing a move is also a legal move. Games are in so many ways better than reality. 

A typical puzzle using this mechanic is given by two position, and the task is to transform the first into the second using only legal moves. Here is a simple example, played on a board of size three with two tokens of different color, placed on top of each other at the leftmost field. The task is to swap the position of the two tokens:

Puzzle0 01

This is not possible on a board of size 2 (why?), and requires five moves on a board of size 3 like so:

Solution0 01

Why should we care? Particular examples can often be used to gain universal insights. In this case, for instance, we have just essentially proven that any puzzle on a board of size at least three can be solved. How so?

We have shown that two adjacent tokens in a single tower can be swapped, if there are two fields available to the right. It does not matter if these fields are occupied or not, because we can just play on top of any existing pieces. It does also not matter if there are tokens below the two we want to swap, and not even if there are tokens on top, because we can move them temporarily out of the way (remembering that moves are reversible).

As the group of all permutations is generated by transpositions (use bubble sort), we can in fact permute the tokens in any single tower to our liking. Finally, to solve an arbitrary puzzle, we first move all tokens (piece by piece, if needed) onto a single tower on the leftmost field, then permute them into the order we need, and then move them into the desired target position.

Here is a puzzle on a board of size 5 with four tokens in 3 colors. You know now that there is a solution. But what is the shortest solution?

Puzzle5 01

To be continued…




Six by Six

This puzzle consists of a 6×6 square board and 36 arrow cards with 6 arrows in 6 colors. The goal is to place all arrow cards on the board such that

  • the entire board is covered with cards;
  • each arrow points to exactly one arrow of the same color in the same row or column.


The example above shows incorrect placements of arrows: The yellow arrow cannot point to another arrow, the left blue arrow points to two different blue arrows, and it is not possible to add to the four purple arrows, while correctly placed, two more purple arrows without violating the rules.

Circuits 01

Indeed, if the six arrows of one color are correctly placed, the arrows can be connected to a closed circuit. The figure above shows two closed circuits of six arrow cards. Note that the circuit paths may well cross. The following puzzles have a few arrows already placed, and need to be completed. Below to the left is simple example that shows how to find the solution.

Ex 1

First consider the green arrows. The arrow at e4 points to the right and therefore we must have another green arrow at f4, either pointing up or down. As there is already a green arrow at f6, the new arrow at f4 must point up. This leaves us with two more green arrows to place. Because we already have three horizontal arrows, the remaining arrows must be both vertical, and point to existing horizontal arrows. The only possibility is to place the new green arrows at c6 and e2, as shown above to the right.

Now let’s consider the red arrows. The one at e3 points down, leaving no choice but to place a red arrow pointing left at e1. There are two more horizontal arrows to place, and the only possibilities are b5 and f3, see below to the left.

Ex 2

Turning to blue, there clearly needs to be a left pointing arrow at f1, and the two remaining vertical arrows need to go to a1 and b6.

For yellow we have only two arrows given, but there are not many free spots available. We first are forced to put a left pointing arrow at e6 and then a down pointing arrow at d6. The remaining horizontal arrows go to c5 and d4.

Ex 3

The purple arrow at d4 can only be reached by a right pointing arrow at a5, and the one at c3 only by an up pointing arrow at c1. Then the arrow at c1 requires a left pointing arrow at d1, and the final purple arrow goes to a3.

Filling the remaining spots with cyan arrows is now easy, giving the solution.

Below is a new puzzle to warm up:

Arrowpuzzle 23

And here is a more difficult one. In both cases, there is only one solution.

Arrowpuzzle 02

Stellating the Icosidodecahedron in Black and White

DSC 1737

It is also this time of the year to chase away the dark hours by making presents. As in previous years,
we will make a stellation out of paper without glue. This year, we are going to stellate the Icosidodecahedron, one of the fancier Archimedean solids.


The stellation is quite simple, it is also a compound of the dodecahedron and icosahedron. The simpler compounds of a Platonic solid with its dual are also doable, see the post from two years ago.


To make it, we will need 20 triangles and 12 pentagons, so printing and cutting two of the templates below will do. I suggest to print four templates in two different colors and to make two models.


Then we start by sliding five triangles into one pentagon like so:

DSC 1739

Then we add five pentagons between two adjacent triangles.

DSC 1740

Next another five triangles:

DSC 1742

Now we have finished one half of the model. This already would make a nice dome for the backyard.

You can make another half and try to attach them, but I think it is easier to just keep going.
This next step is a little tricky, because to prevent the polygons from falling out, it is best to add a ring of alternating pentagons and triangles. When done, it looks like this:

DSC 1746

The last two steps (add five more triangles and one more pentagon) are then pretty clear, but still tricky because you have to insert the new polygons in four or five slits essentially at once.

DSC 1750

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.

Mutual Resistance (DePauw Nature Park II)

DSC 3635

A while ago, I posted pictures from the DePauw Nature Park. The area is still haunting me, photographically. The place offers a large variety of motives,

DSC 3536

and each image seems to demand its own treatment by choice of format, color space, and other adjustments.

DSC 3563

After several visits, I ended up with a fair amount of decent pictures, without a common theme besides being taken at the same location. It is as if this place attempts to resist any categorization.

DSC 3619

Here I am countering this stubbornness with a reduction to simplicity. The images are all square and black & white.

DSC 3549

But again, the place beats me with views like this, of undecipherable complexity. The dialogue will continue.

Over and Under

Time for a game. You will need one or more decks of the following 16 triangular cards.

Cards 01

The first game is a puzzle and asks to tile a triangle with all cards from a complete deck so that the tiles match along their edges, like so,

Challenge 01

except that in my attempt above two triangles don’t match. No hints today.

Next we use one or more decks to play a 2-person game. All cards are shuffled and form a single deck, top card visible. You will need three special cards, each just marked with one of the three card colors on it. Both players draw one of these color cards and keep their color secret. 

Now they take turns picking the top card from the deck and placing it on the table so that it matches previously placed cards. However, this time the matching has to happen along half-edges. For instance, after using a 16 card deck, the table might look like this:

Game1 01

Each newly placed card has to border a previously placed card, and match along half edges on all sides where it borders another card.

When all cards are played, the players reveal their secret colors and score. Note that the colored arcs form chains of equal color. Suppose that player A is orange and player B purple. A looks at all orange chains of length at least 2. There are three orange chains of length 2 and one of length 3. For each of these chains, A counts how often they go over a purple arc. This happens 7 times, and A scores as many points. Similarly, B looks at all purple chains of length at least two. There are three, of lengths 2, 3, and 4. They go over an orange arc six times, so A wins by one point.

The idea is to arrange cards in chains of your color that go often over the snakes of your opponent’s color. The problem is, of course, that in the beginning you won’t know your opponent’s color. So you might want to put cards that have your arc go under both other arcs not into chains but out of the way. This, however, might give away your color…

Finally, here is a 3 person game played on a hexagonal board of edge length 4.

Board0 01

The three players are dealt a color card each, and again the colors are being kept secret. You will need six decks of cards, for a total of 96 cards. Shuffle all cards and let each player grab 32. Then the players put their cards onto the board so that they meet at least one previously placed card along an entire edge, and match the colors of all cards they meet. After all cards are played, the board will look similar to the one below, except that there will be crossings.

Board 01

When the board is completely tiled, the players reveal their colors and score: For each completed circle of their color, the player counts how often that circle stays above the other two colors. This can happen (for each circle) between 0 and 12 times. That number is squared, and all numbers for all full circles for each color are added up, giving the score for that player.

There is a little catch to be aware of: There are two colors with 12 full circles each, and one color with 13 circles (purple in the example). Clearly the player with 13 circles will have an advantage when scoring. The first player will decide which color has 13 circles, and is therefore likely to claim the advantage. But then the two opponents might unite…

Spring Cleaning I

Spring Cleaning is played on a rectangular array of randomly placed dirt pieces. A sweep consists of removing a single row or column of consecutive dirt pieces.

Sweep legal

Above are some example of legal sweeps, and below are illegal sweeps.

Sweep illegal

This is a game for two players, who take turns by doing exactly one sweep. The player who sweeps the last time is the winner. This is an impartial game which means that each position is equivalent to a single game of Nim. This is usually bad news, because playing Nim well requires us to perform exclusive or additions of binary numbers in our head, for which our brains are not (yet) well equipped.

The good news here is that many simple positions are equivalent to very small Nim piles, meaning that computations are easy. I will explain this using an example. No proofs (even though they are easy, too).

Sweep win1

It’s your turn to find a winning move in the position above. You know (because I promise) that rectangles completely filled with dirt pieces are easy positions, so you will look for moves that separate the dirt pieces into such rectangles. Here is such a move:

Sweep win1 sol

After that, we are left with four separate rectangles, all completely dirty. This means that this game is equivalent to a game of Nim with four Nim piles. The question is what the pile sizes are. The answer is simple: Any rectangle both of whose dimensions are odd corresponds to a Nim pile of size 1, if both dimensions are even, the Nim pile is empty (size 0), and otherwise, the Nim pile has size 2. In our example, we have a 1×1 rectangle, a 1×3 rectangle, and two 1×2 rectangles. They correspond to Nim piles of sizes 1, 1, 2, and 2. The exclusive or sum of these numbers is 0. This is what we want, because it means that after this move, the game is equivalent to an empty Nim pile. From now on it’s easy. Suppose that our opponent performs a vertical swipe on the 1×3 rectangle. What do we do to return the game to Nim-value 0?

Sweep 3 01

We can sweep away any of the isolated dirt pieces: From then on, the game is symmetrical and we can win easily without any Nim-theory. And we better leave the two 1×2 rectangles untouched. Suppose we remove one of them completely. Then we are left with three 1×1 rectangles and a single 1×2 rectangle, which exclusive or sums up to a Nim pile of size 3, in which case our opponent can win.

Sweep 4 01

The winning move would be to reduce the remaining 1×2 rectangle to a 1×1 rectangle with a horizontal sweep.

So, if we know how to deal with Nim positions that consist of Nim piles of sizes 1 and 2, we will be able to win Spring Cleaning by dissecting a given position eventually into rectangles.