# 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$?

-
You shouldn't cut multiple layers of fabric like this - it'll ruin your shears. –  alex.jordan Jun 3 '13 at 21:51
@alex.jordan: I use a high-powered imaginary laser when cutting mathematically arbitrary layers of fabric. Folding also gets tough when you have a lot of layers, but we're not taking that into account here. –  Darrel Hoffman Jun 3 '13 at 22:21
Can you explain how you argue that $2^k$ needs at least $2k-1$ operations? –  Calvin Lin Jun 3 '13 at 22:29
@Vadim123 I believe that counts as $2N-4$ folds, because they are not already lined up. –  Calvin Lin Jun 3 '13 at 22:31
@CalvinLin: If you ignore the Fold operation, you can simply cut it in half and gather until you're done. However, that may be wrong, since folds can double up, so I think Vadim123 below may be closer - though I think that's still not quite right. –  Darrel Hoffman Jun 3 '13 at 23:38

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.

-
Actually, for odd numbers, you could leave one end dangling, so the folded stack is 2 wide except for at one end where it's 3. Since you're cutting down the middle, that will still produce a length of 2, which can be gathered for the final cut. For $N=9$ then, it'd still be 5 steps - Fold at the 4th mark, then fold again so it's 2 wide plus that dangling 3rd. Cut, Gather, Cut again. I believe this may be the best solution. –  Darrel Hoffman Jun 3 '13 at 23:28
Then again, you could even leave 2 ends dangling the same way, so $N=10$ could also be 5 steps. Fold in half, then Fold again for a stack 2 wide with 2 ends dangling. Cut and you have 5 lengths of 2, which you can then Gather and Cut and be done. Only at $N=11$ does it go up to 6 steps... –  Darrel Hoffman Jun 3 '13 at 23:34
Taking the above into account, I'd say the actual formula would be $2+\lceil\log_2 (n-2)\rceil$. That allows you to avoid some unnecessary folding steps for values within $2^k+2$. –  Darrel Hoffman Jun 4 '13 at 0:35