數學網紅的演算法脫口秀

iThome 2020/07/30 09:07(11天前)

我有準確到很誇張的料理秤,因為我看著食譜烹飪時會想完全遵照。生活中已經充滿複雜的選擇和決定,但至少像烤蛋糕這種事有完整又詳盡的步驟說明,所以不必擔心做出無知的決定。我也很喜歡量東西。

悲哀的是,生活的其他各方面很少有「食譜書」,但這不表示我們無法應用同樣的思維。有一些其他的情況,譬如選擇終身伴侶,仍然能運用通常只會在食譜書上看到的條理清楚的決策類型。把引導你進行某種活動的預先決定步驟條列出來,這在數學上稱為算則或演算法(algorithm),有點像發展到極致的蛋糕食譜,它會讓你做決定,然後根據你的決定來指示接下來要做什麼,而不是在告訴你究竟要做什麼。

如何尋找理想另一半

尋覓終身伴侶是一種微妙的平衡。一般而言,第一次開始約會的時候,你並不知道對方跟自己的可能愛情速配程度,在沒有比較基準的情況下,你無法確定某個人是不是高於平均標準的合適對象,是否應該跟某個人定下來。這會讓跟第一次約會對象共度一生有點像在賭博:你應該多跟幾個人約會,先了解一下情況。話雖如此,如果你和人約會的時間花太久,這樣也很冒險,可能會錯過理想伴侶,最後只好隨便找個單身的人將就。這是個棘手的狀況。理想的做法是約會人數恰到好處,得到選擇的最佳益處,同時又讓不會錯過理想對象的可能性最大。

幸好數學替我們省了一些事:那個適當人數是你這輩子能約會的總人數的平方根。要如何估計可能約會人數的多寡,全看你的統計熟練度和自信程度,就像你接下來要如何收集樣本。「自發性回應樣本」通常算是被社會接受的,而「分層隨機樣本」可能就會害你關進監獄。

暫時先不管這個,下面是尋覓最理想的愛情的方法:

第1步:估計你這輩子能約會的人數n。

第2步:算出那個數字的平方根√n。

第3步:開始約會,並刷掉前面√n個人;當中最棒的人選會是你的衡量標準。

第4步:繼續約會,在遇到超越前面√n個約會對象所設標準的第一個人時定下來。

誰會曉得事情可以這麼容易?像決定要跟誰定下來這類的問題,有個令人微微焦慮的數學名稱叫做「最佳停止問題」(optimal stopping problem)。最初的那個最佳停止問題稱為祕書問題(secretary problem),以下就是原始的版本。

你想新聘一個私人助理,公司的人資部門已經遵照正式的多元化政策所制定的準則刊登徵人廣告,此刻你的辦公室外面有十個應徵者,有各種性別種族,全都準備好要面試這份工作,每位應徵者將逐一走進你的辦公室,讓你評定他們的條件是否足以勝任。跟每個應徵者面試過後,你必須立刻決定要錄用還是繼續面試下一位。你沒有錄用的人,馬上就會被一個競爭對手錄用:你無法事後再請他們回頭替你工作。

你現在的處境很有意思。邏輯建議你不應該錄用你面試的第一個人,因為你還不清楚應徵者的一般素質如何,但你也不想等到第十個人,因為如果只剩一個人可面試,你就只能錄取這個人,不管他的工作適任程度如何。中間一定有某個理想的地方,你可以不要再面試更多的應徵者,而只是看看他們的長相,然後趕緊挑選出優秀者,這就是最佳停止點。這和為了找終身伴侶而跟人約會,是同樣的限制條件;如果你和某個對象分手,而後來才發覺那人是理想人選,很少能回頭再面試一次。

1950年代,祕書問題在美國數學家之間拋來拋去,我們不知道是誰先解決的〔不過大家認為可能是美國數學家梅瑞爾‧弗拉德(Merrill Flood)]。出現在印刷品上的第一個正式解法,是英國統計學家丹尼斯‧林德利(Dennis Lindley)在1961年出版的。要解開這個問題,需要意識到所有的十個應徵者可以從最佳排到最差,然後打散成某種隨機順序。第一個走進來的應徵者是最佳人選的機會是十分之一,但問題是你根本不知道。

分析了天分的可能分布,計算出如果你面試等候應徵的任何一群人的前面37%,然後挑選出比你目前為止面試過的人來得優秀的下一位,那麼你就有37%的機會選中最佳應徵者。因此,他的演算法跟我們的約會演算法一樣,只是以0.37×n代替了√n。37%這個數字之所以一直出現,是因為它是這個1/e比率,e就是常數2.718281828...。為什麼e這個常數擅自闖入,簡單說是跟最佳應徵者在隊伍中的可能位置的估計有關。利用這個方法,你就有超過三分之一的機會,選到總體而言最適合的人選。

不過,原始的祕書問題是假設你採取寧缺勿濫的極端態度。林德利在數學上證明了,他的37%演算法是最好的方法,但那是只在你完全滿意最佳人選、完全不滿意其他人的情況下。在現實情況下,取得略遜於最佳選擇的東西只會讓你稍微不滿意。更好的解決之道,是會讓你盡可能選到應徵者當中排名在很前面的人,即使不一定是最好的。

心理學家尼爾‧比爾登(Neil Bearden)在2006年計算出,可用來挑選出與理論上最佳人選相比,排名在最前面的應徵者的最佳策略,他正是√n方法的發現者。平均來說,√n方法會讓你從十個人當中選到滿意度75%的人選;而在一百人的排隊應徵者中,這個數字大約是90%。

面對生活上的任何抉擇,從選擇終身伴侶到購物,你都可以採用這個演算法。我要買二手車的時候,就採用了這個策略,確定自己在非買下不可之前,去看了我有時間查看的車子數量當中的至少√n輛。我認為這個方法最大的好處是讓人待時而動,不要衝動之下接受了自己的第一個選擇。針對現實決策過程案例的分析均發現,大家決定得太快,考慮的選項不夠多(線上交友除外,有些人在交友網站會因為選擇太多,而變得難以抉擇,只要可能有更好的人選,他們就無法讓自己定下來)。最佳停止演算法可以免除一切的遲疑不決。

以這種方式尋覓另一半,聽起來或許很冷淡無情,不過曾經有人用數學來尋找愛。(提出克卜勒猜想的那位)克卜勒的第一任妻子因霍亂亡故後,決心把尋找新任妻子變成一個數學步驟。在1613年寫的一封信中,他描述自己計畫以兩年的時間跟十一個可能人選面談、排序,然後做出精心計算過的抉擇。我們不知道他用來排序的「為妻相宜函數」是什麼,不過倒是知道他感覺到祕書問題的限制。他企圖回頭向他面談的第四位小姐求婚,但她已經準備好迎接新的生活,所以拒絕了。最後他幸福快樂地娶了十一人中的第五位,這下子可就是嚴謹的愛意了。

魔術怎麼變?

撇下兩性關係,我們也可以把演算法應用到正整數上,甚至更好!只不過,按預先規定逐步做數字運算,聽起來也許不大刺激,主要是因為這真的不刺激。但那不是重點:執行演算法這件事本身就不大有趣。數學家對演算法興致高昂的原因,不是他們喜歡做重複的差事(儘管很多人還是愛做),那就像你是因為很喜歡量好材料然後攪拌而去烤蛋糕(我就是這樣)。數學家之所以喜歡演算法,是因為演算法能夠做到的事。數學家喜歡做計算,也喜歡把它吃掉。

第1步:取任何一個正整數。

第2步:把每位數字相加起來。

第3步:如果算出的數字和超過一位數,就重複做第2步。

第4步:把最後的一位數答案寫下來。

這個演算法是找出任何一個整數除以9的餘數的方法。你可以隨便找個整數來驗算看看,答案會等於比它小的第一個9的倍數與它的差數。像這樣反覆把所有的數字相加,直到得出一位數的答案為止的產出結果,稱為一個整數的數字根(digital root)。這個過程本身稱為去九法(casting out nines),因為它是從一個整數去掉9的倍數。去九法是數學上最古老、最重要的演算法之一。

在上一個千禧年之交,活躍於現今伊朗的科學家伊本‧西那〔(Ibn Sina,他的拉丁文名字是阿維森納(Avicenna)〕在寫到這個去九法時,把它稱為「印度人的方法」,暗示這個方法已經使用很久了。在費波納契(Fibonacci)把印度-阿拉伯數字引進歐洲前,管帳的人早就在使用去九法了。已知最早的金融數學印刷本《特雷維索算術》(Treviso Arithmetic,出版於1478年),就描述了確認複雜算術問題答案的數字根,要等於所相加的數的數字根總和的方法。他們把9去掉,來驗算重要的財務計算結果。接下來我們準備用這個方法變個魔術。

自願的觀眾:

第1步:取任何一個正整數。

第2步:把這個數乘以9。

第3步:大聲唸出乘出來的答案,但其中一位數字不要唸出來。

魔術師:

第1步:算出自願觀眾唸出來的所有數字的數字根。

第2步:知道所缺的那個數字是數字根與9的差數。

第3步:宣布漏掉沒說出的是哪個數字。

觀眾:

第1步:感到不可思議。

這是個很棒的魔術,因為不論自願的觀眾選了哪個整數,只要乘上9,乘出的新數的數字根一定是9。算出他們告訴你的那些數字的數字根後,你就能知道缺的那個數字是讓數字根加到9所欠缺的那個數。利用去九法算出數字根,也很容易心算出來,因為需要處理的數永遠不會超過一位數。這聽起來實在太簡單了,但是效果很讚。我有一次在倫敦漢默史密斯阿波羅(Hammersmith Apollo)會館的舞台上,在三千多人的面前表演這個把戲,當時最令人緊張的一點,是希望自願的觀眾按電子計算機的時候不要出錯。

這個把戲更具雄圖的版本(有這麼多人在場,我還不敢嘗試)需要掩飾一下乘以9的步驟。如果請自願的觀眾拿著計算機,不斷地把隨機的數字相乘起來,直到螢幕上無法顯示更多位數的答案為止,這時他們很可能在無意間乘了9,要不然就是至少乘了兩個帶有因數3的數。確切地說,把許多隨機的一位數相乘起來,得出的八位數答案有96.75%的機會,會是9的倍數。不過,我不願意承擔那3.25%的機會,讓自己在那麼多人面前像個白痴!(註:為了算出這個機率,我寫了一個電腦程式,產生100億次這樣的隨機數字,而100億個當中有9,674,919,018個是9的倍數。寫電腦演算法來檢驗一個魔術演算法,讓我非常開心。)

有一整套稱為免手法魔術(self-working trick)的魔術,其實就是靠演算法做到的魔術,只要魔術師一步一步照著指示做,魔術就一定會成功。有一個免手法魔術,是幾乎每個人一生當中似乎都會遇到的紙牌魔術,它通常叫做三疊紙牌魔術(Three Pile Trick),傳統上是用21張牌來玩,理由我搞不懂:用到27張牌也能變一模一樣的魔術。魔術師誇口說(這是一定要的)他可以找出自願者隨機選出的任何一張牌。

第1步:自願的觀眾從一疊27張牌中挑出一張,記住花色和數字,然後把牌放回去並重新洗牌。

第2步:魔術師以牌面朝上的方式發牌,分成三疊(依照同樣的發牌方向,每次在每疊牌各發一張)。

第3步:自願者指出他們選中的牌在哪一疊裡,但不要指出是哪張牌。

第4步:魔術師收起三疊牌,把自願者所指的那一疊放在中間。

第5步:第2、3、4步再重做兩次。

第6步:現在自願者挑選的那張牌正好在27張牌的正中央,也就是從最上面開始算的第十四張。

魔術師現在可以運用自己最具創意的方法,揭曉第十四張牌。我個人最喜歡的方式,是一開始先把牌一張一張翻開,一邊聲稱自己在搜尋自願者臉上的反應,接著你就一直翻到差不多第十七張牌,然後聲稱下一張絕對是他們挑出的那張牌。有時候他們甚至會跟你賭一杯酒之類的,因為他們很確定你會猜錯。

接下來你就往回翻,把已經翻開的第十四張牌翻面,實踐了你誇口說出的話,如果你又老謀深算打了賭,就還賭贏了。但要提醒一下,要是自願者沒有把他們選中的牌,告訴獨立的第三人或是寫在某處,他們很容易就會靠謊騙來逃避賭輸請客。

這類型的紙牌魔術已經夠好了,不過有一類稱為「任意牌、任意數字」的戲法,是紙牌魔術當中夢寐以求的戲法。這是指自願者所選出的牌可以移動到一副牌的指定位置(而不是淪落在中間)。稍加調整並多思考一下,「三疊紙牌魔術」也能做到這一點。在我的版本中,我在把牌發成三疊的時候,會隨便問問自願者最喜歡哪個小於27的數字,而在魔術終了,他們的牌就出現在那個位置。

唯一的差別是有時你可以把指出的那疊牌放在最上面或最下面,而不是每次都放在中間。為了找出它在哪裡,就把疊在最上面稱為位置0,中間位置稱為1,最下面稱為2,然後只要把你想擺在自願者的牌上方的牌數轉換成三進位。第一次重組三疊牌的位置時,根據1的數目把指出的牌放進位置0、1或2,第二次就依據3的數目,而第三次依據9的數目;因此,如果你想把七張牌放在自願者選出的牌的上方,7的三進位表示是021(它有零個9,兩個3,一個1),於是就按照這個順序(從1開始倒過來進行)把指出的那疊放在中間、最下面及最上面。在魔術終了,你從最上面數七張牌拿走,在第八個位置的下一張就是自願觀眾所選出的牌。

我有點懊悔在我的書裡解釋這個魔術,因為這個魔術讓我成功地給觀眾,還有數學家和魔術師,留下深刻印象。我當初是在葛登能1956年的第一本數學書《數學、魔術與謎》裡偶然發現這類型的魔術,他在書中把它稱為「熱爾崗的疊牌問題」(Gergonne's Pile Problem),並暗示這個問題在前一個半世紀已經為人熟知。在那之後的半個世紀,它似乎給人遺忘了,而我在重新探究它背後的數學的過程中獲得很大的樂趣,還把它用在我最喜歡的魔術表演中。

葛登能在他的書裡用了一章的篇幅來介紹27張牌魔術的各種變化,不過重點還是放在魔術表演的可能性,他在章末附上加拿大人梅爾‧史多佛(Mel Stover)寄給他的短箋。史多佛指出了這套魔術的進位制,以及改成不同牌數的魔術變法,他的短箋裡說明了如何把牌數增加到100億張的假想狀況。理論上,把100億張牌發成十疊,共發牌十次,就能把所選出的任何一張牌移動到100億種可能位置當中的任何一個位置,若每秒發一張牌,就是不到3,169年的時間。史多佛先生強調,發這一百疊、每疊十億張牌的過程要很細心,因為稍有不慎就會全毀。用他的話來說:「這會讓魔術從頭再來,很少有觀眾願意看第二遍。」(摘錄整理自第11章)

 書籍簡介 

數學大觀念2:從掐指一算到穿越四次元的數學魔術

麥特‧帕克(Matt Parker)/著;畢馨云/譯

貓頭鷹出版

售價: 600元

 作者簡介 

麥特‧帕克(Matt Parker)

人稱脫口秀數學家,經常出現在BBC、《衛報》、英國各地的舞台上、科展、科學節和劇場,跟大家談數學。原本在澳洲教數學,現居英國基爾福(Guildford)。

FB留言

即時科技
媒體

降雨:

氣溫: