Category: Mathematics

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.

Reflections on the Letters r,s,t (Groups II)

Continuing the discussion from last week, let’s consider the 3-letter alphabet {r,s,t}. We are allowed to form all possible words in these letters (and their inverses, if you want to), but we agree that rr=ss=tt=1 and (rs)^2=(st)^3=(tr)^6=1. This defines the Coxeter group G(2,3,6). Last time we saw that the very similar group G(2,3,3) is finite, today we will see that G(2,3,6) is infinite. Below is the beginning of its Cayley graph.

Cayley236 01

We travel from one word to the next by appending r,s, or t. This looks much more complicated than what we saw for G(2,3,3), but things become clearer when we look at another group. Consider a yellow triangle with 30, 60, 90 degree angles (writing this as π/2, π/3,π/6 makes 2-3-6 reappear), and let ρ, σ, τ be the reflections at the lines extending its edges.

Reflectiongroup 01

These three reflections generate a group Γ(2,3,6) of Euclidean symmetries which has the yellow triangle as its fundamental domain. The clue is that Γ(2,3,6) = G(2,3,6). We can easily map G(2,3,6) to Γ(2,3,6) by sending R to ρ, s to &sigma, t to τ. This works because ρ, σ, τ satisfy the same relations as r, s, t. It doesn’t work as easily the other way because ρ, σ, &tau could also satisfy other, hidden relations.

Reflpath 01

Let’s look at the word tsrtst. Reading it from left to right gives us a path on the Cayley graph from the initial triangle to a target triangle. Translating from Latin tsrtst to Greek τσρτστ gives a composition of reflections that takes the initial triangle to the same target triangle. This is not completely trivial, you prove it by induction. Remember that the composition is applied from the right to the left, so we also change reading direction.

This observation can be used to show that the translation map G(2,3,6) to Γ(2,3,6) is injective. If a word in G is the identity in $γ, its path in the Cayley graph must be a closed loop. As the Euclidean plane where the tiling lives is simply connected, we can homotope it to a constant path, using elementary operations: Backtracking an edge, or shrinking a loop around a vertex to a point. The former is the accomplished using the relations rr=ss=tt=1, the latter using the other relations. This shows that the geometric homotopy can be realized using the relations of the group, and thus we can reduce the word to the trivial word 1.

Cayley
This is essentially the proof of a famous theorem by Walther Franz Anton von Dyck: The group G(a,b,c) is finite if and only if 1/a+1/b+1/c>1. We have seen the relevant examples in the case
1/a+1/b+1/c>1 and 1/a+1/b+1/c=1. If 1/a+1/b+1/c <1, we need hyoperbolic geometry. Above is a picture of the Cayley graph of G(2,3,7) within the tiling of the hyperbolic plane by (π/2,π/3,π/7)-triangles.

Do and Undo (Groups I)

Groups are mathematical games being played with letters. In the simplest version, we use just one letter (say a), and are allowed to add it to or to remove it from a word. This is the free group of one generator, or the infinite cyclic group.

Cyclic 1 01

Clearly, this game of create and destroy needs more rules. A simple rule is to make it truly cyclic and finite by insisting that after using the letter a say 7 times, we are back where we started. This means aaaaaaa=1, which is a relief, but still not very interesting.

Cyclic 2 01

With two letters a and b, our game expands.

Free2

This Cayley graph is the dual graph of the tiling of the hyperbolic plane by ideal squares, and not accidentally so.

Again we can restrict the rules of the game. Let’s play with the three letters r, s, and t, and insist that rr=ss=tt=1 to avoid any repetitions, and also that rsrs=ststst=trtrtr=1. The result is the Coxeter group G(2,3,3), and after a while playing around with the words, you find its Cayley graph below, neatly laid out.

Dyck233

This is dual to a tiling of the sphere by spherical triangles with angles π/2,π/3,π/3, and this is also not accidentally so.
We’ll see more about this next week.

Cox233

Always or Never

Pentaponce

Take two ellipses, one within the other. Take a point on the outer ellipse, and draw one of the two tangents to the inner ellipse, and find its second intersection with the outer ellipse. Use this point to start the process again, and again. You will get a polygonal path in the ellipse that will most likely not close up. But in case you are lucky, something miraculous happens: If you pick any other point and repeat the game, the polygon will again close up.

This is the content of a famous theorem by Jean-Victor Poncelet.

Steiner 01

In spirit, it is similar to a theorem of Jakob Steiner that asserts that a chain of circles in an annulus bounded by two circles either always or never closes up. While Steiner’s theorem follows immediately by inverting the circles into a pair of concentric circles, such a simple proof is not available for Poncelet’s theorem. Until recently, all proofs I know of were, let’s say, advanced.

At the core of a new proof by Lorenz Halbeisen and Norbert Hungerbühler are some fundamental theorems from projective geometry.

Let’s first recall that five points, no three collinear, determine a unique conic.

Conic4points

This is because through four points, you can find two different degenerate conics consisting each of a pair of lines, and by forming linear combinations, accommodate a fifth point. Below we will need the dual theorem: Given five lines, no three concurrent, there is a unique conic tangent to them.

Pascal Hyperbola 01

Pascal’s theorem is a condition for six points to lie on a conic: They do if and only if opposite sides intersect in collinear points. Above you see this for six points on the two branches of a hyperbola.

Brianchon 01
Dual to this is Brianchon’s theorem (illustrated above): The sides of a hexagons are tangent to a conic if and only of its diagonals are concurrent.

Ponce1

As an application, Halbeisen and Hungerbühler show: If the six vertices of two triangles a1,a2,a3 and b1,b2,b3 lie on a conic, than there is a conic tangent to the six sides of the triangles. The proof is easy: Applying Pascal to the hexagon a1,b2,a3,b1,a2,b3 gives us three collinear points c12,c13,c23.

Ponce2

Then applying Brianchon to the hexagon a1,c12,b1,b3,c23,a3 shows that it is tangent to a conic. But the sides of this hexagon are the same as the sides of the two triangles, so we are done

Ponce3

From here, we obtain Poncelet’s theorem for triangles: Suppose you have two ellipses inside each other, and a triangle whose vertices lie on the outer ellipse and whose sides are tangent to the inner. Take another point on the outer ellipse, and form a second triangle by drawing the tangents to the inner ellipse. We have to show that the third side of the triangle is also tangent to the inner ellipse.

By the theorem by Halbeisen and Hungerbühler, the two triangles have an inscribed common ellipse. The given inner ellipse touches five of the same six lines by construction. But a conic is uniquely determined by five tangent lines.

The general case follows of n-gons the same idea, but requires more bookkeeping.

Odd Angles

For a while, this will be my last post about conformal spiderwebs. Today, we will still look at circular quadrilaterals that are conformal images of squares, but allow the angles to be multiples of 90 degrees. Like so:

2quarter a 01

Let’s call this a square of type (1,1,3,3). Multiply the numbers by 90 and you get the angles at the vertices. I have again employed Möbius to place three corners at (1,0), (0,1), and (-1,0). The fourth vertex is again moving cautiously along the unit circle. Below is a square of type (1,3,3,3), and here the fourth vertex is on the x-axis, the second possible case we noticed for right angled circular quadrilaterals.

Mixed31b 0

Similarly, here is a square of type (1,1,1,3), also with the fourth vertex on the x-axis.

1quarter a 01

Missing are squares of type (1,3,1,3). While there are quadrilaterals of this type, all conformally correct squares I could find were only immersed (i.e. overlapping).

Then one can also have squares of type (2,2,2,2), for instance. The circle would be an example, with artificial vertices at (1,0),(0,1),(-1,0) and (0,-1), but there are also bean shaped squares like the one below.

Bean0

Finally, the square with zero angles, in its most regular form.

Zero 4 01

More Spiderwebs: Conformal Squares with Circular Edges

The Schwarzian derivative of a map f(z) from the upper half plane to a right angled circular quadrilateral that sends the points -1, 0, 1 and infinity to the vertices of the quadrilateral (and thus making it conformally a square) is given by the expression

Schwarzian

From it, one can find this map by taking the quotient of two solutions of the linear ordinary differential equation u”(z) + 2 Sf(z) u(z)=0. This is one step more complicated that the hypergeometric differential equation needed for triangles.

The parameter “a” is the accessory parameter. We have seen last week that there is a two-parameter family of right angled circular quadrilaterals, and the parameter a singles out the 1-dimensional subfamily of those quadrilaterals that are conformally squares.

Square 0

In these images I have used a Möbius transformation to move three of the vertices to the points (1,0), (0,1) and (-1,0). The fourth vertex is then somewhere on the lower unit circle.

Square 1

This is somewhat remarkable: First, it shows that we can find a conformal square for any such choice of four points (the first three normalized, the fourth on the half-circle). Secondly, it appears that the second family of right circular quadrilaterals we found last week where the fourth corner would move on line through (-1,0) and (1,0) does not contain any conformal squares. Thirdly, remember again from last week that for any such choice of four vertices, there is a 1-parameter family of right circular quadrilaterals with these points as vertices, but only one of them is conformally a square.

Square 0 5

Of course one can also play with the angles. As a teaser for what’s to come next week, below is an anti-square.

3quarter b

Not Being Square

I meant to post today a sequel to the circular triangles from last week, but I got carried away looking at right angled quadrilaterals bounded by circular arcs. Like the pillows, but more general. Like so:

Circulon 2

The question arises for what choices of four points we can find a right angled quadrilaterals bounded by circular arcs?

By the way, how do we call these? I thought about circulons (taken) and horny squares (oops). For now, I call them circulions (like centurions), to avoid a lawsuit about trade marks. Above you see a solution that is not a square but where the vertices are at the corners of a square. There are more like these, in fact a 1-parameter family.

Circulon 1

Below you can see the entire family at once, you just have to follow all dots with the same color.

Squaregradient

Can we do that for any choice of four points? Not so, but: Möbius allows us to move three points anywhere we like (and he will send circulions to circulions), so we can ask: where are we allowed to place a fourth point so that there is a circulion through all of them?

Möbius also tells us that this is easy if we place all four points on a circle (by sending that circle to a line, and then connecting the four points on the line alternatingly by segments of the real line and half circles, for instance). Here is an example where the first three points are at the corners of an equilateral triangle, and the fourth point is on the circle through them.

Circulon 3

Again, there is a 1-parameter family of such circulions through these points.

Trianglegradient

Pretty, isn’t it?

Now, surprisingly to me, for each choice of three points, there is a second circle on which the fourth point can reside: Take the circle that contains the given three points, and construct the circle orthogonal through it that passes through the two points between which we want to put the fourth vertex. You can put the fourth point anywhere on that new circle. Here is an example, with the first three points again at the corners of an equilateral triangle.

Circulon 4

Below is again an entire family, color coded and adorned with moiré.

Trianglegradientb

Next week you’ll see conformally correct squares. Promised.

Safely Footed Spiderwebs

… et je continue encore de fouler le parvis sacré de votre temple solennel…

Tri10 01

Let’s talk again a little about triangles. The last time I wrote about triangles is not quite a year ago, and it didn’t help.

Tri90 01

What you see in this post are all triangle that have their vertices at the same place, the third roots of unity, to be precise. They are, however, not Euclidean triangles with straight edges, but curved ones, with circular edges.

Tri240b 01

The first three are equiangular still, making angles of 10, 90 and 240 degrees at the corners, respectively. The spiderwebs are conformal images of polar coordinates on the disk, thus illustrating the Schwarz-Christoffel formula for circular polygons. The bat down below is a neat optical illusion, too: Would you think that the vertices are at the corners of an equilateral triangle?

Tri 1 1 3 01

The theory behind this is based on Schwarzian derivatives and the Schwarz reflection principle, so clearly Hermann Amandus Schwarz owns all this.
It is also intimately connected to hypergeometric functions and much more recent mathematics.

Bird 01

And there is some mystery, still. While circular triangles are safe (they are determined by their angles, up to a Möbius transformation, and the Schwarz-Christoffel formula will deliver), quadrilaterals are not. Even Euclidean straight & right quadrilaterals can be differently shaped rectangles, and things get worse with circular ones. In this case, the Schwarz-Christoffel formula will have some extra parameters, the so-called accessory parameters. Changing the will not change the conformal nature of the quadrilateral nor its angles, but its “bulge”. More about this later.

The Desargues Configuration – A Quick Tour

Configurations are a wonderful way to confront the Euclideanly prejudiced with the abstraction of incidence geometries. Take for instance the Desargues configuration. Its ten points are given by the 10 different subsets with two elements of the set {1,2,3,4,5}. Here they are:

{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}

Its ten lines are given similarly by the 10 different subsets with three elements of the set {1,2,3,4,5}. Here they are, likewise:

{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}

Then we say that a point is incident with a line if is a subset of the line. For instance, the point {1,2} is incident with the three lines {1,2,3}, {1,2,4}, and {1,2,5}. Clearly, every point us incident with exactly three lines. Likewise, every line is incident with precisely 3 point: For instance, {1,2,3} is incident with {1,2},{1,3}, and {2,3}. This makes the Desargue configuration a configuration of type (10,3).

Desargues5a

Above is a nice geometric interpretation of this. Take five planes in space so that no two of them are parallel and no three intersect in a single line. Then these planes will intersect in the 10 lines and 10 planes of the Desargues configuration. Unfortunately, there is no way I can think of to place five planes into space so that this will look pretty, the reason being that the “faces” of this configuration are nonconvex quadrilaterals. But one can do differently. Still using space, consider a tetrahedron. Take as points the four vertices of the tetrahedron as well as the 6 midpoints of the edges. Lines are the six edges of the tetrahedron and the incircles of the triangles. That requires bending our understanding of lines a little, but now this configuration becomes easy to visualize.

Desargue tetra

Where have the five planes gone? You could say that four of them have become the faces of the tetrahedron, and the fifth a wisely chosen sphere. The right image shows in a top view how to label the points and lines. If this is still too concrete, you can also use the following 2-dimensional drawing.

Desargues

This is illustrating Desargue’s Theorem: Take two triangles p1, p2, p3 and q1, q2, q3 which are in perspective, i.e. have the three lines lines p(i)q(i) pass through a common point p. Now consider the intersection r12 of the two lines p1q1 and p2q2, and likewise the intersections r13 and r23. Desargue tells us that these three points lie on a common line. This sounds complicated, but given that we are only using the most elementary notion from geometry, namely incidence, it is surprising enough that there are non-trivial theorems at all. Why is this true? A miracle? Let’s move back into space and pretend for a second that the two triangles lie in different planes.

Desargues space

Then these planes meet in a line, which is the one through r12, r13, r23, because these points are intersections of lines that belong to one of the two planes each. So, in space Desargue was evidently right. Can things go wrong in the plane? Yes and no. No, because a Euclidean plane can always be though of as a plane in space, and we can understand any planar Desarguesian construction of the projection of a similar configuration from space. No, because there are in fact “planes” that do not lie in any space and where Desargues’ theorem is false.

Hyperbolic Inversion (Inversion II)

The first time I taught hyperbolic geometry, I thought I could be done in a week. I also thought that it would help to do spherical and hyperbolic geometry side by side. To save time, I did it not side by side, but simultaneously, using the quadratic forms
Quadform
For negative ε, the spheres become hyperboloids, but the formula for inversion I(x) = x/ x ‧ x still works, with all its suitably formulated properties. Hence one can use the stereographic projection both for spheres and the hyperboloid in Lorentz space to get all the models with its simultaneously.

Needless to say, this was a complete disaster. Let’s just study the 2-dimensional hyperbolic inversion. Circles in this geometry are the level sets of the quadratic form above, which are hyperbolas. Below you see concentric hyperbolas with growing radius. For each radius, you get two branches. The squared radius can be 0, in which case you get the two diagonals, and even negative, so that the hyperbolas open upward and downward.

Concentric 01

These and their translates are the only hyperbolas we will consider, others belong to other quadratic forms. Let’s begin simple and invert a family of parallel horizontal lines at the blue hyperbola. Their images are hyperbolas with one branch intersecting the mirror hyperbola in the same points as the lines, and all touching at the origin.

Horizontal 01

In fact, all lines are mapped to hyperbolas. Below are to families of line segments and their image hyperbolas.

Stars 01

If you want to check this with a computation: A line through (a,b) making angle φ with the x-axis is mapped to a hyperbola with “center” p and squared radius

Linetohyperbola

Then, certain hyperbolas (namely level sets of our quadratic form) are mapped to hyperbolas. Below, the purplish hyperbolas are concentric, and their greenish images pass through the same pair points. (Where do these intersections come from – – -?).

Hyperbolicinv 01

In formulas: A hyperbola with center (a,b) and radius r is mapped to another hyperbola with

Hyp2hyp

Are circles mapped to circles?

Invcircles 01

Evidently not. Euclid isn’t here anymore, circles are not round, and we better don’t mention the rest.