Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
You shouldn't cut multiple layers of fabric like this - it'll ruin your shears. –  alex.jordan Jun 3 '13 at 21:51
2  
@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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.