Paper Folding Algorithm

This week in CSC104, we were given the task of formulating an algorithm that could predict the direction of the vertices from folding in a strip of paper. The instructions were to "Take a strip of paper and stretch it so that you have one end between your left thumb and index finger and the other between your right thumb and fore finger. Fold the strip so that the left end is on top of the right end. Repeat this several times, each time folding so that the left end is on top of the right end of the strip." The assignment asked to find a sure way to predict the sequence of ups and downs for any number of times you fold the paper.

UNDERSTANDING THE PROBLEM

We want to be able to predict future sequences when the thin strip of paper is folded any number of times.

To further understand the problem, I conducted trials for a strip of paper with up to 5 folds. Their patterns and characteristics are listed below (Tables 1 and 2).

DEVISING A PLAN

A few observations:

-       The number of segments (bordered by the paper edges and vertices) is 2^F.

o   S = 2^F

-       The total number of vertices is one less than the number of segments.

o   V = 2^F-1

-       The number of down vertices is 2^(F-1).

o   D = 2^(F-1)

-       The number of up vertices increases by 2^(F-2) with each successive fold.

o   U_F = U_F-1 + 2^(F-2)

-       The number of up vertices is also 1 less than the number of down vertices.

o   U = D - 1

-       Each fold has a central D.

-       For F number of folds, the sequence of F - 1 forms the right portion of F’s sequence after the central D.

o   For example, with 2 folds, the resulting sequence is UDD. For 3 folds, the resulting sequence is UUDDUDD. The UDD from the sequence before is carried over into the next, forming the right side of the sequence.

-       The left side of the central D is a toggled mirror image of the right side.

o   For example, UUDDUDD has a right side of UDD. Toggling it will replace D’s with U’s and U’s with D’s. Therefore, UDD becomes DUU. Flipped in a mirror image, it will then be UUD. Put together, you have UUDDUDD.

CARRYING OUT THE PLAN

We can now test out this method to determine the sequence of 6 folds, given the sequence for 5 folds!

1.     Carry previous sequence over to right side of central D of target sequence.

DUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDD

2.     Toggle mirror image that sequence!

UUDUUDDUUUDDUDDUUUDUUDDDUUDDUDD

3.     Put it all together!

UUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDD

LOOKING BACK

We can double-check our prediction with our expected characteristics:

Total # of vertices = 2⁶ – 1 = 64 – 1 = 63 = true!

Total # of downs = 2^6-1 = 2⁵ = 32 = true!

Totally # of ups = 32 – 1 = 31 = true!

The sequence fits all the criteria as the previous sequences did!

And there you have the sequence for 6 folds!