第一章
你的那一半比我的這一半大！

如果兩個人想毫無爭議地分享一塊蛋糕，那麼解決辦法向來是「我切你選」。如果多於兩個人想分這塊蛋糕，問題就複雜多了，而且人愈多愈難處理。除非你用一把慢慢移動的刀子，抽絲剝繭切開那些難處……和那塊蛋糕。

一個大塊頭和一個小個子坐在某列火車的餐車車廂，兩人都點了魚。當侍者上菜時，竟然是一大一小的魚。侍者先端給大塊頭選，他馬上搶了那條大的；小個子抱怨說，這實在太不禮貌了。

「那麼，如果讓你先選，你會怎麼做呢？」大塊頭以讓人惱怒的語氣問道。

「我會很有禮貌，選小的那一條。」小個子調侃地回答。

「那好，這就對了，小的歸你啦！」大塊頭回敬道。

就如這個老笑話所言，不同的人在不同環境下會有不同的想法，有些人總是難以滿足。過去五十年間，數學家一直在這類公平分配的問題中掙扎斡旋――通常用蛋糕而不是魚來說明――直到現在總算有了一個周延且相當深入的理論。羅伯森（Jack Robertson）和韋伯（William Webb）引人入勝的著作《切蛋糕分法》（Cake Cutting Algorithms）（詳見書末「延伸閱讀」）中，對這類問題做了全面的探討。在本章和第十四章，我們將一窺這些看似簡單，而且讓大家都滿意他們分得的那份蛋糕的分法。

最簡單的情形是只有兩個人來分，他們――一再重申――想分享一塊蛋糕，而且要能滿足於自己公平分到的那一份。這裡所謂的「公平」是指「比我評估的一半還多」，儘管兩位接受者對蛋糕成分的評價可能不盡相同。例如，愛麗絲可能喜歡櫻桃，而鮑伯偏愛糖霜。更令人玩味的現象之一是，在切蛋糕理論中，如果接受者對蛋糕部位的喜好不同，分蛋糕的工作比較容易。這一點也不讓人意外，因為我們可以分給鮑伯糖霜的部分，把櫻桃那個部分給愛麗絲，然後得到兩全其美的結果。如果兩人都喜歡糖霜，問題的難度就變高了。

如果只有兩位接受者，問題還好解決。這種「愛麗絲切，鮑伯選」的解決方式，已經運作了兩千八百年！兩位參與者之所以認為這種方式還算公平，某種意義上是因為他們沒有抱怨結果的理由。如果愛麗絲不喜歡鮑伯選剩的部分，只能怪她自己分蛋糕的時候不夠謹慎，沒好好地（根據自己的評估）平分。如果鮑伯不喜歡他的部分，是他自己做了錯誤的選擇。

當參與分配的人增加到三位，整個情況開始變得有趣多了。湯姆、迪克和哈利想分一塊蛋糕，讓彼此都滿意自己分到的至少1/3塊蛋糕，憑藉各自的價值判斷來決定。順道說明，在所有這類問題中，都假設蛋糕可以無限分割，雖然在理論上，蛋糕多是由有價值的「原子」組成――一個至少有一位接受者認為它是非0值（non-zero value）的點。不過為了簡化，我會假設沒有「原子」存在。羅伯森和韋伯藉由分析一個似是而非的答案來處理這個變化，推演過程如下：

步驟一：湯姆把蛋糕切成X和W兩塊，他認為X有1/3這麼大，W是2/3大。
步驟二：迪克把W切成Y和Z兩塊，他認為兩塊各占W的1/2。
步驟三：哈利從X、Y和Z中選擇喜歡的一塊。然後湯姆從選剩的兩塊中挑選。
最後剩下的那一塊是迪克的。

這種分法公平嗎？

顯然哈利會很滿意，因為他有優先選擇權。湯姆也很滿意，原因稍微複雜了點。如果哈利選擇X，則湯姆可以從Y和Z中選擇一塊他認為比較有價值的（如果他看來兩塊等值，就隨便挑一塊）。既然他認為它們總值是2/3，必定覺得其中至少有一塊值1/3。另一方面，如果哈利選擇了Y或Z，則湯姆可以選擇X。

然而，迪克可能不會滿意結果。如果他一開始就不贊同湯姆的第一次切法，可能認為W不值2/3，這意味著能讓他滿意的只有X那塊。但如果哈利選擇了Y，湯姆選擇了X，那麼迪克只剩Z可拿――這可不是他想要的。

於是上述分法是不公平的。1944年，波蘭數學家團體成員之一的史坦豪斯（Hugo Steinhaus），率先提出三人公平分配蛋糕的正確解答。這個團體的成員定期在利沃夫（Lvov）一家咖啡館聚會。史坦豪斯的方法應用了一種稱為「修減法」（trimming）的手法。

步驟一：湯姆把蛋糕切成X和W兩塊，他認為X有1/3這麼大，W是2/3大。
步驟二：他把X交給迪克修整，如果迪克認為它的大小多於1/3，那麼他可以
將這塊蛋糕修成他認為的1/3；否則原封不動。我們稱這塊得到的
蛋糕為X*：它不是等於X，就是小於X。
步驟三：迪克把X*交給哈利，讓哈利決定要不要這塊。
步驟四：（a）如果哈利接受了X*，那麼湯姆和迪克將剩下的蛋糕――W加
上任何從X修減下來的部分――堆成單一一堆（糊糊的）蛋糕。他
們用它來玩「我切你選」的遊戲。（b）如果哈利不接受X*，且迪
克修減過X，則迪克拿X*，湯姆和哈利玩剩下的蛋糕的「我切你
選」。（c）如果哈利不接受X*，且迪克沒有修減過X，則湯姆拿X，
迪克和哈利玩剩下的蛋糕的「我切你選」。

這是一項解答――至於它的邏輯，就交由你去證明。基本上，任何不滿意所得那塊的人一定是一開始做了錯誤的選擇，抑或切割時沒有仔細評估。那也只能怪自己了。

1961年，杜賓斯（Leonard Dubins）和史班尼爾（Edwin Spanier）提出一個迥然不同的解答，運用一把移動刀。把蛋糕擺在桌上，用一把刀從蛋糕的最左邊開始，平穩地逐步橫過蛋糕。決定下刀時，刀子左邊部分的蛋糕稱為L。當L達到湯姆、迪克和哈利各自認為的1/3大小時，依規定他們得馬上喊「停！」。第一個喊停的人得到蛋糕L，其餘兩人要嘛以「我切你選」的方式分蛋糕，要嘛再次移動刀子，直到某人認為蛋糕值達1/2時馬上喊停，得到此份蛋糕（想想看，如果兩人同時喊停，該怎麼辦呢？）。

這種分法的最大特色是，它可以輕易擴及n位分配者。移動刀子橫過蛋糕，並規定每一位分配者依各自的評價，在L達到1/n時馬上喊停。第一個喊停的人得到蛋糕L，而其餘n－1個參與者針對剩下的蛋糕重複上述程序，當然這次喊停時的蛋糕評價值為1/（n－1）……依此類推。

我向來不特別偏愛移動刀的分法――我想是因為這牽涉到參與者對時間差的反應能力。避免這種爭論的最佳方法，或許是把刀子的移動速度放慢。非常慢。或者，對等地，假設所有參與者都有超快的反應能力。

讓我們稱第一種解答為「固定刀」分法，第二種為「移動刀」分法。運用於三人參與的固定刀分法，也能輕易擴及n位參與者。當湯姆正獨自坐著凝視「他的」蛋糕時，迪克出現了，想分塊蛋糕。於是湯姆把蛋糕切成他認為的兩等份，而迪克選了其中一塊。當他們正要開始享用時，哈利來了，也要求平分蛋糕。湯姆和迪克各自將自己的蛋糕切成三等份，他們認為每一份是等值的。哈利從湯姆和迪克的蛋糕中各選一份。為什麼這種「連續式配對」的分法行得通，道理並不難懂，能擴大運用到任何數目的參與者的箇中原因相對容易明白。修減法也可以擴大運用至n個參與者，但必須在座每一位參與者都有機會修減一塊蛋糕到他能接受的結果，如果再沒有其他人想修減，那麼他就得到這塊蛋糕。

當分蛋糕的人很多，連續式配對的分法需要切非常多刀。何種分法才能切最少刀呢？移動刀分法需要切n－1刀，以得到n塊蛋糕，這就是你能得到的最小數目。但固定刀分法的下刀次數就沒那麼容易計算了。假設有n個人，一般來說用修減式分法要切（n²－n）/2次。連續式配對分法需要n!－1次，這裡n!＝n（n－1）（n－2）…3.2.1就是n的階乘（factorial）。這個數目遠大於修減式分法需要的次數（n＝2時除外）。

然而，修減法不是最好的方法。較有效率的「分割與獲得」（divide and conquer）分法，進行方式大致如下：試著一刀切開蛋糕，讓約半數的人願意獲得一塊公平分配的蛋糕，而其他人願意獲得另一塊。然後把相同的模式重複運用在兩塊分開來的子蛋糕。這種分法所需的切割次數大約是n log2 n。正確的公式為nk－2k＋1，這裡的k是一單一整數，而2k－1＜n≦2k。這大概是你能運用的最佳方式了。

這些概念最終不只是為了好玩而已。現實生活中常見的重要課題是，以何種方式來分配資產，讓所有參與分配的人覺得公平。領土和商業利益的協商就是例子。原則上，切蛋糕問題的解決方法可以應用於這類情況。的確，當德國戰敗後，由同盟國（美國、英國、法國）和蘇聯共同瓜分託管，第一次嘗試分割後剩下柏林，然後柏林再做另一次瓜分，所以協商者直覺地用了類似的分法。某種相當類似的處理方式造成今日以色列和巴勒斯坦間的緊張關係，搶著爭食主要的耶路撒冷「廚餘」和另一個爭議的焦點西岸（West Bank）。數學上的公平分配能在協商時幫上忙嗎？非常慶幸地，我們活在一個有足夠理性來處理這類事情的世界，但政治往往不是這麼回事。特別是，人們對事情的價值判斷很容易在達成暫時性的協議之後改變；如果這樣，我們之前的討論就等於白談了。

不過，還是先以理性的方式試試看，說不定行得通呢。

讀者迴響

我收到許多關於切蛋糕分法的信件，內容從我討論的切法的簡化到嶄新的實質研究都有。有些讀者試圖消除我對「移動刀」分法隱約的不安感。我擔心的是反應時間的快慢。避免這個問題的建議是――經過一些書信往來後，稍微做了修改――利用參與者在蛋糕（或比例模型〔scale model〕）上做記號的方式，代替移動刀。首先，選定一個方向（假設是北南向），然後輪流要求n位參與者中的每一個人，在蛋糕上最西邊的部分畫一條北南向的線，在線以西的蛋糕是他們想要的（也就是說，他們估計線左邊的那塊蛋糕值1/n）。誰的線在最左邊，誰就切下那一小塊拿走，並退出分配。以同樣的方式繼續執行下去。於是由西往東的依序切割取代了計時，而相同的作法適用於所有移動刀分法。

如此看來，我對移動刀分法的保留是多餘的。可是沒多久，紐約大學的布姆斯（Steven Brams）――這類問題的專家――撰文指出，我先前的憂慮不是那麼容易去除。布姆斯、泰勒（Alan D. Taylor）和茲維克（William S. Zwicker）分析移動刀設計的兩篇論文，特別列於「延伸閱讀」。他們的第二篇論文顯示，在有四位參與者的一個無猜忌分配移動刀步驟中，最多只需要切十一刀。

然而，針對四位參與者，並限定切割次數（不管次數多麼多）的離散處理方式尚未出現，或許這種方式根本不存在。顯然他們不能以蛋糕上有想像的「記號」的方式，做出這樣離散的設計。所以用「記號」的方式來簡化移動刀的設計，適用於某些情況――但不是所有情況。

第一章你的那一半比我的這一半大！如果兩個人想毫無爭議地分享一塊蛋糕，那麼解決辦法向來是「我切你選」。如果多於兩個人想分這塊蛋糕，問題就複雜多了，而且人愈多愈難處理。除非你用一把慢慢移動的刀子，抽絲剝繭切開那些難處……和那塊蛋糕。一個大塊頭和一個小個子坐在某列火車的餐車車廂，兩人都點了魚。當侍者上菜時，竟然是一大一小的魚。侍者先端給大塊頭選，他馬上搶了那條大的；小個子抱怨說，這實在太不禮貌了。 「那麼，如果讓你先選，你會怎麼做呢？」大塊頭以讓人惱怒的語氣問道。 「我會很有禮貌，選小的那一條。」...