HMMT 十一月 2008 · 冲刺赛 · 第 15 题

HMMT November 2008 — Guts Round — Problem 15

[ 9 ] A cat is going up a stairwell with ten stairs. However, instead of walking up the stairs one at a time, the cat jumps, going either two or three stairs up at each step (though if necessary, it will just walk the last step). How many different ways can the cat go from the bottom to the top? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . st 1 HARVARD-MIT NOVEMBER TOURNAMENT, 8 NOVEMBER 2008 — GUTS ROUND p 2008 2009

解析

[ 9 ] A cat is going up a stairwell with ten stairs. However, instead of walking up the stairs one at a time, the cat jumps, going either two or three stairs up at each step (though if necessary, it will just walk the last step). How many different ways can the cat go from the bottom to the top? Answer: 12 The number of ways for the cat to get to the i th step is the number of ways for the cat to get to step i − 2 plus the number of ways to get to step i − 3, because for each way to get to step i , we can undo the last move the cat made to go back to one of these two steps. The cat can get to step 1 in 0 ways, to step 2 in 1 way, and to step 3 in 1 way. Now we repeatedly use our formula for calculating the number of ways to get to the i th step to see that the cat gets to: Step 1 2 3 4 5 6 7 8 9 10 Number of ways 0 1 1 1 2 2 3 4 5 7 So our answer is 5 + 7 = 12. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . st 1 HARVARD-MIT NOVEMBER TOURNAMENT, 8 SATURDAY 2008 — GUTS ROUND p 2008 2009