[Math] Cutting a paper with the smallest number of cuts

algorithmscombinatorics

You want to cut a piece of paper of length $N$ to $N$ pieces of length 1.

It is not allowed to fold the paper, but if two or more previously-cut pieces of paper have the same length, it is allowed to put them one over the other.

If $N=2$ you need 1 cut.

If $N=3$ you need 2 cuts.

If $N=4$ you can use 3 cuts, but there is a better way: use one cut to create two pieces of length 2, then put the two pieces one over the other and use one cut to create four pieces. The total number of cuts is 2.

In general, if $N$ is a power of 2 then the total number of cuts required is $\log_2{N}$.

What is the smallest number of cuts required when $N$ is not a power of 2?

I thought of the following recursive algorithm:

Cut(N)
   If $N=2m+1$ then cut a piece of length 1 and use Cut(2m) on the remainder.
   If $N=2m$ then cut two pieces of length $m$, 
             put one over the other and use Cut(m) on the remainder.

For every $N$, after at most 2 cuts the remaining length will be at most $N/2$. Hence, the number of required cuts in the above algorithm is at most:
$$2 \lfloor\log_2(N)\rfloor$$

The worst case is when $N=2^k-1$; then, $2(k-1)$ cuts are required.

Is there an algorithm that requires a smaller number of cuts?

NOTE: The present question is simpler than Fold, Gather, Cut because here it is not allowed to fold the paper.

Best Answer

Your problem is equivalent to that of finding the shortest addition chain for $N$. You can order the operations by descending lengths of the cut pieces, so you never need to cut the same length twice, so what you're doing is to prescribe for each length that occurs how to compose it from two smaller lengths, which is exactly what an addition chain does.

The lengths of the shortest addition chains are in OEIS sequence A003313. Some interesting results and references are given, but no closed formula.

Related Question