chrismilson/PAPER_FOLDING.md

## PAPER_FOLDING.md

      
    Raw
  

              PAPER_FOLDING.md
            
          
    This puzzle is part of the Matt Parker's Maths
Puzzles series.
Paper Folding

Given a piece of paper with eight marked out regions:
 _______________
|   |   |   |   |
| A | D | E | H |
|___|___|___|___|
|   |   |   |   |
| B | C | F | G |
|___|___|___|___|

How many different possible orderings of the letters are there?
Clarification: An ordering of the letters is obtained by folding the paper
along the boundaries between regions such that all the regions form a stack. For
example, the paper could be folded along the long edge and then the short edges
to form the following stack when viewed from above:
        ________
 |  |  |   __   |  |  |
A| B| C|  |  | F| G| H|
 |  |__| D| E|  |__|  |
 |________|  |________|

This generates the order ABCDEFGH from the piece of paper.
Insights

Initially one may ask if all permutations are possible. There are a lot of
permutations to check (8! = 40320), and that would take a long time, especially
if we don't know how to prove that a given order is impossible.
Instead of steaming ahead with the problem, we may simplify the problem first.
What if instead of 8 regions, there were only 4.
 _______
|   |   |
| A | D |
|___|___|
|   |   |
| B | C |
|___|___|

What can we do? There are two ways to do the first fold:

Forward; and,
__A__.__D__

__B__.__C__


Backward.
__B__.__C__

__A__.__D__


There are four folds from each of these positions:

  
    Up
    Down
    In
    Out
  
  
    Forward
    
      ___C___
       |
__D__  |
     | |
__A__| |
       |
___B___|
      
    
      ___A___
       |
__B__  |
     | |
__C__| |
       |
___D___|
      
    
      __A__
     |
__D__|
__C__
     |
__B__|
      
    
      __D__
     |
__A__|
__B__
     |
__C__|
      
    
    Back
    
      ___D___
       |
__C__  |
     | |
__B__| |
       |
___A___|
      
    
      ___B___
       |
__A__  |
     | |
__D__| |
       |
___C___|
      
    
      __B__
     |
__C__|
__D__
     |
__A__|
      
    
      __C__
     |
__B__|
__A__
     |
__D__|
      
    
These, by exhaustion these must be all of the valid orders on four regions:

CDAB
DCBA
ADCB
BCDA
ABCD
BADC
DABC
CBAD


I then had some insights about larger cases (pieces of paper with 2 x n regions)
The paper with eight regions is just three of these four region pieces of paper
that are joined together.
Since the A must be at the front, the horizontal fold must be forward, and the
first group of 4, ABCD can only be folded down or in, as the out and up folds
would put characters in front of the A. The Other groupd of 4 however, CDEF
and EFGH are free to do any of the up down in or out moves giving them four
configurations each, that do not interfere with each other. Thus there should be
4 x 4 x 2 = 32 different orders with A at the front.


ABCD Move
CDEF Move
EFGH Move
Order


Up
Up
Up
ABEFGHCD


Up
Up
Down
ABGHEFCD


Up
Up
In
ABEHGFCD


Up
Up
Out
ABHEFGCD


Up
Down
Up
ABCDEFGH


Up
Down
Down
ABCDGHEF


Up
Down
In
ABCDEHGF


Up
Down
Out
ABCDHEFG


Up
In
Up
ABCFEHGD


Up
In
Down
ABCHGFED


Up
In
In
ABCGFEHD


Up
In
Out
ABCFGHED


Up
Out
Up
INVALID


Up
Out
Down
INVALID


Up
Out
In
ABGFCDEH


Up
Out
Out
ABFGCDHE


In
Up
Up
AFEHGDCB


In
Up
Down
AHGFEDCB


In
Up
In
AFHGEDCB


In
Up
Out
AGFEHDCB


In
Down
Up
ADCFEHGB


In
Down
Down
ADCHGFEB


In
Down
In
ADCGFEHB


In
Down
Out
ADCFGHEB


In
In
Up
INVALID


In
In
Down
INVALID


In
In
In
AEHDCGFB


In
In
Out
AHEDCFGB


In
Out
Up
ADEFGHCB


In
Out
Down
ADGHEFCB


In
Out
In
ADEHGFCB


In
Out
Out
ADHEFGCB


I was wrong in my prediction of 32, there are four impossible configurations,
giving us a total of 28 different possible configurations. This was a difficult
problem and I couldn't think of any elegant way to gain intuition through code.
After playing with the paper more, I found five new configurations:

AEFBCGHD
AEFGHBCD
AGHEFBCD
AEHGFBCD
AHEFGBCD

These configurations are not from any up, down, in, or out moves. They are
obtained by threading the paper into itself as shown:
 _______A______
|
|  ______E_____
| |            |
| |  ____F___  |
| | |        | |
| | |  __B__ | |
| | | |      | |
| | | |___C__| |
| | |          |
| | |____G___  |
| |            |
| |_____H____  |
|              |
|_______D______|

I then found another configuration: ADHGCBFE. This was when I got a new idea.
Perhaps I should forget about the horizontal fold altogether and focus on the
verticies from above; the full stops from the forward and back folds on four
regions. After thinking about this, I thought of even more possible
configurations:

ADEFCBGH
ADCBHGFE
ADHGCBFE
ADCBGFEH
ADCBFGHE
ADCBFEHG

I then thought about something that must always be true about valid
configurations:
Vertical Pairs

Consider the vertical pairs AB, CD, EF, and GH. Let ab be a pair and
cd be another pair arbitrarily, then if c is between a and b in a
configuration, then d must also be between a and b.
Filtering out the permutations of four that satisfy this property for pairs AB
and CD
`ABCD` Move	`CDEF` Move	`EFGH` Move	Order
Up	Up	Up	`ABEFGHCD`
Up	Up	Down	`ABGHEFCD`
Up	Up	In	`ABEHGFCD`
Up	Up	Out	`ABHEFGCD`
Up	Down	Up	`ABCDEFGH`
Up	Down	Down	`ABCDGHEF`
Up	Down	In	`ABCDEHGF`
Up	Down	Out	`ABCDHEFG`
Up	In	Up	`ABCFEHGD`
Up	In	Down	`ABCHGFED`
Up	In	In	`ABCGFEHD`
Up	In	Out	`ABCFGHED`
Up	Out	Up	INVALID
Up	Out	Down	INVALID
Up	Out	In	`ABGFCDEH`
Up	Out	Out	`ABFGCDHE`
In	Up	Up	`AFEHGDCB`
In	Up	Down	`AHGFEDCB`
In	Up	In	`AFHGEDCB`
In	Up	Out	`AGFEHDCB`
In	Down	Up	`ADCFEHGB`
In	Down	Down	`ADCHGFEB`
In	Down	In	`ADCGFEHB`
In	Down	Out	`ADCFGHEB`
In	In	Up	INVALID
In	In	Down	INVALID
In	In	In	`AEHDCGFB`
In	In	Out	`AHEDCFGB`
In	Out	Up	`ADEFGHCB`
In	Out	Down	`ADGHEFCB`
In	Out	In	`ADEHGFCB`
In	Out	Out	`ADHEFGCB`