Toiletpaper Problem

A Toiletpaper Problem

To truly let this blog live up to its name, I propose the following toiletpaper problem, inspired by real life:

I'm on the toilet (number 2, if you must know) and, because the paper is rather thin, I tear off a good long section to be able to double it over. Upon folding it in half, however, I realize that the piece I tore off is still too long to use! What to do?

WELL: I could tear this folded over peice in half, but this would lead to the unfortunate situation in which the one section would have two layers, unconnected by a fold. As we all know, the layers of this cheap toiletpaper would seperate in such a case.

The problem becomes: how to tear this piece in half such that the two halves end up folded in half and of the same size.

The solution for this was pretty obvious: I ended up unfolding it, tearing it in half, and then folding each half in half.

BUT this gave rise to the question: what if the piece you tore off originally is 3 times the length you want? 4 times? N times?

The algorithm above takes N folds and N-1 tears. But you can do better than this.

Give an algorithm that takes:

N folds and one tear

1 fold and O(log(N)) tears

O(log(N)) folds and one tear

NOTE: O(log(n)) means "order of log(N)" This means that the number of folds grows roughly logarithmically but may be slightly different from what your calculator would say for "log base 2 of N" For example: f(m) = log2(m) + 4; O(f(m)) = O(log(m)). The constant goes away.