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?

  • 0
    To know the optimal solution we would kind of need the prices... don't you agree?2012-01-11
  • 0
    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 asking2012-01-11
  • 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