Transdissections

A few weeks ago, I explained that two Euclidean polygons are scissor congruent if and only of they have the same area. A scissor congruence is a dissection of the two polygons into smaller polygons (“pieces”) so that the pieces of the first polygon can be translated and rotated into the pieces of the second polygon. Then I asked whether we really need to rotate the pieces, or whether translating them is enough. For instance, can one dissect a square into pieces that can be translated into a second square that is rotated by say 45º?

 

 Mahlo 01

That this is possible is a consequence of a famous dissection of a square into two squares, shown above, which uses translations only, but tilts the square by an angle which we can make 22.5º. Then we need to repeat this process, tilting the other way, using a mirrored dissection.  This increases the number of pieces needed, and the question arises with how few pieces one can do this. A few years back I ran a contest about this in our department. The best solution with six pieces was found by Seth, one of our (then) undergraduates:

SolpuzzleSince then, I learned that there are solutions with only five pieces. Check them out!

Another cool example is the trans-dissection of a single pentagon into four smaller ones, by Harry Lindgren:

Fourpentagons 01

So, do trans-dissections always exist? Not at all. Let’s try to trans-dissect an equilateral triangle into a copy of it that is rotated by 180º. Suppose we found such a dissection, like the one above. Look at its horizontal edges. There are two types, the ones at the bottom of the pieces, (pointing right), and the ones at the top of the pieces, pointing left. When we add these together (taking the direction into account) for the dissected pieces, the edges in the interior cancel, while the boundary edges add up to the length of the bottom edge of the initial triangle.

 

 

Transdiss 01

 

Thus the oriented length of all horizontal edges of the two tiles that we want to dissect into each other need to be equal. This eliminates the possibility to rotate a triangle at all. The same argument works of course for all directions.

Therefore, in order for two polygons to be trans-scissor-congruent, they not only need to have the same area, but also have the same oriented edge lengths for all edge directions. Remarkably, these conditions are also sufficient, as was proven in 1951 by Paul Glur and Hugo Hadwiger. The argument is a little tricker than the one for general dissections, but not too bad. Maybe I’ll come back to it later.

Advertisements

Dissections and Area

Whenever need to explain what Mathematics is about, one of my favorite examples is the concept of area. The existence of an elementary notion of area hinges on the fact that any two Euclidean polygons have the same area if and only if they are scissor congruent, meaning that they can be cut into congruent pieces using straight cuts. To see this, it suffices to show that any polygon can be dissected into a square. Rect2square

The example above shows how to dissect a well-proportioned rectangle into a square. Here, well-proportioned means that the rectangle is not more than twice as tall than wide. If a rectangle is not well-proportioned, a few cuts parallel to the edges will make it so. Thus any two rectangles of the same area can be dissected int each other. We will use this later.

Triangul

Next we show that any polygon can be dissected into triangles. By induction, it suffices to find a secant inside the polygon. To find this secant, pretend that the polygon is actually the floor plan of a room, and we are standing at one vertex V . The two adjacent walls lead to two vertices A and B which we can see. If we can see yet another vertex W from our position, we have found our secant VW. If we can’t see another vertex, nothing obstructs our view in the triangular region formed by A, B and V , and thus A and B can be joined by a secant.

As a further simplification, we cut all triangles into two pieces along one of their heights so that all triangles become right triangles.

Now we have a collection of right triangles, which will need to be dissected into a single square.

Triangle2squareTo do so, we dissect each right triangle into a rectangle. This can be done as shown above by dissecting the triangle into two pieces along a segment parallel to one of the legs and dividing the other leg into equal parts.

This leaves us with a collection of rectangles that most likely have different dimensions. So we dissect them into new rectangles that all have all height 1, using the example at the beginning. 

Then, the new rectangles can be lined up edge to edge along their sides of length 1 to form one very wide rectangle that finally can be dissected into a square.

Transdiss

As this was nice and easy, here a challenge: In our dissections, we were allowed to translate and rotate the pieces arbitrarily. What about if we forbid rotations? Can you dissect an equilateral triangle into finitely many pieces and translate them so that the result is the same triangle upside down? Or, can you cut a square, translate the pieces, and thereby achieve a 45 degree rotation of the square? 

 

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.

Badmoves

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.

Icosidodecahedron

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.

Compound

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.

StellaDodecaIcosa

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:

Cubes

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

Insanenets

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).

Singlenets

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?

InstantInsanity

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.

Solution

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.