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?

  • 4
    If you have to choose the number of steps you will take at a time, and stick with that number the whole way down, then the only thing you have missed is the possibility of taking 10 at a time. But if you are allowed to (for example) take 3 steps, then 4, then 3, well, that's a whole different problem. So, which is it?2011-12-08
  • 0
    @Gerry Myerson: "taking one or many steps at a time" probably indicate a variable number of steps at each time ... also this version seems to be the interesting one.2011-12-08
  • 0
    If we have total freedom, there are $512$ ways.2011-12-08
  • 3
    See the WP page on the [number of compositions](http://en.wikipedia.org/wiki/Composition_(number_theory)#Number_of_compositions)2011-12-08
  • 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

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