You climb a 12-step ladder. With each movement you can advance 1 or 2 steps. How many different ways can you get to the top?
Home > Riddles > 12-step ladder
12-step ladder
It is one of those problems that can be miscounted if one clings to immediate intuition. The good way to read it is not to list paths blindly: it relates each case to the previous ones.
Hints
Show hints
- It is not necessary to list all the paths: it is enough to relate each case to the previous ones.
- To reach step n, the last move can only come from n−1 or n−2.
- That produces the same recurrence as Fibonacci, with a different start.
Solution
Show full solution
Answer: 233 ways. Let $F(n)$ be the number of ways to reach step $n$. The last movement can only be of two types:
- or you come from step $n-1$ with a jump of 1;
- or you come from step $n-2$ with a jump of 2. Therefore,
$$ F(n)=F(n-1)+F(n-2). $$ The initial conditions are: $$
F(1)=1,\qquad F(2)=2.
$$ From there:
$$ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ 144,\ 233. $$ Thus, for 12 steps, $$
F(12)=233.
$$ It is the same Fibonacci recurrence, but displaced by the initial conditions.
Related riddles
Keep practicing
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.