2018年5月19日 星期六

小明上樓梯


史丹福回家時時常要行上很長的樓梯,有一次就忽發奇想地想到一條很有趣的數學問題。假如小明要行上一道100級的樓梯,他可以每次最少行上1,但他也可以誇步,由於他的腿真的很長,他最多可以一次誇100級。問他有多少種方法去行上這道100級的樓梯?



方法1
如果小明用1步走完樓梯,明顯只有一種方法,就是一步誇100級。
如果小明用2步走完樓梯,他必須在中間的99級樓梯中選擇一級踏上,所以共有99C1種方法。
如果小明用3步走完樓梯,他必須在中間的99級樓梯中選擇2級踏上,所以共有99C2種方法。
如果小明用4步走完樓梯,他必須在中間的99級樓梯中選擇3級踏上,所以共有99C3種方法。
如此類推,如果小明用100步走完樓梯,他必須在中間的99級樓梯中選擇99級踏上,所以共有99C99種方法。

最後答案就是1 + 99C1 + 99C2 + 99C3 + … + 99C99。這條式要怎麼計算呢?

根據二項式定理(Binomial theorem),(1+x) n = 1 + nC1 x + nC2 x2 + nC3 x3 + … + nCn xn
代入x =1,我們就得到1 + nC1 + nC2 + nC3 + … + nCn = 2n
再代入 n = 99,我們就得到1 + 99C1 + 99C2 + 99C3 + … + 99C99 = 299
所以小明共有299種方法行上樓梯。

方法2
第一個方法已經很精彩了,但思路清晰的朋友也許會想到一個更簡潔美麗的方法,小明可以選擇踏上或者不踏上第一級,可以選擇踏上或者不踏上第二級,可以選擇踏上或者不踏上第三級,如此類推,他最後可以選擇踏上或者不踏上第99級,所以他自然有299種方法行上樓梯。

1 則留言: