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.

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?

share|improve this question
    
To know the optimal solution we would kind of need the prices... don't you agree? –  Patrick Da Silva Jan 11 '12 at 16:31
    
The prices are assumed to be known.I mentioned that.But in how many ways a rod can be cut in general is not dependent on prices.2^(n-1) is not the optimal solution.Is the number of solutions i.e. the total number of ways a rod can be cut.And for this number I am asking –  user384706 Jan 11 '12 at 16:35
4  
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. –  Thomas Andrews Jan 11 '12 at 16:44

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

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.