## A-maze-ing donuts

Here is a treat that the confectioners at your local bakery never dreamed of -- a donut made of a math maze. Although it may not satisfy anybody's sweet tooth, it does serve up a satisfying array of properties and puzzles to many mathematicians, including Indiana University Professor of Mathematics Russ Lyons.

The donut is actually made from a two-dimensional maze, such as the one with the solution depicted below in red. Mazes such as this one have two important properties. One, it is possible to reach every single point in the maze from any other point. Two, if you pick any two points, there is exactly one unique path that connects the two without backtracking. Together, these characteristics make what mathematicians call a "spanning tree."

Don't believe it? Then take a moment (maybe two) to try each of the 10^800 (one followed by 800 zeros) possible combinations. Or just take Lyons' word for it.

"There are a huge number of these mazes that can be made, and a very simple algorithm can create each maze," said Lyons. "I wish I had the time to solve each one."

According to Lyons, although there is a fuzzy, practical significance to this area of mathematics in chemistry (polymers) and physics (two-dimensional quantum gravity), the math behind the donut is studied mostly out of sheer human curiosity.

And it is that curiosity that leads him one step further into the maze, where there are several more interesting properties.

Of all the mazes that can be created, the shortest possible solution is one that travels in two straight lines: one along the left side and one along the bottom. The longest possible solution is one in which the red line visits every single place in the grid.

If the maze is made in a 10-by-10 grid, the shortest solution is 20 lines long (10-by-2) and the longest is 100 (10-by-10). But odds against randomly creating either of these mazes exceed imagination. So if left to chance, about how long will the solution to the maze be? Recent mathematical proofs have shown that for very large mazes, the average solution will be about 1.9 x n^1.25, where "n" is how long each side of the grid is. So for a 10-by-10 grid like the one shown above, "n" is 10, and the average solution is 34 lines long.

Recently, Lyons took the problem another step further. He connected the top and bottom of the maze to make a cylinder (like the one seen below), and then connected the ends to make a donut. When this is done, the previously mentioned characteristics disappear. But others take their place.

Now, instead of one unique path connecting any two points, there is a unique set of edges that traverse the donut in any direction. That is, once on the purple path shown, one can go around and around the donut as many times as one wants without backtracking. The maze below shows this set of lines on a two-dimensional grid. However, if the path is blocked, and if one is not allowed to go once around the donut via this path, it again becomes a spanning tree, meaning there is only one way to get from point A to point B.

In a randomly generated donut, how many edges will likely be included in the purple path that spans the donut? Nobody is quite sure, but Lyons has reason to believe it is again 1.9 x n^1.25. This is just one characteristic of this problem that is currently being explored.

"There have been plenty of important, historical discoveries that were discovered by basic research out of intellectual curiosity, and not practical concerns," said Lyons. "And besides, it's fun."