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.


Solutions were received from Al Zimmermann, Kirk Bresniker, Rob van der Nier, Nosaiba Yousef, Claudio Baiocchi.  Kirk Bresniker's summary:
For my first fold I have 4 choices: 
    horizontal or vertical * to the front or to the back.
For my second fold I have 2 choices: to the front or to the back.
4 * 2 = 8 combinations.

For solutions including 1, folding vertical fixes the relationship of 1 and 7,
it's either 1 7 or 7 1 in the sequence.  The folding fron or back either appends
or prepends the sequence 6 4 or 4 6, so the results are:

4 6 1 7
1 7 4 6
6 4 7 1
7 1 6 4

Folding hortizontal swaps 6 and 7:

4 7 6 1
1 6 4 7
7 4 6 1
6 1 7 4
--------------------
Update 8/16/04:
3x3 ->

For my first fold I have 8 choices:
2 horizontal + 2 vertical * to the front or to the back

For my second fold I have 6 choices:
1 H + 2V or 2H + 1 V * to the front or to the back,
                       depending on my first fold

For my third fold I have 4 choices:
1H + 1V or 2 H or 2 V * to the front or to the back,
                        depending on my second fold

For my fourth (and last fold) have have 2 choices:
1H or 1 V * to the front or to the back, depending on my third fold

8 * 6 * 4 * 2 = 384 ways to fold.
-----------------------
4x4 ->
This is more interesting because there are either four, five,
or six folds to make depending on if you choose a succession of
folds in the same direction and 'fold away' a gridline.

For example if you number the grids H1, H2, H3, and V1, V2, V3
left to right and top to bottom:

4 fold: H2 V2 H1 V1
5 fold: H1 V2 H2 V1 H3
6 fold: H1 V2 H2 V2 H3 V3

I imagine that further dimensions will be complicated in this way.

I guess the way to think about it is recursively. For the 4x4
there are four lines to fold front or back and end up with a 3x4.
There are two lines to fold front or back and end up with a 2x4, etc.
So ...

Start: 4x4
  A: 4*2 -> 3x4
  B: 2*2 -> 2x4
A: 3x4
  C: 2*2 -> 3x3
  D: 1*2 -> 2x3
  B: 2*2 -> 2x4
B: 2x4
  F: 2*2 -> 2X3
  G: 1*2 -> 2X2
  H: 1*2 -> 1X4
H: 1x4
  I: 1*2 -> 1x2
  J: 2*2 -> 1x3
C: 3x3
  D: 4*2 -> 2x3
D: 2x3
  G: 2*2 -> 2x2
  J: 1*2 -> 1x3
J: 1x3
  N: 2*2 -> 1x2
G: 2x2
  I: 2*2 -> 1x2
I: 1x2
  P: 1*2 -> 1x1

To find them all, follow all the trees and sum

A C D G I P -> 8 * 4 * 8 * 4 * 4 * 2 = 8192
A C D J I P -> 8 * 4 * 8 * 4 * 2 = 2048
A D G I P -> 8 * 2 * 4 * 4 * 2 = 512
A D J I P -> 8 * 2 * 4 * 4 * 2 = 512
B G I P -> 4 * 4 * 4 * 2 = 128
B H I P -> 4 * 2 * 4 * 2 = 64
B H J I P -> 4 * 2 * 8 * 4 * 2 = 512
= 11968



Mail to Ken