BMAD Posted June 30, 2021 Report Share Posted June 30, 2021 How many different paths can I make up a flight of 20 stairs if I can take the steps either one at a time or two at a time (in any order)? Quote Link to comment Share on other sites More sharing options...
1 rocdocmac Posted July 1, 2021 Report Share Posted July 1, 2021 Spoiler 10946 (Fibonacci #22) Quote Link to comment Share on other sites More sharing options...
0 harey Posted October 7, 2021 Report Share Posted October 7, 2021 Same as rocdocmac Spoiler Before reaching 20 (n) stairs, you can either: - go up 1 stair and apply the solution for 19 (n-1) stairs -- or -- - go up 2 stairs and apply the solution for 18 (n-2) stairs. This gives the formula: f(n)=f(n-1)+f(n-2). (Looks like Fibonacci...) For 1 stair, there is 1 possibility. For 2 stairs, there is 2 possibilities. => Fibonacci Combinatorics: Spoiler Maximum number of double stair steps is given by the integer division of number of stairs by 2. Complete sigle stair steps. Take all permutations with repetitions: Spoiler from math import factorial as MF FIBO_1,FIBO_2=1,1 # staircase will take the values 1,2,3,...20 (yes, 20) for staircase in range(1,21): FIBO_1,FIBO_2=FIBO_2,FIBO_1+FIBO_2 combi=0 doubles=staircase//2 # double will take values 0,1,2...doubles (see staircase) for double in range(0,doubles+1): single=staircase-double*2 combi=combi+MF(single+double)//MF(double)//MF(single) # remove # in the next line for intermediate results # print(staircase,single,double,combi) print('stairs =',staircase,'combinations =',combi,'Fibonacci =',FIBO_1) Output: Spoiler stairs = 1 combinations = 1 Fibonacci = 1 stairs = 2 combinations = 2 Fibonacci = 2 stairs = 3 combinations = 3 Fibonacci = 3 stairs = 4 combinations = 5 Fibonacci = 5 stairs = 5 combinations = 8 Fibonacci = 8 stairs = 6 combinations = 13 Fibonacci = 13 stairs = 7 combinations = 21 Fibonacci = 21 stairs = 8 combinations = 34 Fibonacci = 34 stairs = 9 combinations = 55 Fibonacci = 55 stairs = 10 combinations = 89 Fibonacci = 89 stairs = 11 combinations = 144 Fibonacci = 144 stairs = 12 combinations = 233 Fibonacci = 233 stairs = 13 combinations = 377 Fibonacci = 377 stairs = 14 combinations = 610 Fibonacci = 610 stairs = 15 combinations = 987 Fibonacci = 987 stairs = 16 combinations = 1597 Fibonacci = 1597 stairs = 17 combinations = 2584 Fibonacci = 2584 stairs = 18 combinations = 4181 Fibonacci = 4181 stairs = 19 combinations = 6765 Fibonacci = 6765 stairs = 20 combinations = 10946 Fibonacci = 10946 Quote Link to comment Share on other sites More sharing options...
Question
BMAD
How many different paths can I make up a flight of 20 stairs if I can take the steps either one at a time or two at a time (in any order)?
Link to comment
Share on other sites
2 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.