10. Ahmad walks up a flight of eight steps, going up either one or two steps at a time. There is a hole on the sixth step, so he cannot use this step. In how many different ways can Ahmad reach the top step?
A 6
B 7
C 8
D 9
E 10
Solution
C

The sixth step has a hole, so Ahmad must jump from the fifth to the seventh and then he steps up one step to get to the eighth step. Hence we only need to count the number of ways to get to the fifth step using one or two steps at a time. He could use only "one-steps" (one way), or he could use one "2-step" and three "1-steps" (four ways: 2111, 1211, 1121, 1112), or he could use two "2-steps" and one "1-step" (three ways: $221,212,122$ ). Altogether this is $1+4+3=8$ ways.