Question

There are ten steps in a staircase and a person has to take those steps. At every step, the person has got the choice of taking one step or two steps or three steps. The number of ways in which a person can take those steps is
A. ${{3}^{10}}$
B. ${{3}^{9}}$
C. ${{3}^{8}}$
D. None of those

Answer 1

Hint: To solve this question, we have to take every combination of steps that the person can take and we have to write the number of ways he can do that combination and sum them up. We have to assume the number of one steps taken by the person as x, the number of 2 steps taken by the person as y, and the number of 3 steps taken by the person as z. As the total number of steps is 10 we can write that $x+2y+3z=10$. We have to substitute different values of z and write corresponding x and y to get the answer. For example, if z = 1 , we get $x+2y=7$, one way is x = 1, y= 3, z= 1 . The number of ways of arranging x number of a’s, y number of b’s, and z number of c’s….. is given by $N=\dfrac{\left( a+b+c... \right)!}{a!\times b!\times c!...}$. Use this formula for every combination to get the total number of possible ways.

Complete step-by-step solution:
To do the problem, we have to assume the number of one steps taken by the person as x, the number of 2 steps taken by the person as y, and the number of 3 steps taken by the person as z. As the total number of steps is 10 we can write that
 $x+2y+3z=10\to \left( 1 \right)$
We have to use different values of z to get a set of (x, y, z) and apply the combinations formula to get the number of combinations for a particular set of (x, y, z).
Number of ways of arranging x number of a’s, y number of b’s and z number of c’s….. is given by $N=\dfrac{\left( a+b+c... \right)!}{a!\times b!\times c!...}\to \left( 2 \right)$
Case-1 z=1
Then we get $x+2y=7$
We can write the different possible combinations of x and y are
$\left( x,y \right)=\left( 1,3 \right),\left( 3,2 \right),\left( 5,1 \right)$
We can write the different possible ordered pairs of (x, y, z) as
$\left( x,y,z \right)=\left( 1,3,1 \right),\left( 3,2,1 \right),\left( 5,1,1 \right)$
For example consider $\left( x,y,z \right)=\left( 1,3,1 \right)$, there are 1-1 steps, 3-2 steps and 1-3 steps. Let us consider N(x, y, z) as the number of combinations for (x, y, z). Using the analogy in equation-2, we get
$N\left( 1,3,1 \right)=\dfrac{\left( 1+3+1 \right)!}{1!\times 3!\times 1!}=\dfrac{5!}{3!}=\dfrac{5\times 4\times 3!}{3!}=20$.
Similarly, applying it to other cases, we get
$N\left( 3,2,1 \right)=\dfrac{\left( 3+2+1 \right)!}{3!\times 2!\times 1!}=\dfrac{6!}{3!\times 2!}=\dfrac{6\times 5\times 4\times 3!}{3!\times 2}=60$
$N\left( 5,1,1 \right)=\dfrac{\left( 5+1+1 \right)!}{5!\times 1!\times 1!}=\dfrac{7!}{5!}=\dfrac{7\times 6\times 5!}{5!}=42$
Totally, $N(z=1)=N\left( 1,3,1 \right)+N\left( 3,2,1 \right)+N\left( 5,1,1 \right)=20+60+42=122$
Case-2 z=2
Then we get $x+2y=4$
We can write the different possible combinations of x and y are
$\left( x,y \right)=\left( 2,1 \right),\left( 0,2 \right),\left( 4,0 \right)$
We can write the different possible ordered pairs of (x, y, z) as
$\left( x,y,z \right)=\left( 2,1,2 \right),\left( 0,2,2 \right),\left( 4,0,2 \right)$
Using the analogy in equation-2, we get
$N\left( 2,1,2 \right)=\dfrac{\left( 2+1+2 \right)!}{2!\times 1!\times 2!}=\dfrac{5!}{2!\times 2!}=\dfrac{120}{4}=30$.
$N\left( 0,2,2 \right)=\dfrac{\left( 0+2+2 \right)!}{0!\times 2!\times 2!}=\dfrac{4!}{2!\times 2!}=\dfrac{24}{2\times 2}=6$
$N\left( 4,0,2 \right)=\dfrac{\left( 4+0+2 \right)!}{4!\times 0!\times 2!}=\dfrac{6!}{4!\times 2!}=\dfrac{6\times 5\times 4!}{4!\times 2}=15$
Totally, $N(z=2)=N\left( 2,1,2 \right)+N\left( 0,2,2 \right)+N\left( 4,0,2 \right)=30+6+15=51$
Case-3 z=3
Then we get $x+2y=1$
We can write the different possible combinations of x and y are
$\left( x,y \right)=\left( 1,0 \right)$
We can write the different possible ordered pairs of (x, y, z) as
$\left( x,y,z \right)=\left( 1,0,3 \right)$
Using the analogy in equation-2, we get .
$N\left( 1,0,3 \right)=\dfrac{\left( 1+0+3 \right)!}{1!\times 0!\times 3!}=\dfrac{4!}{1\times 3!}=\dfrac{4\times 3!}{3!}=4$
Totally, $N(z=3)=N\left( 1,0,3 \right)=4$
Case-4 z=0
Then we get $x+2y=10$
We can write the different possible combinations of x and y are
$\left( x,y \right)=\left( 10,0 \right),\left( 8,1 \right),\left( 6,2 \right),\left( 4,3 \right),\left( 2,4 \right),\left( 0,5 \right)$
We can write the different possible ordered pairs of (x, y, z) as
$\left( x,y,z \right)=\left( 10,0,0 \right),\left( 8,1,0 \right),\left( 6,2,0 \right),\left( 4,3,0 \right),\left( 2,4,0 \right),\left( 0,5,0 \right)$
Using the analogy in equation-2, we get
$N\left( 10,0,0 \right)=\dfrac{\left( 10+0+0 \right)!}{10!\times 0!\times 0!}=1$.
$N\left( 8,1,0 \right)=\dfrac{\left( 8+1+0 \right)!}{8!\times 1!\times 0!}=\dfrac{9!}{8!\times 1!}=9$
$\begin{align}
  & N\left( 6,2,0 \right)=\dfrac{\left( 6+2+0 \right)!}{6!\times 2!\times 0!}=\dfrac{8!}{6!\times 2!}=28 \\
 & N\left( 4,3,0 \right)=\dfrac{\left( 4+3+0 \right)!}{4!\times 3!\times 0!}=\dfrac{7!}{4!\times 3!}=\dfrac{7\times 6\times 5}{6}=35 \\
 & N\left( 2,4,0 \right)=\dfrac{\left( 2+4+0 \right)!}{2!\times 4!\times 0!}=\dfrac{6!}{2!\times 4!}=15 \\
\end{align}$
$N\left( 0,5,0 \right)=\dfrac{\left( 0+5+0 \right)!}{0!\times 5!\times 0!}=1$
Finally, we get
 $\begin{align}
  & N\left( z=0 \right)=N\left( 10,0,0 \right)+N\left( 8,1,0 \right)N+\left( 6,2,0 \right)N+\left( 4,3,0 \right)N+\left( 2,4,0 \right)N+\left( 0,5,0 \right) \\
 & N\left( z=0 \right)=1+9+28+35+15+1=89 \\
\end{align}$
Total number of ways is given by
$\begin{align}
  & N=N\left( z=1 \right)+N\left( z=2 \right)+N\left( z=3 \right)+N\left( z=0 \right) \\
 & N=122+51+4+89=266 \\
\end{align}$
$\therefore $ Total number of possible ways= 266 ways. Answer is option(D).

Note: Students can make a mistake by considering that there are 3 ways for each step and the total will be ${{3}^{10}}$ but that is not the case because, if we choose to take 2 steps at a step, we cannot land on the immediate step but we are also counting them. So, ${{3}^{10}}$ leads to a large over the count of the total ways.