6 • • • • • • • • • • • • • • • • • • • • • • • • •
Doodling into a Labyrinth
IN THIS CHAPTER, we begin with doodling as inspired by [8] and, by the end, use a math theorem to create a maze.
Doodling in Math Class
We begin with doodling. Place a pencil on a piece of paper and maybe even close your eyes. Create your doodle by drawing in big sweeping motions, keeping the pencil on the paper at all times. Remember that the longer you doodle the harder the exercise will be. On the left in Figure 6.1 is my doodle.
Let the math begin by placing a dot at every crossing point in your doodle. Also place a dot at both endpoints in your drawing, unless somehow you started and ended at the same spot. Count each dot and write that number on your doodle. In Figure 6.1 on the right, you can see the 11 dots for my doodle.
Next, count the enclosed areas of the doodle. Write this number on your paper. On the left in Figure 6.2 I found 9 in my doodle. Notice that the entire outside area of the piece of paper is counted as a space, which makes a total of 10. This will be important in a moment. Finally, count each segment between two dots. Write this number on your paper. My doodle has 19, which I label in Figure 6.2 on the right.
Figure 6.2. Counting enclosed areas and segments between dots in my doodle.
Add the number of dots and enclosed areas and subtract the number of segments. This gives you a number and you should have the same as me—the number 2. If you didn’t, try counting again and check your addition and subtraction. Why would this happen? First, the dots are often called vertices, the enclosed areas are called faces, and the segments are called edges. If we denote these V, F, and E, respectively, then we will see the formula that Leonhard Euler proved
Leonhard Euler was a famous mathematician who lived during the 1700s. He wrote hundreds and hundreds of pages on his mathematical discoveries. Among Euler’s many works, he introduced the concept of a function and was the first to write f (x) to denote the function f applied to the argument x. He also introduced the modern notation for e which is the base of the natural logarithm and the letter i to denote the imaginary unit.
This property is called the Euler Characteristic. Euler’s proof shows this property will hold for infinitely many doodles. Such is the power and generality of mathematical theory. Try a bunch of doodles and you will see that you get the answer 2 every time.
A Touching Puzzle
Let’s change gears and consider a puzzle that appears in [13]. The game is played by rearranging the order of the blocks numbered 0 through 9 seen in Figure 6.3 (a). Each block is assigned a score equaling the product of that block’s value and the number of squares it touches with neighboring blocks. The score for a particular arrangement is the sum of the scores for all the blocks.
Let’s compute the score of the initial arrangement in Figure 6.3 (a).
Figure 6.3. Two arrangement for the Touching Numbers Puzzle.
The block for the number zero touches 2 squares on the neighboring block. So the number zero block receives a score of 0(2) = 0. The number one block touches 2 squares on its left and 1 square on its right, giving it a score of 1(2 + 1) = 3. The number two block touches 4 squares of its neighboring blocks so its score is 2(4) = 8. Continuing this for every number and summing up every block’s score, we get
which is the score of this initial arrangement.
Let’s try another arrangement as given in Figure 6.3 (b). The number one block touches one square on its neighboring block; so it’s score is 1(1) = 1. The number three block touches 1 neighboring square on its left and 4 neighboring squares on its right. So, this block’s score is 3(1 + 4) = 15. The number five block’s score is 5(4 + 1) = 25. Continuing in this way leads to this arrangement’s score, which equals
We produced a higher score with this new arrangement, which leads to the challenge.
Challenge 6.1. What arrangement produces the largest possible score? The smallest?
This puzzle can be represented by a graph as seen in Figure 6.4, which, for simplicity, looks only at the blocks for the numbers 0, 1, and 2. We connect the number blocks with arrows or directed edges that have costs associated with them. The cost of an edge from i to j is the number of squares that touch if i is placed to the left of j. If you place the number one block to the left of the number two block, 1 square would touch. The corresponding edge in Figure 6.4 has a cost of 1.
This formulation falls in the field of graph theory. Solving the puzzle corresponds to finding a path that visits every number block exactly once, where the sum of the weights of the traversed edges is as small as possible.
This puzzle, and in particular viewing it from this formulation, leads us to a game from the nineteenth century.
A Trip of a Puzzle
Let’s play a game posed by Sir William Hamilton during the 1800s. For an octahedron as pictured in Figure 6.5 (a), find a path along the edges that visits every corner exactly once, except the origin node that is visited “first” and “last.” After this, find such a path on the dodecahedron pictured in Figure 6.5 (b).
Sometimes, rather than visualizing such surfaces in 3D, it is easier to create what is known as a Schlegel graph of the solid. Figure 6.6 (a) depicts a Schlegel graph for a cube. Note how this corresponds to almost looking down into the cube from above.
We see Schelgel graphs of an octahedron and dodecahedron in Figure 6.6 (b) and (c), respectively. Our puzzle remains the same but can now be posed in 2D. We again search for a path along the edges of the graph that visits every vertex exactly once, except the origin node that is visited “first” and “last.” Such a path is called a circuit.
Figure 6.6. Schlegel graphs for a cube (a), an octahedron (b) and adodecahedron (c).
Sir Hamilton’s puzzle, seen in Figure 6.7, was called an Icosian Puzzle. The pattern on the board is a Schlegel graph of a dodecahedron. The puzzle is the same that we just played.
If we put a weight on each edge and now search for a circuit with minimal sum of its edges, we have posed the Traveling Salesman Problem (TSP). It is called a TSP as the vertices of the graph can be regarded as cities and the weights as distances. The solution shows a salesperson the shortest route that visits all the cities and starts and ends at home.
Solving the TSP on even a moderately sized problem, such as 20 cities, is a problem that is well-known to be difficult. In 1962, Proctor and Gamble ran a contest that required solving a TSP on a specified 33 cities. An early TSP researcher, Professor Gerald Thompson of Carnegie Mellon University, was one of the winners. You can see the contest announcement in Figure 6.8 (a).
Figure 6.7. Icosian puzzle.
Figure 6.8. The TSP has an active history. Proctor and Gamble contest announcement (a) from 1962 and (b) contains the optimal tour found in 1998 of the 13,509 cities in the United States with populations greater than 500.
By 1987, the state of the art for finding TSP solutions had progressed considerably with Groetschel and Holland finding the optimal tour of 666 interesting places in the world. Just over 10 years later in 1998, Applegate, Bixby, Chvátal, and Cook found the optimal tour of the 13,509 cities in the United States with populations greater than 500. If you want to take such a tour, the route can be seen in Figure 6.8 (b). For more information on solving TSPs and the history of tackling such an important and difficult problem, see [14].
Figure 6.9. A stippling (a) that serves as the cities for a TSP creating the route in (b).
We are now positioned to create some mathematical art.
A Maze of Math
Let’s still create a route for a traveling salesperson but now the location of the cities is created from a stippling as seen in Figure 6.9 (a). If we start at a point and always follow a line segment from one point to another, what’s the shortest path that visits all of the dots before returning to the starting point? The route is seen in Figure 6.9 (b). Such visual art, called TSP Art, was developed by Robert Bosch, Adrianne Herman and Craig Kaplan. [5, 6] In a moment we’ll create mazes from such paths. First, try the maze in Figure 6.10.
Did you find the route from the start to the finish? If you did, you know something that I didn’t when I made the maze. Still, I did know such a solution existed. How did I create this maze without knowing the solution? The Euler Characteristic from earlier in this chapter aided me.
The TSP Art image of Bart in Figure 6.11 (a) is constructed from line segments that form one continuous line. In other words, it could be created with one loop of string and nails placed as the endpoints of the line segments. The image has 5,000 vertices. There is one edge for every vertex so there are 5,000 edges, too. Recall the Euler Characteristic, which states
Figure 6.10. A maze of Bart.
we know for Bart’s image that:
Figure 6.12. See the love!
Since F = 2, there are only 2 enclosed regions in this image. Look at Figure 6.11 (b) in which one region is filled with red.
So, how did I create the maze? I placed the start at some point along the boundary of the red region and the end somewhere else along the boundary of that region. As such, I know there is some path from the start to the finish. What path? I don’t know, but I have proven it exists. Though I created the maze and know the solution exists, the exact solution may continue to remain a mystery to me.
Figure 6.13. TSP maze originating from a photograph.
Challenge 6.2. Find a start and end for a maze using the TSP Art in Figure 6.12. Remember, one region will be connected to the area outside the picture. The start and end should be placed along the boundary of the other region.
Got time? Solve the maze in Figure 6.13, which originates from a photograph.