Contributed by David Reed
One of my favorite problems to introduce in CS1 is the paper folding puzzle.
Folding a piece of paper in half results in a folded sheet twice as thick as the original sheet. Similarly, folding this doubled sheet results in a folded sheet four times as thick as the original sheet, and so on. If this process is continued, how many folds would be necessary to obtain a folded sheet whose thickness stretched from the earth to the sun?
I often introduce this puzzle to demonstrate while loops, since a solution can be written in only a few lines of code using a while loop and an assignment. It is a compelling example in that it is virtually impossible to solve without a computer (the answer is counterintuitive), yet simple to program. Student guesses as to the answer vary greatly, with answers in the millions or billions fairly common. They are usually surprised to discover that only 52 folds are necessary, assuming that a single sheet of paper is .002 inches thick.
In addition to providing some basic programming practice, this problem demonstrates the explosive effect of doubling, i.e., exponential growth. Students see that repeatedly doubling a value, even if it starts out small, will produce large values quickly. This exponential growth can conversely be described in terms of halving. Repeatedly halving a quantity reduces its size very quickly, reaching unit size in only a logarithmic number of steps. In this case, each unfolding of a folded sheet reduces its thickness by one half. Starting with a folded sheet one astronomical unit thick, only 52 unfoldings are necessary to reduce it to a single unfolded sheet.
I subsequently build upon the students' analysis of the paper folding puzzle in later parts of the course, especially with respect to binary search and O(N log N) sorting algorithms such as Mergesort and Quicksort. The same halving effect takes place in these algorithms (repeatedly halving the section of list to be searched/sorted), and similarly introduces the logarithmic components to their efficiencies. I have found that students are much more comfortable with the analysis of these algorithms after first having understood the paper folding puzzle.
As an interesting side topic, I sometimes ask students to come up with the initial estimate of paper thickness. I have found this to be a good exercise in problem-solving. Many just guess at a thickness, but at least one student will think of measuring an entire package and dividing by the number of pages. Of course, this is just an estimate since factors such as packaging compression contribute to the measurement. However, this allows us to discuss just how sensitive the puzzle is to an inaccurate initial measure. Due to the doubling effect, the initial estimate can be off by as much as a factor of two and the derived answer will only be off by one fold, at most.