Skip to content

Instantly share code, notes, and snippets.

@chrismilson
Last active June 12, 2020 08:24
Show Gist options
  • Save chrismilson/5e38d83679bcb35c09cb497c58e8bbae to your computer and use it in GitHub Desktop.
Save chrismilson/5e38d83679bcb35c09cb497c58e8bbae to your computer and use it in GitHub Desktop.
Folding Puzzle

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment