A probability problem by Twisting Tiger

Note it down it will be better to solve

1 (2 steps) at a time and 9 (1 steps) at a time = 10! / 9!

2 (2 steps) at a time and 7 (1 steps) at a time = 9! / (7! x 2!)

3 (2 steps) at a time and 5 (1 steps) at a time = 8! / (5! x 3!)

4 (2 steps) at a time and 3 (1 steps) at a time = 7! / (4! x 3!)

5 (2 steps) at a time and 1 (1 steps) at a time = 6! / (5! x 1)

0 (2 steps at a time and 11 (1 steps) at a time = 11! / 11!

Total ways together = 10! / 9! + 9! / (7! x 2!) + 8! / (5! x 3!) + 7! / (4! x 3!) + 6! / (5! x 1) + 11! / 11!

                     = 10 + 36 + 56 + 35 + 6 + 1

                     = 144 ways

Let $S(i)$ denote the number of different ways to reach up to the $i$ th step. Clearly, $S(1)=1,S(2)=2$ . For $i\geq 3$ , to reach the ith step, the last step may be of length $1$ or $2$ . Hence, $S(i)=S(i-1)+S(i-2)$ Solving this recursion, we get the answer $S(11)=144$ .

Relevant wiki: Fibonacci Sequence

The person can use 144 different ways to reach the top.

From the problem, we can get the equation $x+2y = 11$ such that $x,y \in \mathbb{N}$ Using some logical reasoning, we see that $x$ is always odd while $y$ can be even or odd. Using this information, we list out all possible coordinates: $(11,0), (9,1), (7,2), (5,3), (3,4), (1,5)$ For each coordinate, there is a number of combinations. $(11,0): \binom{11}{11} = 1 \\ (9,1): \binom{9+1}{1} = 10 \\ (7,2): \binom{7+2}{2} = \frac{9!}{2! \cdot 7!} = 36 \\ (5,3): \binom{5+3}{3} = \frac{8!}{5! \cdot 3!} = 56 \\ (3,4): \binom{3+4}{4} = \frac{7!}{5! \cdot 4!} = 35 \\ (1,5): \binom{1+5}{5} = \binom{6}{1} = 6$ Adding all of these up, we get $1+10+36+56+35+6 = \boxed{144}$

A fairly simple way to view this problem would be to consider the fact that the man's trip to the top of the stairs is the result of moving up one or two stairs. In other words, the trip up the stairs can be expressed as a sum comprising of only 1's and 2's. For example, if we only wanted the man to go up the stairs one step at a time, our sum would be $1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1$ . If we wanted the man to go 2 steps at a time until we got to step number 11, our sum would be $2 + 2 + 2 + 2 + 2 + 1$ . Now, all we have to do is make a list of all of the unique sums we can make (each sum contains a different number of 1's and 2's). The possible sums are:

Sum 1: 2 + 2 + 2 + 2 + 2 + 1

Sum 2: 2 + 2 + 2 + 2 + 1 + 1 + 1

Sum 3: 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1

Sum 4: 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Sum 5: 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Sum 6: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

All we need to do is figure out how many equivalent expressions we can make out of our sums. To do this, we use the binomial coefficient for each of the expressions, considering the fact that the equivalent expressions are all created using the same numbers in different positions due to the Communitive Law of Addition. Sum 1 contains 6 numbers, and 5 of those numbers are 2's, so the binomial coefficient of Sum 1 would be $\binom{6}{5}$ = 6. For each sum, you should get the following:

Sum 1: $\binom{6}{5}$ = 6

Sum 2: $\binom{7}{4}$ = 35

Sum 3: $\binom{8}{3}$ = 56

Sum 4: $\binom{9}{2}$ = 36

Sum 5: $\binom{10}{1}$ = 10

Sum 6: $\binom{11}{0}$ = 1

Add the six numbers together and you get $\boxed{144}$ possible ways.

I will use "hop" to refer to the motion of stepping and "stair" to refer to what the problem refers to as steps. The number of possibilities is equal to the number of sequences $(a_1,\ldots,a_k)$ where $\sum_{i=1}^k = 11$ and $a_i \in \{1,2\}$ for all $i$ . Note that the sequence is of length $k$ if and only if there are exactly $(11-k)$ hops of $2$ stairs. Since the $1$ -stair hops and $2$ -stair hops can happen in any order, there are a total of ${{k}\choose{11-k}}$ ways to climb the stairs with exactly k hops. Clearly $k$ can range from $6$ to $11$ , so the total number of ways this can be done is $\sum_{k=6}^{11} {{k}\choose{11-k}} = {{6}\choose{5}} + {{7}\choose{4}} + {{8}\choose{3}} + {{9}\choose{2}} + {{10}\choose{1}} + {{11}\choose{0}} = 6 + 35 + 56+ 36 + 10 + 1 = 144$

Sum of combinations of (6:5), (7:4), (8:3), (9:2), (10:1), (11:0) = 144

First number represents total steps, second number represents the number of double steps.