Fun With Folding - Math Problem

Earlier in the semester we were told to work through a problem called “Folding”. 

Understand The Problem
We were required to take a piece of paper and fold it in half from left to right. Then, we had to unfold the paper and see how many creases there were and what direction they were facing (either up or down). This process was repeated multiple times. 

Devise a Plan / Carry Out The Plan
While working on this with my partner, we decided to repeat the process five times and came up with the following information. A downward crease is represented by a “D” and an upward crease with a “U”

1.    D

2.    UDD

3.    UUDDUDD

4.    UUDUUDDDUUDDUDD

5.    UUDUUDDUUUDDUDDDUUDUUDDDUUDDUDD

After coming up with the result for the first five folds, we tried to identify a pattern. This did not take us very long as we quickly realized that the sequence prior to the current one appears at the end of the current sequence which can be easily noticed through the five sequences given above.

This was when Prof. Heap gave us permission to look at the hints. The first one said to think recursively which we did by noticing the previous pattern appears in the current one. However, the second pattern said to think symmetrically which took a little while. My partner made a key observation by noticing that half of the pattern occurs twice in some way. This took me a while to catch however my partner quickly understood this and decided to code up a solution to the problem.

Essentially, what we figured was that the previous pattern goes directly to the end of the current one, and the first part of this pattern is the opposite of the previous + ‘D’ but flipped. My partner made a program that emulated this and helped explain to me the small pieces I did not understand. There was a flip method that replaces the “D” with a “U” and vice versa. After flipping it, he also reversed the string. After this, he added a “D” which was the middle character of every pattern and then he added the previous pattern to the end. After finishing the program, we tested it and the result for the first five patterns were the same as what we had written down at the beginning so it seemed to be working. We tested it on a few more to confirm that our logic was right and it seemed that we finished the problem.

Look Back 
I found this very interesting how we started off by understanding the problem we had and then simply by devising a plan (to test the first few patterns) we were able to grasp this pattern and arrive at a solution. The program my partner came up with was also very interesting as it caught me by surprise not having extensive programming knowledge.