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.

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?

share|improve this question
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? –  Gerry Myerson Dec 8 '11 at 2:16
    
@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. –  Quixotic Dec 8 '11 at 2:21
    
If we have total freedom, there are $512$ ways. –  André Nicolas Dec 8 '11 at 2:37
3  
See the WP page on the number of compositions –  r.e.s. Dec 8 '11 at 3:11
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. –  Gerry Myerson Dec 8 '11 at 5:07

3 Answers 3

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.

share|improve this answer

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<n$, 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)$.

share|improve this answer

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

share|improve this answer

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.