數學題︰小明有多少種方法上樓梯?(加強版)

數學題︰小明有多少種方法上樓梯?(加強版)
我們想讓你知道的是

小明上樓梯的時候,如果容許一步跨50級,他能夠有多少種走法?

早前史丹福醫生提出了一道「上樓梯」數學題︰假如小明要上一條100級的樓梯,但他可以跨步——最多可以跨100級——那麼他有多少種上樓梯的方式?(不可後退、先用左腳或右腳踏上相同梯級視作同一方式。)

當然可以跨100級這個假設很不實際,不過有助解決進一步的問題。

我們可以把每一種上樓梯的方式編碼,寫成一個99位長的數字,每個位只可以是0或者1︰假如踏上第n級,對應的第n位數字就是1,否則為0(由於第100級必然踏上,所以只有99位)。例如︰

  • 0000….0000(全部為0)代表一步跨上第100級;
  • 1111…1111(全部為1)代表沒有跨步,逐級走上去;
  • 0101…0101(0和1梅花間竹)代表不斷跨兩級走上去…

編碼每個位有兩種可能,而且有99個位,因此總共有299種可能,代表小明有299種走法。

* * *

當然這問題並不困難,史丹福接下來問︰如果小明最多只可以跨50步,那他總共有多少種走法?

這問題要比上一題複雜一點,不過可以用上一題的答案協助算出來。我們知道如果不限制小明跨越的級數,他可以有299種方法上這100級樓梯,現在限制他最多可以跨50級,即是說他不能跨超過50級,只要我們把跨超過50級的方法總數算出來,就能找到答案。

用編碼角度去看,問題變成找出有多少個編碼包含連續50個0。

這個問題頗有趣,如讀者想自己思考,可以先別讀下去,想完再回來。以下一段可視作提示。

首先要注意的是,假設小明上樓梯時跨了超過50級,他只能這樣跨一次(因為跨兩次超過50級的話,總數就超過100級),而他必須在第49級或以前跨出這一大步(若他在第50級直接跨到第100級,也「僅僅」跨了50級)。

stair-running-609761_1920
Photo Credit: Hans, Public Domain

假如小明一開始就跨出這一大步,所對應的編碼頭50位都是0,餘下49個位並沒有任何限制,總共有2⁴⁹個組合,每個對應一種先跨最少50步的上樓梯方法。

假如他在第1級跨出這一大步,所對應的編碼首50位會是「1000…000」——第一個位是1,接下來是50個0——餘下48個位沒有任何限制,共有248個組合,每個對應一種在第1級跨最後50步的上樓梯方法。

假如他在第2級跨出這一大步,所對應的編碼第2個位開始是「1000…000」 ——第2個位是1,接下來是50個0——餘下48個位(第1個位以及第53至99個位)沒有任何限制,同樣有248個組合。

如此類推,直到小明在第49級跨出這一大步,還是有248種方法上樓梯。

把上述數字加起來,跨超過50步的方法總數是 248 + 49×248 = 51×248。因此小明不跨多於50級的上樓梯方法,總共有299−51×248種。

* * *

這個問題可以從另一角度思考,不用減法而用加法︰由於小明最後一步只能跨1至50級,所以他踏出最後一步時必然在第50級或以後其中一級,我們可以把踏上第100級的方法,細分成「最後一步在第50級的方法」、「最後一步在第51級的方法」、「最後一步在第52級的方法」…等等,再把這些方法的數量加起來。

(以下的解法會有較多運算,比較繁瑣,建議有興趣的讀者自行拿紙筆計算一次,會較易理解。萬一覺得頭暈眼花,不妨拉下去看下一部分。)

在此我們先定義一個數列fn,n必須是正整數,代表小明在最多可以跨50級的情況下可以走上第n級的方法。當然,我們的目標是計算出 f100

根據上面的定義︰f100 = f50 + f51 + f52 + … + f98 + f99。對 1 ≤ n ≤ 50 而言,下面這條公式成立︰fn+50 = fn + fn+1 + … + fn+48 + fn+49

我們知道,小明踏上第50級有 250 種方法,即 f50 = 250。而且如果 k≤50 的話,他踏上第k級就有 2k 種方法,即 fk = 2k。那麼 f51, f52, … f98, f99 是多少?先嘗試逐個算出來︰

f51
= f1 + f2 + f3 + … + f49 + f50
= 20 + 21 + 22 + … + 248 + 249
= 250−1(最後一步可使用幾何級數的求和公式計算。)

f52
= f2 + f3 + f4 + … + f50 + f51
= 21 + 22 + 23 + … + 249 + 250−1
= 20 + 21 + 22 + … + 249 + 250−1−20
= (251−1)−2
= 251−3

f53
= f3 + f4 + f5 + … + f51 + f52
= 22 + 23 + 24 + … + 250−1 + 251−3
= 20 + 21 +22 + … + 250 + 251−1−3−20−21
= (252−1)−7
= 252−8

這樣算下去似乎不是辦法,我決定把減去的那個數字稱為gk,所以 f51 = 250−g1, f52 = 251−g2, f53 = 252−g3 … 當 n ≥ 50 時,fn+1 = 2n−gn+1−50,憑上面的結果我們知道︰g1 = 1, g2 = 3, g3 = 8。

從上面的算式可看得出︰

gk+1
= g1 + g2 + … + gk + f1 + f2 + … + fk-1 + fk+1
= g1 + g2 + … + gk + 20 + 21 + ... + 2k-2 + 2k-1 + 1(因為此處k必定小於50,所以fj = 2j
= g1 + g2 + … + gk + (2k−1) + 1
= g1 + g2 + … + gk + 2k

(完整證明較難在此打出來,就此略過。)

由此可推出 gk+2−gk+1 = gk+1+2k,並得出 gk+2 = 2×gk+1+2k。不斷代換下去,最終可得出以下公式︰gk+2 = 2k+1 + k+1×2k = k+3×2k
(同樣因為不方便打數學公式而略去細節,如不明白請親手計算一次。)

終於到計算答案的一刻︰

f50 + f51 + f52 + … + f98 + f99
= 249 + 250−g1 + 251−g2 + … + 297−g48 + 298−g49
= 249 + 250 + 251 + … +297 + 298−[g1+ g2 + … + g49 ]
= (20 + 21 + … + 248) + 249 + 250 + … + 297 + 298 −(20 + 21 + … + 248) −[g50−249]
= 299−1−(249−1)−[51×248−249]
= 299−1−249 + 1−51×248 + 249
= 299−51×248

* * *

若把小明可以跨的級數再減少,例如減少最多只能跨30級,上述兩個方法都可以推廣來計算答案。

使用第一個方法時須注意,不要重複點算了上樓梯方法,因為這時候小明可以跨兩次甚至三次超過30級。簡單來說,小明開始跨超過30級時在第0級(即地下)、第1至30級、第31至60級以及在第61至69級的情況,需要分開計算。在排除重複的情況時,只要再按上述思路點算便可,雖然煩瑣但不太困難。

使用第二個方法時須注意,在最多跨30級的情況下,要在 f31 而非 f51 開始計算 gk(注意此處的f、g跟跨50步的情況是不同的數列),而且在 k 的值較大時不能使用 gk = g1 + g2 + … + gk + 2k 這條公式。

雖然在小明最多可以跨50級時,第二個方法麻煩得多,但小明可以跨的級數越少時,我猜想第一個方法會越麻煩(因為要減去的上樓梯方法越多),第二個方法則會變得簡單。不過我怕麻煩沒有找出一般的公式,也不肯定數字要多小時才會改變,僅提出一個極端例子作佐證︰假如小明只能跨最多兩級,用第二個方法思考,不難得出公式 fn+1 = fn + fn−1,而且 f1 = 1 和 f2 = 2——也不妨定義 f0 = 1——正是費波那契數列(Fibonacci sequence)。

原文見作者 Medium

相關文章︰

責任編輯︰鄭家榆
核稿編輯︰王陽翎

或許你會想看
更多『評論』文章 更多『生活』文章 更多『Kayue』文章
Loader