Through Mazes

to Mathematics

Level sequences of simple, alternating transit mazes.

(This page has been translated into Polish, Czech, Indonesian, Russian, Estonian, German, Dutch, Hungarian, Georgian, Thai, Kakakh, Urdu, Finnish, Lithuanian and Spanish).

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