Through Mazes | to Mathematics |
(This page has been translated into Polish, Czech, Indonesian, Russian, Estonian, German, Italian, Dutch, Hungarian, and Georgian.)
The basic fact which allows the mathematical study of simple, alternating transit mazes is the following. The topology of a simple, alternating transit maze is completely determined by its level sequence. How this works is explained below; it means that if two s.a.t. mazes (say, both in unrolled form) have the same level sequence, then one can be changed to match the other, or the mirror-image of the other, by a continuous, level-preserving deformation.
It follows that a complete topological
classification of simple
alternating transit mazes
amounts to determining which sequences of numbers can
occur as level
sequences, and in fact there are three conditions which
are necessary and sufficient for a permutation of
the numbers from 0 to n to be the level sequence of an s.a.t. maze
of depth n.
1. The sequence must start with 0 and end with n.
2. Odd and even integers must alternate in the
sequence.
3. Consider the pairs of consecutive
numbers in the level sequence that begin with an even number;
these correspond to the vertical segments on
the right side of the maze.
(*)If two of these segments overlap, one
must be nested inside the other.
The same must hold for the
pairs that begin with an odd number; these correspond to
vertical path segments on the left.
Example: in the level sequence for the Constantinople maze, the segments (10,1) and (2,11) overlap, but neither is nested in the other; so this cannot be the level sequence of an s.a.t. maze.
Here is how this is proved.
Necessity of 1: obvious.
Necessity of 2: Suppose two consecutive layers joined by
a vertical segment on the right, say, have the same parity;
the space between them must have
an odd number of levels. Any path which
goes through that space
must enter and exit on the left,
and so can use up only an even number of levels. Contradiction.
Necessity of 3:
Think of the maze in unrolled form, with
entrance, say, on the right. The path begins on the right side at
level 0, and drops to some odd level. Then it crosses to the
left and moves to the next level in the sequence, which will be even,
then crosses back to the right, etc. So the pairs of consecutive
numbers in the level sequence that begin with an even number
correspond to the vertical segments on the right side of the maze,
and those beginning with an odd number, to segments on the left.
Now consider any two of the vertical path segments on the right.
If they overlap, one must be nested inside the other.
Otherwise they could not both be connected to the left hand
side by horizontal segments, since the maze-path cannot intersect
itself; and the same must hold for the
vertical path segments on the left.
Sufficiency: Suppose given a permutation of the integers from 0 to n, satisfying conditions 1, 2 and 3. Here is how to make it into a maze. On a piece of lined paper, number the lines from 0 to n, starting at the top. For each of the consecutive pairs of integers in the sequence that begins with an even number, join the correspondingly numbered lines with a vertical segment on the right hand side of the page. If two of these segments are nested, draw the shorter one to the left of the longer. Now do the same with the odd-beginning pairs, except on the left hand side, with the shorter segments placed to the right. Now on each of the lines numbered 1,...,n-1 there will be two free ends of the figure. Join them along that line; this leaves a free end at the top and at the bottom. You will have drawn the Ariadne's thread of the unrolled form of the s.a.t. maze corresponding to the level sequence you started with. It is now easy to sketch the maze itself. Moreover, just drawing that part of the maze near the right and left hand edges of the page, and joining these two pieces together along their outside spines, produces the nucleus from which the rolled-up form may be drawn.
Return to Main Maze Page
Return to Tony's Home Page