共同分担家务问题

        巴斯塔·琼斯夫妇新婚不久，各自都有固定的工作，所以一致同 意共同分担家务。

　　为了公平地安排家务，两人把每星期家里必须做的各项家务列成 一张表格。

　　巴斯塔对妻子说:"我已划出一半的项目，亲爱的，剩下的那些 家务该是你的了。"

　　珍妮特反对说:"不，巴斯塔，我认为你这样分配是不公平的， 你把脏活都推给我做，自己却拣轻松的事干。"

　　于是，琼斯夫人拿过了表格，把自己想做的家务事儆上记号。但 是，巴斯塔不同意。

　　正当他们争论不休的时候，门铃响了。进来的是琼斯夫人的母 亲，"两个宝贝在吵什么呀?我一走出电梯就听见你们在嚷嚷�"

　　琼斯夫人的母亲听完巴斯特和她女儿说出的原因之后，突然笑了起来，"我正好想出一个好办法，我告诉你们怎样分配家务。保证你 们两人都满意。"

　　史密斯夫人说:"你们中的一个把这张表格分成两部分，当然你 自己会乐于拿随便哪一份的。然后让第二个人挑取他 (她)最愿意要 的那一半。"

　　但是，一年之后当琼斯夫人的母亲搬进公寓来住的时候，事情就不那么简单了。琼斯夫人的母亲同意承担三分之一的家务劳动，但是 他们无法决定如何在三个人当中公平地分配家务。你能给他们提出分 配方案吗?

--------------------------------------------------------------------------------------------------------------------------------------------

        本题实际上是讲合理分配问题。合理分配问题一般是用两个人分一只烧饼的形式出现的，要把烧饼分给两个人，使得参加分配的每个人都满意地认为自己至少得到半只饼。

　　把一只烧饼分成三份，可以这样来解决:一个人拿一把较大的刀在烧饼上方慢慢移动，烧饼可以是任何一种形状，但是刀一定要这么 移动，使某一边的烧饼量从零逐渐增加到最大。当这三个人中任何一个人认为这把刀处的位置正好使切下第一片的烧饼等于整块烧饼的 1/3时，他 (她)就喊，"切!"，这时刀马上切下，喊叫的那个人就拿这一份烧饼。由于他 (她)已满意地觉得自己得到了1/3，就退出以后 的分配。如果两个人或三个人同时喊"切"的话，则切下的那一份烧饼随便给谁都一样。

　　其他两个人当然满意地觉得剩下的至少有2/3，这样问题就还原到上例讲的那种情况了，只要一个人切，另一个人选，烧饼便可公平 地分掉。

        很显然，可以推广到N个人。随着刀子在烧饼上方移动，第一个喊 "切"的人拿第一次切下的那块饼 (或者把这块饼同时给喊 "切"的几个人当中的任何一个人)。然后其余N-1个人重复以上步 骤，这样一直进行下去，直到剩下两个人。最后剩的烧饼，两人可以 像上例讲的办法那样来分，也可以继续用刀移动的办法来分。这个一般化的解题方法是用数学归纳来证明算法的一个很好范例，很容易看 出，这种算法如何能应用于把一系列家务事分摊给几个人，并使得人人感到满意，觉得他分担的家务是公平合理的。