2
$\begingroup$

I want to climb down a flight of ten stairs, taking one or many steps at a time. In how many ways can I do this if I am able to take as many steps at a time as I like?

I don't know the answer; I am getting $3$ such as:

$1,2,3,4,..., 10$ (one at a time)

$2,4,6,..., 10$ (two at a time)

$5,10 $ (five at a time)

this is correct/incorrect?

  • 1
    @MaX, what you say is true, but I find it hard to believe that under that interpretation OP was only able to find 3 ways to come down the stairs.2011-12-08

3 Answers 3

8

In the interpretation where the number of steps taken is allowed to vary, there is an easy way to see that the answer is $2^{n-1}$:

For each of the $n-1$ steps (not counting the top one), decide whether or not you will stop at that step on the way down.

There are $n-1$ decisions to make, each with 2 possible choices (stop or don't stop), so that's a total of $2^{n-1}$ ways.

5

We answer the question on the following assumptions: (1) At any time, we can take an arbitrary number of stairs, as long as the total number of stairs ends up at $10$ and (2) Order matters, so that for example the pattern $2+4+4$ is to be counted as different from $4+2+4$.

In general, let $f(n)$ be the number of ways to handle a staircase that has $n$ stairs. It is easy to see that $f(1)=1$. We could compute a little more, finding that for $2$ there are the patterns $2$ and $1+1$, so $f(2)=2$. For $3$ there are the patterns $3$, $2+1$, $1+2$, and $1+1+1$, for a total of $4$. For $4$, enumerating the patterns is not hard: we get $4$, $3+1$, $1+3$, $2+2$, $1+1+2$, $1+2+1$, $2+1+1$, and $1+1+1+1$, a total of $8$. On the basis of this admittedly scanty evidence, we conjecture that $f(n)=2^{n-1}$, and in particular $f(10)=512$.

Now we prove that in general $f(n)=2^{n-1}$. There are various approaches. We first prove the result in a natural but somewhat lengthy way, and then in a shorter way. Suppose that we know that for all $k, there are $2^{k-1}$ patterns. We count the number of patterns for $n$.

Either there is only one giant step of length $n$ ($1$ way) or the last step is one of $1$, $2$, $3$, $\dots$, $n-1$.

If the last step is $1$, we needed to get to $n-1$, which by induction assumption can be done in $2^{n-2}$ ways.

If the last step is $2$, we needed to get to $n-2$, which by induction assumption can be done in $2^{n-3}$ ways.

If the last step is $3$, we needed to get to $n-3$, which by induction assumption can be done in $2^{n-4}$ ways.

Go on in this way. Finally, if the last step was $n-1$, we needed to get to $1$, which can be done in $2^0$ ways.

We conclude that $f(n)=(2^{n-2}+2^{n-3}+2^{n-4}+\cdots +1)+1$ (remember the possibility of a giant step). Easily, if we add from the back, we see that $f(n)=2^{n-1}$ (or else we can sum the finite geometric progression).

Another way: We show that in general $f(n+1)=2f(n)$. Consider all patterns of steps that add up to $n+1$. They are of two types (i) Patterns that have last step $1$ and (ii) Patterns that have last step $>1$.

It is obvious that there are $f(n)$ patterns of type (i). We now count the type (ii) patterns. Take a pattern of type (ii), and shorten its last step by $1$. The total is now $n$. Moreover, we get all patterns for $n$ in this manner, in one and only one way. Thus there are $f(n)$ type (ii) patterns. It follows that $f(n+1)=f(n)+f(n)=2f(n)$.

2

A composition of an integer $n$ into $k$ parts is the number of sums $a_1 + \dots + a_k$ of positive integers that equal $n$. For example, there are 3 compositions of $4$ into $2$ parts: 2+2, 3+1, and 1+3. You should try to prove that the number of compositions of $n$ into $k$ parts is equal to $\binom{n-1}{k-1}$. (Or, look it up in any good combinatorics book.)

Your problem essentially asks you to count the number of compositions of $10$ into $k$ parts, where $1\leq k\leq 10$. That is, if as you go down the staircase you cross $a_i$ stairs in your $i^{\text{th}}$ step, then $a_1 + \dots + a_k = 10$. Your answer is thus $ \sum_{k=1}^{10} \binom{10-1}{k-1} =512 $