5
$\begingroup$

I am reading an algorithm example.
The example is about Rod cutting.

The idea is that a steel rod can either be sold as it is, or be cut into integral pieces and sell the pieces. The goal is to find what is best. Sell a rod as a whole or in pieces (prices for rod lengths are assumed to be known).

In the presentation of the solution it says that a rod can be cut in $2^{n-1}$ ways.

I can see and verify that, for $n=1$, $n=2$, $n=3$, and $n=4$ but after that how can this be proved for any value of $n$?

By induction? I mean to verify it for $n=4$ I drew the various cuts. I didn't use some relation with $n=3$.

So although this problem seems to be proved by induction, it seems to me that it is proven some other way, but I am not sure on how.

How can we be sure that the rod can be cut in $2^{n-1}$ ways?

  • 5
    There are $n-1$ places where a cut can be made, and, at each of these places, a cut can either be made or not, so there are $2^{n-1}$ ways of dividing the rod.2012-01-11

2 Answers 2

5

Your question can be interpreted as asking about the number of compositions of the positive integer $n$, and this is indeed $2^{n-1}$.

In order to think of the answer as $2^{n-1}$, we need to assume that there is a marked left end of the rod, and a marked right end, and we are cutting (say) from left to right. So for example we need to think of the cutting $1+2+3+1$ as different from the cutting $1+3+2+1$, or $1+1+2+3$. If order does not matter, we are dealing with the partitions of $n$, which are very much harder to count.

Here is a quick proof of the $2^{n-1}$ result. Suppose that the rod is a ruler, and has a mark every inch. If the rod is $n$ inches long, there are $n-1$ marks. For a cutting pattern, at any of the marks we stop and write Y (we will cut there) or N (we won't cut there). There are $2^{n-1}$ strings of length $n-1$ made up of the letters Y and/or N, so there are $2^{n-1}$ ways to cut.

Comment: One could do a formal induction instead, but that I think would take away from the clarity of the idea. If the induction exercise is important to you, try it. If you experience difficulty, I can fill in details.

0

Thomas Andrews has given a direct proof in his comment. To put it in terms of induction, a one inch rod can be cut in $1=2^{1-1}$ way (not at all). If a length $k$ rod can be cut in $2^{k-1}$ ways, a length $k+1$ rod can be cut either by cutting off the right inch and cut the remaining in $2^{k-1}$ ways or by not cutting off the right inch and cut the remaining in $2^{k-1}$ ways, totaling $2^{(k+1)-1}$ ways.