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

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

我們想讓你知道的是

小明上樓梯的時候,如果容許一步跨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




碳排越少,優惠越好!台灣第一個看得見的消費碳足跡,號召大眾實踐低碳生活

碳排越少,優惠越好!台灣第一個看得見的消費碳足跡,號召大眾實踐低碳生活
Photo Credit:王道銀行

我們想讓你知道的是

王道銀行運用「消費碳排放明細」功能推出採獎勵機制的「低碳生活卡」,藉此建立消費者的綠色消費意識,在生活中選擇對地球更好的產品和服務,在享受特別折扣與回饋的同時,也為減緩全球暖化貢獻一份心力。

近年因應地球暖化加劇、極端氣候衝擊,各國政府陸續喊出2050年淨零碳排的目標;歐盟宣布將於明年開徵碳稅,歐洲數國及美國加州宣布未來要禁用油車,日本預計發行千億美元的綠色債券用來推動能源轉型,台灣政府也在今年3月正式公布2050淨零排放路徑,預計陸續投入新台幣9,000億元,與產業界共同朝著減碳目標努力。

然而,要達成2050年的淨零目標,不可能單靠政府和企業,而需要所有地球公民的力量。但從這份調查得知,目前大多數的台灣消費者儘管對於碳議題有基本的瞭解,也很有意識要減碳,卻常常無從得知自己在生活中的各項活動究竟產生了多少碳排放量。

一、王道銀行與萬事達卡Mastercard合作,全台首創推出「消費碳排放明細」
Photo Credit:王道銀行

為了讓消費者們對「碳排放」有感,王道銀行日前推出「消費碳排放明細」功能,是台灣第一家、也是亞太地區第一家採用萬事達卡(Mastercard)碳足跡計算器的金融業者,使用API串接萬事達卡的大數據資料庫,會依據你刷卡購買的產品或服務類別、消費金額等資訊估算出每一筆刷卡消費的碳排放量;只要是王道銀行萬事達卡卡友,都能在網銀或APP上免費開啟「消費碳排放明細」功能,希望藉此讓消費者更加認識所購產品與服務的碳排放量,進而建立綠色消費意識。

而為了鼓勵消費者將減碳意識化為實際行動,王道銀行也推出減碳成功享活儲加碼的活動,消費者只要開啟「消費碳排放明細」功能,並於2022年底前每月至少刷卡一筆一般消費且年平均每元碳排放量低於8公克,即可享隔年整年度新台幣活儲年利率加碼0.1%的優惠,優惠存款金額無上限。

二、王道銀行「消費碳排放明細」功能,讓消費者知道每一筆消費產生的碳排放量
Photo Credit:王道銀行

2019年,在瑞典曾有結合碳排放量與金融產品的先例,一家名為Doconomy的金融新創公司和萬事達卡(Mastercard)合作推出「DO Black卡」,這是全球第一張以「碳足跡」做為刷卡額度的信用卡,相較一般信用卡是以「金錢」做為信用額度單位,「DO Black卡」則以「個人消費的二氧化碳排放量」做為刷卡消費上限,每筆消費都會透過奧蘭指數(Aland Index)的運算技術,算出碳排放量,當刷卡產生的碳排放量達到當月上限時,就不能再刷卡了。

不同於「DO Black卡」的凍結機制,王道銀行則運用「消費碳排放明細」功能推出採獎勵機制的「低碳生活卡」,全台首創以消費碳排放量決定刷卡現金回饋比例;「低碳生活卡」卡友在開啟「消費碳排放明細」功能後,只要當月平均每元消費碳排放量低於8公克,就能自動享有國內刷卡一般消費新台幣兩萬元內、國外刷卡一般消費不限金額的現金回饋加碼至1.5%。「我們希望不只是提供消費碳排放明細、倡導消費者意識到碳排放量,更能進一步鼓勵消費者採取實際減碳行動!」王道銀行董事長駱怡君說。

除了依消費碳排放量享不同的刷卡現金回饋,王道銀行「低碳生活卡」更攜手台灣多家知名的社會企業共同倡導綠色消費,包括鮮乳坊、仁舟淨塑、直接跟農夫買、綠藤生機、茶籽堂、成真咖啡等25家社會企業與B型企業,持「低碳生活卡」於這些店家刷卡消費,能獲得9折、95折或是滿額贈禮等專屬優惠,王道銀行還會額外加碼提供最高4.22%現金回饋;消費者除了能省荷包,還能支持友善環境及社會的品牌,一舉兩得!

三、王道銀行低碳生活卡合作綠色店家共25家,可獲得專屬優惠折扣以及4_22%現金
Photo Credit:王道銀行

減少碳排放是地球上每一位公民的責任,隨著地球升溫臨界點的倒數計時,我們每一個人都需要將減碳意識化為實際行動,運用銀行推出的工具「消費碳排放明細」以及創新金融產品「低碳生活卡」,在生活中選擇對地球更好的產品和服務,在享受折扣與回饋的同時,也為減緩全球暖化貢獻一份心力。

四、王道銀行串聯25家友善環境的社會企業與B型企業,與消費者共同打造低碳生活
Photo Credit:王道銀行

本文章內容由「王道銀行」提供,經關鍵評論網媒體集團廣編企劃編審。