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:
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:
Or you could do the following:
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:
So my question is, with the given operations, can you compute the minimum number of operations for any given $N$?
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$.
Fold the fabric into a pile that is exactly 2 inches wide. This takes $\lceil\log_2 n\rceil-1$ steps.
Cut down the middle. This will leave many pieces of fabric, almost all 2 inches wide (perhaps one piece 1 inch wide).
Gather it all into a single pile, 2 inches wide.
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.