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.