# Fold, Gather, Cut

Here’s a mathematical puzzle I’ve been thinking about. Let’s say you have a strip of fabric, of length $N$ units ($N$ being an integer), which has regular markings on it every 1 unit along its length. Your task is to cut the fabric into $N$ lengths of 1 unit each, but to do so using the fewest operations possible. The operations available to you are:

1. Cut – you may cut through any number of overlapping layers in a single operation. All cuts must be through the 1-unit markings on the fabric, and the cut must be in a straight line. (No using a wavy cut to do the whole thing in 1 operation.)
2. Gather – you may gather any number of already-cut lengths together in a bundle. They must all line up on one end. (If they are the same lengths, they will of course line up on both ends.)
3. Fold – You may fold any number of layers of fabric in either direction. Multiple folds can only be counted as 1 operation if the places to be folded are already lined up, either via a previous Gather or another Fold step. Unlike Cuts, a Fold may occur between the 1-unit markings. Unfolding does not require an additional operation.

Now it can be trivially shown that for any $N$ which is $2^k$, an ideal solution would be to have $k$ Cuts alternating with $k-1$ Gathers, for a total of $2k – 1$ operations. This is by no means the only ideal solution. For example, consider $N=8$. The steps could be:

1. Cut into 2 lengths of 4.
2. Gather lengths.
3. Cut into 4 lengths of 2.
4. Gather lengths.
5. Cut into 8 lengths of 1.

Or you could do the following:

1. Fold at the 3rd marking.
2. Fold at the 5th marking the other direction.
3. Cut down the middle to get 4 lengths of 2 (2 of which are folded).
4. Gather lengths.
5. Cut into 8 lengths of 1.

Still 5 steps either way. It gets trickier when you consider other numbers however. Say, for $N=9$, you could take any $N=8$ solution, and then add 1 more cut for that last piece that will be 1 unit too long. But you can do 9 in 5 steps as well:

1. Fold in half.
2. Cut at the 3rd and 6th markings (which should be lined up) to get 3 lengths of 3.
3. Gather lengths.
4. Fold all 3 in half again.
5. Cut into 9 lengths of 1.

So my question is, with the given operations, can you compute the minimum number of operations for any given $N$?

#### Solutions Collecting From Web of "Fold, Gather, Cut"

Here is an algorithm that does it in $2+\lceil\log_2 n\rceil$ steps. This doesn’t match the OP’s algorithm for $n=9$, unfortunately, but it’s “k+2” rather than “2k-1” when $n=2^k$.

1. Fold the fabric into a pile that is exactly 2 inches wide. This takes $\lceil\log_2 n\rceil-1$ steps.

2. Cut down the middle. This will leave many pieces of fabric, almost all 2 inches wide (perhaps one piece 1 inch wide).

3. Gather it all into a single pile, 2 inches wide.

4. Cut.

For example, if $n=16$. Fold (8″), fold (4″), fold (2″). Cut, gather, cut. 6 steps.

Second example, if $17\le n\le 32$. Pretend it’s $32$, the next higher power of 2. Fold (16″), fold (8″), fold (4″), fold (2″). Cut, gather, cut. 7 steps.