Monday 13 October 2014

The Paper Folding Challenge

The Challenge: 

Take a strip of paper, hold it lengthwise, such that the longer side is horizontal, then fold it in half from left to right. Repeat this several times, each time folding from left to right, and halving the strip. You will reach a point where you can no longer physically fold the paper in half any more... 7 is the popular theoretical paper folding limit. Now, unfold the paper and you will realize that the creases sometimes point up and sometimes point down. Wouldn't it be nice if you were able to come up with a solution to predict the result of each fold without actually folding it? This will allow us to fold past the theoretical paper folding limit with our mind!

Understand the problem:

Okay, first, I immediately realized that this is a pattern recognition problem. Essentially, if I can figure out the pattern for which the paper's creases come to be as result of each fold,  I should be able to use that pattern to predict the next fold... Right?

Devise a Plan:

My plan was to first just take a piece of paper, fold it in half, observe, record the results, and repeat. Hold on, maybe there are some obvious facts we can take in account first before we dive into this problem. First, we know in our head that by making a fold, the paper is divided into two equal halves, and a second fold would in turn divide each of those halves into two equal halves.

Carry out the Plan:

After some folding, I realized the following:
  • for 2 folds and up, the first crease is always up, while the last crease is always down
  • starting from both ends and moving inwards, the each set of creases are alternates to each other
  • each fold  does not affect the creases created by the previous fold
  • each fold adds alternative up/down creases to the pre-existing creases, such that the first crease is always fronted by an up crease, and followed by a down crease, then each subsequent crease is followed by alternating ups and downs

Look back:

Here is the pattern for folds 1 to 6:
d
udd
uuddudd
uuduuddduuddudd
uuduudduuudduddduuduuddduuddudd
uuduudduuuddudduuuduuddduudduddduuduudduuudduddduuduuddduuddudd

How to do this in Python:

Add code below:

No comments:

Post a Comment