##
Folding a Square

Take a square piece of paper and number each quadrant, 1 in the top-left, 2
in the top-right, 3 in the bottom-left, and 4 in the bottom right. Number
the back of the paper 5-8, 5 behind 4, 6 behind 3, 7 behind 2, and 8 behind 1.
Fold the paper twice, once each horizontally and vertically, to make another
square 1/4 the size of the original. The end result can be identified by
reading the numbers facing up, from the top to the bottom of the square.
How many different configurations can be achieved in this way?

For example, if we fold the 5 to the 6, then the 2 to the 4, we could read
from top to bottom 1-7-4-6. 3-5-2-8 is equivalent, found by simply turning
the stack over. To simplify comparisons, only consider solutions that
include the "1".

Extension 7/23/04: How many ways can you fold a square if the original
piece is a 3x3 grid, 4x4, or NxN? Again, you may only fold along the
gridlines until you have a single square (disregard paper thickness.)

Source: Original.

Solution

Mail to Ken