劉應興的部落格

有 n 個人分蛋糕，怎麼分才能人人覺得滿意？

這問題的基本假定是：其一，每個人都想分到最大塊的蛋糕；其二，每個人對蛋糕大小的評判是主觀（且固定）的；其三，每個人都可以精確切出任意他所要大小的蛋糕。

整個蛋糕，我們用一個宇集 S 表示；一塊蛋糕，用一個子集 A 表示，各人對蛋糕大小的評判，用測度 μi(A) 表示，並假設 μi(S) 都是 1。

當 n = 2 時，由一人，稱某甲，把 S 切割成 S = A∪A', 其中 A' 就是 A 的補集；然後另一人，稱某乙，選擇他要 A 或 A'。某甲事先不知某乙將選哪一塊，所以他必然切出他認為公平的，恰好 A, A' 各佔 1/2 的結果。如果某乙選 A，就是 μ2(A) ≧ 1/2 ≧ μ2(A')；以某甲看來則是 μ1(A) = μ1(A') = 1/2，結果皆大歡喜。

當 n = 3 時，甲切 μ1(A) = 1/3 的一塊交給乙；乙如果認為 μ2(A) ≦ 1/3 則 pass 給丙，如果認為 μ2(A) > 1/3 則切成較小一塊 B 交給丙；丙如果接受乙傳過來的 B 或 A 表示他接受 μ3(B) 或 μ3(A) > 1/3, 若不接受則乙接受 B，或如果他沒有把 A 切小成 B 則可接受 A（表示他認同 μ2(A) = 1/3)，或由甲接受 A。故結果有五種情形：

(1) 丙接受 B: μ3(B) ≧ 1/3, μ2(B) = 1/3, μ1(B) ≦ 1/3; 留下 S* = B'。
(2) 乙接受 B: μ2(B) = 1/3, μ1(B) ≦ 1/3, μ3(B) < 1/3; 留下 S* = B'。
(3) 丙接受 A: μ3(A) ≧ 1/3, μ1(A) = 1/3, μ2(A) ≦ 1/3; 留下 S* = A'。
(4) 乙接受 A: μ2(A) = 1/3 = μ1(A), μ3(A) < 1/3; 留下 S* = A'。
(5) 甲接受 A: μ1(A) = 1/3, μ2(A) < 1/3, μ3(A) < 1/3; 留下 S* = A'。

不管哪種惰形，都留下 S* 給剩下兩個人分，而在兩人的評判中，留下的部分都至少是 2/3, 因此每人可分得至少整個蛋糕的 1/3，又是皆大歡喜。

當 n > 3 時，類似 n = 3 的方法，第一個人切下他認為 1/n 大小的蛋糕，第二個人以後可以直接 pass 給下一人或切下他認為多出的部分；最後一人決定要不要接受最後的結果，如果接受表示他認為那一塊至少有 1/n；如果不接受表示他認為那一塊小於 1/n，則回傳前一人。如果無人接受，則切最後一刀的人必須接受，因為他認為那就是 1/n 大小；在他後面的人認為那一塊不到 1/n，而在他前面的人所認為的 1/n 大小的一塊被切除了所謂「多了」的一塊，也認為最後頂多仍是 1/n，但更可能認為小於 1/n（被切除的不是 0 測度）。最後留下至少（除了已分到的人以外所有人認為） 1-1/n 給 n-1 人分，他們將分得每個人認為最少 1-1/n 的 1/(n-1)，也就是最後每個人都認為他分得整個蛋糕的 1／n 或更多，歡喜收場。