分蛋糕的無(wú)妒忌協(xié)議

蔡歷亮

有一只質(zhì)地均勻的蛋糕，要把它分給n個(gè)人，是否存在著一種方法能把這只蛋糕分得人人都心滿意足呢？這相當(dāng)于在問(wèn)：是否存在一種方法，使得這n個(gè)人中每個(gè)人都認(rèn)為自己所得的這部分是各人所得中最為理想的部分？這個(gè)問(wèn)題，還可敘述的更深入一些（也更繞口一些）：是否存在一種“將蛋糕切分成n個(gè)部分，并且使得參與分蛋糕的n個(gè)人中的每個(gè)人都對(duì)‘自己所分配到的蛋糕是所切分成的n個(gè)部分中的哪一個(gè)部分的態(tài)度是毫不在乎的”的方法？如果存在這樣的方法，我們把其中的分配稱為n人無(wú)妒忌分配，把導(dǎo)致這種分配的程序稱為n人無(wú)妒忌協(xié)議.

1二人無(wú)妒忌協(xié)議

把局中人記為﹟1、﹟2.由﹟1將蛋糕切分成兩部分，﹟2從中挑選他喜歡的部分.

評(píng)注（1）這種分配協(xié)議很簡(jiǎn)潔，并且具有令人滿意的性質(zhì)：如果﹟1認(rèn)為自己吃了虧，那么只能責(zé)怪自己分割不均；如果﹟2認(rèn)為自己吃了虧，那么只能責(zé)怪自己挑選無(wú)方.

（2）二人協(xié)議是“我切你選”協(xié)議，它要求一位局中人能把這個(gè)蛋糕切分成2個(gè)對(duì)他來(lái)說(shuō)都可以接受的子蛋糕塊.也就是說(shuō)，至少有一位局中人具備這種切分能力，對(duì)二人協(xié)議來(lái)說(shuō)，這是一個(gè)前提（也稱基本假設(shè)）.本文在緊接著討論的3人、4人及更多人的無(wú)妒忌協(xié)議中，將上述基本假設(shè)加強(qiáng)為如下所述的基本假設(shè)A：給出一個(gè)蛋糕或其任意部分，給出任意一個(gè)正整數(shù)m，局中的每一位人都能充當(dāng)分割者，把這個(gè)蛋糕（或其任意部分）分割成m個(gè)對(duì)分割者來(lái)說(shuō)都可以接受的子蛋糕塊.

2塞爾弗里奇三人協(xié)議

下面緊接著敘述的這個(gè)協(xié)議抄錄自文[1].據(jù)文[1]介紹，這個(gè)協(xié)議是屬于約翰·塞爾弗里奇（John Selfridge）的，本文在這里只改動(dòng)了其中1處明顯的錯(cuò)誤.文[1]把局中人記為﹟1、﹟2、﹟3.

第一步：﹟1把蛋糕“三分天下”，分成對(duì)他來(lái)說(shuō)都可以接受的3個(gè)部分.endprint

有一只質(zhì)地均勻的蛋糕，要把它分給n個(gè)人，是否存在著一種方法能把這只蛋糕分得人人都心滿意足呢？這相當(dāng)于在問(wèn)：是否存在一種方法，使得這n個(gè)人中每個(gè)人都認(rèn)為自己所得的這部分是各人所得中最為理想的部分？這個(gè)問(wèn)題，還可敘述的更深入一些（也更繞口一些）：是否存在一種“將蛋糕切分成n個(gè)部分，并且使得參與分蛋糕的n個(gè)人中的每個(gè)人都對(duì)‘自己所分配到的蛋糕是所切分成的n個(gè)部分中的哪一個(gè)部分的態(tài)度是毫不在乎的”的方法？如果存在這樣的方法，我們把其中的分配稱為n人無(wú)妒忌分配，把導(dǎo)致這種分配的程序稱為n人無(wú)妒忌協(xié)議.

1二人無(wú)妒忌協(xié)議

把局中人記為﹟1、﹟2.由﹟1將蛋糕切分成兩部分，﹟2從中挑選他喜歡的部分.

評(píng)注（1）這種分配協(xié)議很簡(jiǎn)潔，并且具有令人滿意的性質(zhì)：如果﹟1認(rèn)為自己吃了虧，那么只能責(zé)怪自己分割不均；如果﹟2認(rèn)為自己吃了虧，那么只能責(zé)怪自己挑選無(wú)方.

（2）二人協(xié)議是“我切你選”協(xié)議，它要求一位局中人能把這個(gè)蛋糕切分成2個(gè)對(duì)他來(lái)說(shuō)都可以接受的子蛋糕塊.也就是說(shuō)，至少有一位局中人具備這種切分能力，對(duì)二人協(xié)議來(lái)說(shuō)，這是一個(gè)前提（也稱基本假設(shè)）.本文在緊接著討論的3人、4人及更多人的無(wú)妒忌協(xié)議中，將上述基本假設(shè)加強(qiáng)為如下所述的基本假設(shè)A：給出一個(gè)蛋糕或其任意部分，給出任意一個(gè)正整數(shù)m，局中的每一位人都能充當(dāng)分割者，把這個(gè)蛋糕（或其任意部分）分割成m個(gè)對(duì)分割者來(lái)說(shuō)都可以接受的子蛋糕塊.

2塞爾弗里奇三人協(xié)議

下面緊接著敘述的這個(gè)協(xié)議抄錄自文[1].據(jù)文[1]介紹，這個(gè)協(xié)議是屬于約翰·塞爾弗里奇（John Selfridge）的，本文在這里只改動(dòng)了其中1處明顯的錯(cuò)誤.文[1]把局中人記為﹟1、﹟2、﹟3.

第一步：﹟1把蛋糕“三分天下”，分成對(duì)他來(lái)說(shuō)都可以接受的3個(gè)部分.endprint

有一只質(zhì)地均勻的蛋糕，要把它分給n個(gè)人，是否存在著一種方法能把這只蛋糕分得人人都心滿意足呢？這相當(dāng)于在問(wèn)：是否存在一種方法，使得這n個(gè)人中每個(gè)人都認(rèn)為自己所得的這部分是各人所得中最為理想的部分？這個(gè)問(wèn)題，還可敘述的更深入一些（也更繞口一些）：是否存在一種“將蛋糕切分成n個(gè)部分，并且使得參與分蛋糕的n個(gè)人中的每個(gè)人都對(duì)‘自己所分配到的蛋糕是所切分成的n個(gè)部分中的哪一個(gè)部分的態(tài)度是毫不在乎的”的方法？如果存在這樣的方法，我們把其中的分配稱為n人無(wú)妒忌分配，把導(dǎo)致這種分配的程序稱為n人無(wú)妒忌協(xié)議.

1二人無(wú)妒忌協(xié)議

把局中人記為﹟1、﹟2.由﹟1將蛋糕切分成兩部分，﹟2從中挑選他喜歡的部分.

評(píng)注（1）這種分配協(xié)議很簡(jiǎn)潔，并且具有令人滿意的性質(zhì)：如果﹟1認(rèn)為自己吃了虧，那么只能責(zé)怪自己分割不均；如果﹟2認(rèn)為自己吃了虧，那么只能責(zé)怪自己挑選無(wú)方.

（2）二人協(xié)議是“我切你選”協(xié)議，它要求一位局中人能把這個(gè)蛋糕切分成2個(gè)對(duì)他來(lái)說(shuō)都可以接受的子蛋糕塊.也就是說(shuō)，至少有一位局中人具備這種切分能力，對(duì)二人協(xié)議來(lái)說(shuō)，這是一個(gè)前提（也稱基本假設(shè)）.本文在緊接著討論的3人、4人及更多人的無(wú)妒忌協(xié)議中，將上述基本假設(shè)加強(qiáng)為如下所述的基本假設(shè)A：給出一個(gè)蛋糕或其任意部分，給出任意一個(gè)正整數(shù)m，局中的每一位人都能充當(dāng)分割者，把這個(gè)蛋糕（或其任意部分）分割成m個(gè)對(duì)分割者來(lái)說(shuō)都可以接受的子蛋糕塊.

2塞爾弗里奇三人協(xié)議

下面緊接著敘述的這個(gè)協(xié)議抄錄自文[1].據(jù)文[1]介紹，這個(gè)協(xié)議是屬于約翰·塞爾弗里奇（John Selfridge）的，本文在這里只改動(dòng)了其中1處明顯的錯(cuò)誤.文[1]把局中人記為﹟1、﹟2、﹟3.

第一步：﹟1把蛋糕“三分天下”，分成對(duì)他來(lái)說(shuō)都可以接受的3個(gè)部分.endprint