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.

When I see a problem such as "Given a rod of length $n$ inches, how many ways can you cut it? Components after the cut should have integer inch lengths.", I immediately know that the answer is $2^{n-1}$ since we have an independent option of cutting or not cutting at distance $i$ inches from the left end.

However, I have forgotten why is it so? I know I have 2 options, and I know that we have $n-1$ points where the rod can be cut (or not). But, why is $n-1$ the exponent of $2$?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

Since you recognize that there are $n-1$ potential cut points on an $n$-inch stick, I’m assuming that the question is why you combine the $2$ alternatives at each potential cut point with the $n-1$ potential cut points by exponentiation rather than in some other way.

It’s the multiplication principle at work. Let’s look at a rather different problem first. Suppose that you have a group of $4$ girls and $3$ boys, and you want to select a mixed couple. You can combine any of the $4$ girls with each of the $3$ boys. The possible combinations correspond to the $12$ numbered cells in this table:

$$\begin{array}{c|c|} &B_1&B_2&B_3\\ \hline G_1&1&2&3\\ \hline G_2&4&5&6\\ \hline G_3&7&8&9\\ \hline G_4&10&11&12 \end{array}$$

More generally, if you have to make a sequence of two choices, and the first can be made in $m$ ways and the second in $n$ ways, you have $mn$ ways to make the pair of choices, corresponding to the $mn$ cells in a similar $m\times n$ table whose rows correspond to the alternatives for the first choice, and whose columns correspond to the alternatives for the second choice.

If you have to make a sequence of three choices, the corresponding table will be $3$-dimensional, but the principle is the same. If there are $k$ alternatives for the third choice, you’ll have an $m\times n\times k$ table whose $mnk$ cells correspond to the different ways of combining the choices.

In the stick problem you have a sequence of $n-1$ choices, each of which has $2$ alternatives: at the $k$-inch point, for $k=1,\dots,n-1$, you can either cut or not cut. Thus, a table showing all of the possible combinations would be $(n-1)$-dimensional, with $2$ rows/columns/whatevers in each direction and would have

$$\underbrace{2\cdot2\cdot2\ldots\cdot2}_{n-1}=2^{n-1}$$

cells.

Alternatively, you can simply observe that every time you add an inch to the length of the stick, you add another possible cut point. If you had $a_n$ different ways of cutting an $n$-inch stick, you can still cut the first $n$ inches of an $(n+1)$-inch stick in $a_n$ different ways, and for each of those you can either cut or not cut at $n$ inches. This gives you twice as many possibilities, two for each of the old ones, so $a_{n+1}=2a_n$: the number doubles each time you add an inch to the stick and create a new potential cut point. Now $a_2=2$, since there’s only one possible cut point (at $1$ inch), and you can either cut there or not. Thus, $a_3=2a_2=2^2$, $a_4=2a_3=2\cdot2^2=2^3$, and so on, so that in general $a_n=2^{n-1}$.

share|improve this answer
add comment

You can't cut at $0$ or $n$ as there is no rod on the other side. So there are points you can cut from $1$ to $n-1$. Try counting from $1$ to $3$, how many numbers do you count?

share|improve this answer
add comment

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.