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 2F.
o S = 2F
-
The total number of vertices is
one less than the number of segments.
o V = 2F-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 UF = UF-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 = 26 – 1 = 64 – 1 = 63 = true!
Total # of
downs = 26-1 = 25 = 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!
