Problem Solving Episode

Having the slides printed out for Friday's lecture was very helpful, so I'll be doing that from now on.

Earlier in the semester, we were given a paper folding problem to solve in class using Polya's problem solving method. Today I will write up the process I followed in solving this problem. A copy of the problem can be found on Professor Heap's problem solving wiki.

Step 1 is understand the problem. I need to find the pattern of "up" and "down" folds created by folding a strip of paper a number of times. The paper should always be folded exactly in half, so that the left side folds over the right. The exact number of folds to make is not specified; instead I should be able to answer for any number of folds. Therefore my solution should be in the form of a method or algorithm which can return the pattern based on any given number of folds.

Step 2 is to create a plan. My plan was to carry out a number of folds, then compare the sequence of creases for n folds to the sequence for n-1 folds. There should be a pattern since the sequence for n folds is formed by folding the sequence for n - 1 folds. The total number of creases for each n folds must be a function of n. Also, since the paper is initially folded in half, every subsequent fold will affect both halves of the unfolded paper. Hence, the half to the left of the initial "down" fold must have some relation to the half to the right.

Step 3 is to carry out the plan. I recorded the sequence of up and down folds in a table for each number of folds. First, I discovered that the number of creases for any number of folds n was equal to (2^n) - 1. It was also apparent that the initial "down" crease made by the first fold was always in the centre of the unfolded strip. Because there are always an odd number of creases, there are an equal number of creases on both sides of centre. Comparing the left side to the right side, I found that the left side was the same as the right side in reverse order, with the up and down folds interchanged. When I compared each sequence to the one before it, I found that the right half of the sequence for n is identical to the complete sequence for n - 1. Based on this, the method for finding the sequence of up and down folds for any number of folds n can be expressed by the following recursive algorithm:

def folds(n):
    if n == 1:
        sequence = ["down"]
    else:
        right_side = folds(n-1)
        left_side =  []
        i = len(right_side) - 1
        while i >= 0:
            left_side.append(right_side[i])
            i = i - 1
        left_side = invert(left_side) #for each word, change "down" to "up" and "up" to "down"
        sequence = left_side + ["down"] + right_side
    return sequence

Step 4 is to look back. The relationship between the two halves of a sequence for n folds makes sense, since when folding n - 1 times, the two halves overlap perfectly. I think a solution could also be derived by inserting new creases between each existing crease for the next fold.