Sometimes, jumping 3 at a time can change your face!

If Abdur Rehman likes to walk up the stairs climbing either one or three stairs in each step, in how many ways can he walk up ten stairs?


The answer is 28.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Aditya Kumar
Mar 31, 2016

Since I'm not so good at combinatorics, I chose to do it in a no-brainer method, i.e., by simple counting.

No. of 3s No. of 1s Ways to do it No. of ways to do it
0 10 1111111111 1
1 7 31111111,13111111...,11111113 8
2 4 331111,133111...,111133 15
3 1 3331,3313,3133,1333 4

Hence, total ways to do it is = 1 + 8 + 15 + 4 = 28 =1+8+15+4=28

Moderator note:

Good approach of listing out the possible ways.

Once the number of 3's and 1's is fixed, do you know how to use stars and bars?

Nice display of information. If Abdur can climb one, two or three steps at a time there would be 274 274 ways of him walking up the ten stairs, (I think).

Brian Charlesworth - 5 years, 2 months ago

Log in to reply

Did you do the same way?

Aditya Kumar - 5 years, 2 months ago

Log in to reply

2 years ago when I didn't know much combinatorics I also used to problems that way. But now simply I did 10C0+8C1+6C2+4C3

Kushagra Sahni - 5 years, 2 months ago
Ankit Kumar Jain
Apr 1, 2016

We can form an equation as a + 3 b = 10 a + 3b = 10 . So, we obtain 4 4 solutions ;

b = 0 , a = 10 b = 0 , a = 10

b = 1 , a = 7 b = 1 , a = 7

b = 2 , a = 4 b = 2 , a = 4

b = 3 , a = 1 b = 3 , a = 1

Here the values of b b indicate the number of steps in which he climbed up 3 3 stairs and a a indicates the number of steps in which he climbed up 1 1 stair.

So for case I I we have 10 10 steps of 1 1 stair hence permutations = 10 ! 10 ! × 0 ! = 1 = \dfrac{10!}{10!\times0!} = 1

For case I I II we have 7 7 steps of 1 1 stair and 1 1 step of 3 3 stairs hence permutations = 8 ! 7 ! × 1 ! = 8 = \dfrac{8!}{7!\times1!} = 8

Similarly for cases I I I III and I V IV we have permutations = 6 ! 4 ! × 2 ! = 15 = \dfrac{6!}{4!\times2!} = 15 and 4 ! 3 ! × 1 ! = 4 \dfrac{4!}{3!\times1!} = 4

Adding all the cases : 1 + 8 + 15 + 4 = 28 1 + 8 + 15 + 4 = \boxed{28}

Moderator note:

Good approach applying stars and bars.

How would we solve this problem more generally? Like if there were 100 steps?

Good approach applying stars and bars.

How would we solve this problem more generally? Like if there were 100 steps?

Calvin Lin Staff - 5 years, 2 months ago

Log in to reply

@Calvin Lin To solve it more generally I first thought of generating functions but I think that wouldn' t help much.. Sir can you suggest me the generalised form of the question...

Ankit Kumar Jain - 5 years, 2 months ago

Log in to reply

Check out the wiki page :)

Calvin Lin Staff - 5 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...