分蛋糕的无妒忌协议

蔡历亮

有一只质地均匀的蛋糕，要把它分给n个人，是否存在着一种方法能把这只蛋糕分得人人都心满意足呢？这相当于在问：是否存在一种方法，使得这n个人中每个人都认为自己所得的这部分是各人所得中最为理想的部分？这个问题，还可叙述的更深入一些（也更绕口一些）：是否存在一种“将蛋糕切分成n个部分，并且使得参与分蛋糕的n个人中的每个人都对‘自己所分配到的蛋糕是所切分成的n个部分中的哪一个部分的态度是毫不在乎的”的方法？如果存在这样的方法，我们把其中的分配称为n人无妒忌分配，把导致这种分配的程序称为n人无妒忌协议.

1二人无妒忌协议

把局中人记为﹟1、﹟2.由﹟1将蛋糕切分成两部分，﹟2从中挑选他喜欢的部分.

评注（1）这种分配协议很简洁，并且具有令人满意的性质：如果﹟1认为自己吃了亏，那么只能责怪自己分割不均；如果﹟2认为自己吃了亏，那么只能责怪自己挑选无方.

（2）二人协议是“我切你选”协议，它要求一位局中人能把这个蛋糕切分成2个对他来说都可以接受的子蛋糕块.也就是说，至少有一位局中人具备这种切分能力，对二人协议来说，这是一个前提（也称基本假设）.本文在紧接着讨论的3人、4人及更多人的无妒忌协议中，将上述基本假设加强为如下所述的基本假设A：给出一个蛋糕或其任意部分，给出任意一个正整数m，局中的每一位人都能充当分割者，把这个蛋糕（或其任意部分）分割成m个对分割者来说都可以接受的子蛋糕块.

2塞尔弗里奇三人协议

下面紧接着叙述的这个协议抄录自文[1].据文[1]介绍，这个协议是属于约翰·塞尔弗里奇（John Selfridge）的，本文在这里只改动了其中1处明显的错误.文[1]把局中人记为﹟1、﹟2、﹟3.

第一步：﹟1把蛋糕“三分天下”，分成对他来说都可以接受的3个部分.endprint

有一只质地均匀的蛋糕，要把它分给n个人，是否存在着一种方法能把这只蛋糕分得人人都心满意足呢？这相当于在问：是否存在一种方法，使得这n个人中每个人都认为自己所得的这部分是各人所得中最为理想的部分？这个问题，还可叙述的更深入一些（也更绕口一些）：是否存在一种“将蛋糕切分成n个部分，并且使得参与分蛋糕的n个人中的每个人都对‘自己所分配到的蛋糕是所切分成的n个部分中的哪一个部分的态度是毫不在乎的”的方法？如果存在这样的方法，我们把其中的分配称为n人无妒忌分配，把导致这种分配的程序称为n人无妒忌协议.

1二人无妒忌协议

把局中人记为﹟1、﹟2.由﹟1将蛋糕切分成两部分，﹟2从中挑选他喜欢的部分.

评注（1）这种分配协议很简洁，并且具有令人满意的性质：如果﹟1认为自己吃了亏，那么只能责怪自己分割不均；如果﹟2认为自己吃了亏，那么只能责怪自己挑选无方.

（2）二人协议是“我切你选”协议，它要求一位局中人能把这个蛋糕切分成2个对他来说都可以接受的子蛋糕块.也就是说，至少有一位局中人具备这种切分能力，对二人协议来说，这是一个前提（也称基本假设）.本文在紧接着讨论的3人、4人及更多人的无妒忌协议中，将上述基本假设加强为如下所述的基本假设A：给出一个蛋糕或其任意部分，给出任意一个正整数m，局中的每一位人都能充当分割者，把这个蛋糕（或其任意部分）分割成m个对分割者来说都可以接受的子蛋糕块.

2塞尔弗里奇三人协议

下面紧接着叙述的这个协议抄录自文[1].据文[1]介绍，这个协议是属于约翰·塞尔弗里奇（John Selfridge）的，本文在这里只改动了其中1处明显的错误.文[1]把局中人记为﹟1、﹟2、﹟3.

第一步：﹟1把蛋糕“三分天下”，分成对他来说都可以接受的3个部分.endprint

有一只质地均匀的蛋糕，要把它分给n个人，是否存在着一种方法能把这只蛋糕分得人人都心满意足呢？这相当于在问：是否存在一种方法，使得这n个人中每个人都认为自己所得的这部分是各人所得中最为理想的部分？这个问题，还可叙述的更深入一些（也更绕口一些）：是否存在一种“将蛋糕切分成n个部分，并且使得参与分蛋糕的n个人中的每个人都对‘自己所分配到的蛋糕是所切分成的n个部分中的哪一个部分的态度是毫不在乎的”的方法？如果存在这样的方法，我们把其中的分配称为n人无妒忌分配，把导致这种分配的程序称为n人无妒忌协议.

1二人无妒忌协议

把局中人记为﹟1、﹟2.由﹟1将蛋糕切分成两部分，﹟2从中挑选他喜欢的部分.

评注（1）这种分配协议很简洁，并且具有令人满意的性质：如果﹟1认为自己吃了亏，那么只能责怪自己分割不均；如果﹟2认为自己吃了亏，那么只能责怪自己挑选无方.

（2）二人协议是“我切你选”协议，它要求一位局中人能把这个蛋糕切分成2个对他来说都可以接受的子蛋糕块.也就是说，至少有一位局中人具备这种切分能力，对二人协议来说，这是一个前提（也称基本假设）.本文在紧接着讨论的3人、4人及更多人的无妒忌协议中，将上述基本假设加强为如下所述的基本假设A：给出一个蛋糕或其任意部分，给出任意一个正整数m，局中的每一位人都能充当分割者，把这个蛋糕（或其任意部分）分割成m个对分割者来说都可以接受的子蛋糕块.

2塞尔弗里奇三人协议

下面紧接着叙述的这个协议抄录自文[1].据文[1]介绍，这个协议是属于约翰·塞尔弗里奇（John Selfridge）的，本文在这里只改动了其中1处明显的错误.文[1]把局中人记为﹟1、﹟2、﹟3.

第一步：﹟1把蛋糕“三分天下”，分成对他来说都可以接受的3个部分.endprint