2
$\begingroup$

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$?

2 Answers 2

1

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}$.

1

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?