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

蔡歷亮

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

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

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

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

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

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

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

第一步：﹟1把蛋糕“三分天下”，分成對他來說都可以接受的3個部分.endprint

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

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

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

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

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

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

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

第一步：﹟1把蛋糕“三分天下”，分成對他來說都可以接受的3個部分.endprint

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

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

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

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

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

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

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

第一步：﹟1把蛋糕“三分天下”，分成對他來說都可以接受的3個部分.endprint