Difficulty: Tricky
Flora likes to run up stairs as fast as she can! Sometimes she lands on every stair and sometimes she skips a stair, taking two in one stride. And sometimes, she mixes it up, skipping a stair with some strides, and not skipping on others. She never skips more than one stair in one stride – that’s a bit too dangerous!
This gets her thinking: how many different ways can she run up a staircase?
For example, she can run up a 3-stair staircase three different ways:
- 1 1 1 = meaning all three stairs taken 1 at a time
- 1 2 = one regular stride, and then skip a stair and do the remaining 2 in one go.
- 2 1 = skip the first stair with a big stride, then take a regular stride to get to the top.
How many different ways can Flora run up a 4-stair staircase?
Bonus challenge question: how many ways can Flora run up a 10-stair staircase?
Need a hint?
Notice how in the example above, the numbers in each solution add up to 3, the number of stairs in the staircase. Use patterns of 1 and 2 to write out possible solutions for a 4-stair staircase. Each solution should add up to 4 and you shouldn’t repeat the same pattern of numbers.
For the bonus challenge question, write out the number of solutions for each staircase size from 1 to 5 stairs and see if you can recognise a famous pattern.
Brainteaser answer
There are five ways for Flora to run up a 4-stair staircase and 89 ways to run up a 10-stair staircase.
For the 4-stair staircase, it can help to organise the solutions by how many stairs were taken 2 at a time. This way you can keep track of the patterns and make sure none are repeated. Remember that the sum of the digits in each solution must add up to 4.
All one-stairs: 1111
One 2-stair: 112, 121, 211
Two 2-stairs: 22
There are 5 total solutions for a 4-stair staircase.
Bonus challenge question: how many solutions for a 10-stair staircase?
Writing out all the possible solutions for a 10-stair staircase would take a long time! Perhaps we can use patterns to help us solve this question faster. The pattern we are interested in is the number of solutions as the staircase gets more stairs.
We’ll begin by writing out the number of solutions for each size staircase so far:
1-stair staircase = 1 solution = 1
2-stair staircase = 2 solutions = 11, 2
3-stair staircase = 3 solutions = 111, 12, 21
4-stair staircase = 5 solutions = 1111, 112, 121, 211, 22
So far, the pattern for solutions is: 1, 2, 3, 5. It looked the number of stairs equalled the number of ways, but that pattern didn’t work for 4, so we need a better way of looking at the question.
When you take your first step, you can go up one stair, or 2 stairs.
If you go up one stair, you have 4 stairs left. We already know how many ways you can take those 4 stairs: There are 5 solutions.
If, instead, your first step is a big one and you skip a stair, you have 3 stairs left. Once again, we can look back and see there are 3 solutions.
We can turn these ideas into lists of solutions:
Adding “1” to 4 stair staircase solutions = 5 solutions = 11111, 1112, 1121, 1211, 122
And adding “2” to 3 stair staircase solutions = 3 solutions = 2111, 212, 221
Find the total number of solutions by adding 5 + 3 = 8 solutions for a 5-stair staircase. Take a moment to convince yourself that we captured all possible solutions. You can use our original organisational tool:
All one-stairs: 11111
One 2-stair: 1112, 1121, 1211, 2111
Two 2-stairs: 122, 212, 221
Again, there are 8 total solutions for a 5-stair staircase.
Now our solutions pattern is 1, 2, 3, 5, 8… If you’ve spent a lot of time playing with numbers, you might recognise this pattern. It’s called the Fibonacci sequence!
The Fibonacci sequence follows the rule that each new number is equal to the two previous numbers added together. Adding the two previous numbers is exactly what we did above to find the solutions for a 5-stair staircase.
We can keep using this pattern to calculate the remaining answers. For example, the 6-stair staircase has 8 + 5 = 13 solutions.
6-stair = 5 + 8 = 13
7-stair = 8 +13 = 21
8-stair = 13 + 21 = 34
9-stair = 21 + 34 = 55
10-stair = 34 + 55 = 89
There are 89 possible ways for Flora to run up a 10-stair staircase! Is that more or less than you expected?
You can learn more about the Fibonacci sequence in spirals and in fruit here!
Leave a Reply