Maths Olympiad Prep

Library / /275 of 520

Combinatorics Difficulty 3.1 AMC 10/12 Find the answer

Everyday at school, Jo climbs a flight of 66 stairs. Jo can take the stairs 11, 22, or 33 at a time. For example, Jo could climb 33, then 11, then 22. In how many ways can Jo climb the stairs?

Pick one

Solution

A dynamics programming approach is quick and easy. The number of ways to climb one stair is 11. There are 22 ways to climb two stairs: 11,11 or 22. For 3 stairs, there are 44 ways:
(11,11,11)
(11,22)
(22,11)
(33)
For four stairs, consider what step they came from to land on the fourth stair. They could have hopped straight from the 1st, done a double from #2, or used a single step from #3. The ways to get to each of these steps are 1+2+4=71+2+4=7 ways to get to step 4. The pattern can then be extended:
44 steps: 1+2+4=71+2+4=7 ways.
55 steps: 2+4+7=132+4+7=13 ways.
66 steps: 4+7+13=244+7+13=24 ways.
Thus, there are (E) 24\boxed{\textbf{(E) } 24} ways to get to step 6.6.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.