论文部分内容阅读
两人分饼吵
很久很久以前，有个地主，雇着两个长工。这两个长工每个月打一架，力气都用在口角上了。地主很郁闷，后来发现起因都在自己。原来，为了激发老王和老李干活的动力，地主每个月月底给每人发一个芝麻饼。可不是老王觉得自己的饼小了就是老李觉得对方的饼大了，地主大喝：“两个一样大！老子什么时候对你们不公平了？”一阵沉默后，两人继续打。
唉，骂归骂，别人碗里的肉总是比较大，身为地主怎么会不明白这个道理呢。于是他决定改变策略。饼还是照发，不过这次他买了一大号的，由老王和老李自己来分。地主说：“你们一个人切，由另一个人来挑。”老李笑着把刀递给老王，心想挑份大的还不简单么。经常打输的老王不得已接过刀，恨恨地想，可不能便宜了这小子，一定得切出差不多的两份来！切好了，老李绕着桌子瞧了个360度。嗯，一块稍微大那么一丁点儿，可是另一块的芝麻却也多出那么一丁点儿。老王在一旁暗笑，挑呗，怎么挑都是一样的。最后老李捡走了芝麻多的，老王也乐得拿块大的，俩人都觉得没吃亏。
地主很得意。这个办法真是好。2虽然等于1加1，可世界上从来没有两块一模一样的饼。自己当老大想把一碗水端平，在别人看来不一定就端平了。这回把决策权给他们自己，饼也许并没有真正分匀，却消除了争吵，让双方都满意。还有比这双赢更好的对策么？
可事情并不总是那么简单的。吃饱了的长工们干活很卖力，把邻村地主气坏了。他嫌自己的长工老高不够勤快，直接炒了鱿鱼。老高郁闷地背着铺盖卷，跑到这边来投奔。地主家这回有三个工人了。
三人分饼愁
月底的时候，地主想买个大一号的饼，给他们三个人分。才走到半路呢，忽然犯了愁：切和挑的顺序该怎么定呢？如果一个人切，两个人挑，切的人肯定不在乎得到哪一份，因为他会努力切出自己觉得一样大的三块。问题在于，如果另两个人都看中了同一块的话，后挑的就会不满意了，妈呀，又打架……地主在路边坐下来，考虑另一种方案：切的人拿走别人都不要的一块，反正他不在乎；剩下的两块拼在一起，重新分配，一人切一人挑。怎么样？还是不行。虽然第一次切的人拿走他那块时，觉得三块一样大，可剩下的被重新分了以后，他会觉得其中一份比自己手里的大了。打架看来是不可避免的。
地主抱着头坐在路边想呀想。太阳出来了，太阳西沉了，月亮出来了，月亮西沉了……似乎切啊挑啊，总有人不满意。东方露出了鱼肚白，天空像被万道霞光切成无数片的大蛋糕——咦，有了！咱扔掉一块就解决问题啦！他跳起来，揉着红肿的眼睛，朝烧饼店轻快地跑去……
来到长工的窝棚，地主煞有介事地说道：“这块大饼给你们三个人分。都给我听仔细了，看看自己为什么只能当长工，而我可以当地主。”
他的方案是这样的：新来的老高掌刀，把饼先切成自己觉得均匀的三块。老王和老李各自指出自己想要的那块。如果两人各有所爱，就各取所需，剩下那块归老高，问题就解决了，谁也不眼红谁。如果老王和老李都看中了同一块，就进行下一步：由其中一人掌刀（假设是老李，换成老王也一样类推），把这一块切去一点，直到自己觉得它和第二大的那块不相上下。把切掉的部分放到一边，然后由老王从三块中挑。接下来老李挑，剩下的归老高。有点烦琐，可是这样保证了公平：首先，老王不眼红任何人，他先挑的；老李也不眼红，因为他眼中有两块一样大，而且都比第三块大。那么不论老王挑走哪块，他都有机会拿到两大块中的一块；最妙的是老高也不会眼红。因为剩给他的肯定不是被切过的那块，而最初的三块在他眼里本来是一样的。那么切了的那块尽管在别人眼里是大的，在他看来却比自己手里的小。哈哈，地主好得意啊，不仅使三个长工都各自满意，还有切出来的一小点可以给自己当零食。
人手又多干劲又足，地主家成了优秀管理的典型，县令都亲自坐轿前来观摩。听罢主人的自夸，芝麻官笑了。他一边摆弄着那块切下来的边角料，一边捻着胡子说：“你这不是还有一小部分没分完吗？他们聪明点的话说你克扣工钱，怎么办？”地主一愣：“可是，如果用同样的分法来分这一小部分，不是有更小的一块剩下来吗？那不是分起来没完没了了？”
县太爷分饼妙
县令的办法是这样的：假设刚才被切了两刀的饼最后归了老李（归老王的话可以类推），就让老王来把这剩下的一块切成三份，然后规定挑的顺序为老李，老高，老王。这就保证了每个人都满意。为什么呢？首先老李先挑，他没啥好抱怨。老高呢，本来就觉得老李上次那块比自己的小，剩下的全给他也不吃亏；老王那块和自己的差不多，但可以在他之前挑，因此也不用眼红老王。最后老王也不眼红他们，因为是他掌的刀。地主听得下巴都快掉了，晕晕乎乎送走了县太爷。回家仔细想了一遍，这逻辑确实高明。
从此地主家成了方圆百里之内有名的科学管理户，并于年底被选为县代表送去京城进修。进修班里圣上亲自驾到御授了一堂课，听得地主直拍大腿：“果然是天子，吾等草包顶多做到芝麻官儿了！”
皇上说啥了呢？皇上说，你们别看切饼分配像是为了防止人类的嫉妒心而搞出来的权宜之策，那都是数学！对，不是心理学、社会学，是数学！一系列的推理中蕴涵着逻辑，而逻辑可以化为符号式的语言。比如用三个点表示三个人，另外三个点表示三块饼，谁拿哪块饼就把两个点用线段连起来。整个问题就被抽象成了一些节点和边构成的网络图。这叫啥？这叫图论。图论是离散数学的一个分支，利用人们已经发现的定理，就能对“分饼图”进行推导，证明有没有让大家都满意的最佳方案。
地主充满崇拜地问：“皇上您圣明，可我咋还是不太明白呢？咋就把那么长的推理变成了点和线？还证明？”皇上龙颜不悦地皱了皱眉头：“你以为我啥都知道啊？这不是洋人弄出来的玩意儿嘛！”
链接
“公平分配“是现代数学中赛局理论研究的重要问题之一。而“分饼”所代表的一类案例属于公平分配中的“切蛋糕算法”范畴。文中提到的三人分饼法在20世纪60年代由两位数学家Selfridge和Conway各自独立发现，并由后继研究者推广到任意n人公平分配。如果在问题中加入各种条件，就能衍生出更加复杂而又有趣的新问题。
很久很久以前，有个地主，雇着两个长工。这两个长工每个月打一架，力气都用在口角上了。地主很郁闷，后来发现起因都在自己。原来，为了激发老王和老李干活的动力，地主每个月月底给每人发一个芝麻饼。可不是老王觉得自己的饼小了就是老李觉得对方的饼大了，地主大喝：“两个一样大！老子什么时候对你们不公平了？”一阵沉默后，两人继续打。
唉，骂归骂，别人碗里的肉总是比较大，身为地主怎么会不明白这个道理呢。于是他决定改变策略。饼还是照发，不过这次他买了一大号的，由老王和老李自己来分。地主说：“你们一个人切，由另一个人来挑。”老李笑着把刀递给老王，心想挑份大的还不简单么。经常打输的老王不得已接过刀，恨恨地想，可不能便宜了这小子，一定得切出差不多的两份来！切好了，老李绕着桌子瞧了个360度。嗯，一块稍微大那么一丁点儿，可是另一块的芝麻却也多出那么一丁点儿。老王在一旁暗笑，挑呗，怎么挑都是一样的。最后老李捡走了芝麻多的，老王也乐得拿块大的，俩人都觉得没吃亏。
地主很得意。这个办法真是好。2虽然等于1加1，可世界上从来没有两块一模一样的饼。自己当老大想把一碗水端平，在别人看来不一定就端平了。这回把决策权给他们自己，饼也许并没有真正分匀，却消除了争吵，让双方都满意。还有比这双赢更好的对策么？
可事情并不总是那么简单的。吃饱了的长工们干活很卖力，把邻村地主气坏了。他嫌自己的长工老高不够勤快，直接炒了鱿鱼。老高郁闷地背着铺盖卷，跑到这边来投奔。地主家这回有三个工人了。
三人分饼愁
月底的时候，地主想买个大一号的饼，给他们三个人分。才走到半路呢，忽然犯了愁：切和挑的顺序该怎么定呢？如果一个人切，两个人挑，切的人肯定不在乎得到哪一份，因为他会努力切出自己觉得一样大的三块。问题在于，如果另两个人都看中了同一块的话，后挑的就会不满意了，妈呀，又打架……地主在路边坐下来，考虑另一种方案：切的人拿走别人都不要的一块，反正他不在乎；剩下的两块拼在一起，重新分配，一人切一人挑。怎么样？还是不行。虽然第一次切的人拿走他那块时，觉得三块一样大，可剩下的被重新分了以后，他会觉得其中一份比自己手里的大了。打架看来是不可避免的。
地主抱着头坐在路边想呀想。太阳出来了，太阳西沉了，月亮出来了，月亮西沉了……似乎切啊挑啊，总有人不满意。东方露出了鱼肚白，天空像被万道霞光切成无数片的大蛋糕——咦，有了！咱扔掉一块就解决问题啦！他跳起来，揉着红肿的眼睛，朝烧饼店轻快地跑去……
来到长工的窝棚，地主煞有介事地说道：“这块大饼给你们三个人分。都给我听仔细了，看看自己为什么只能当长工，而我可以当地主。”
他的方案是这样的：新来的老高掌刀，把饼先切成自己觉得均匀的三块。老王和老李各自指出自己想要的那块。如果两人各有所爱，就各取所需，剩下那块归老高，问题就解决了，谁也不眼红谁。如果老王和老李都看中了同一块，就进行下一步：由其中一人掌刀（假设是老李，换成老王也一样类推），把这一块切去一点，直到自己觉得它和第二大的那块不相上下。把切掉的部分放到一边，然后由老王从三块中挑。接下来老李挑，剩下的归老高。有点烦琐，可是这样保证了公平：首先，老王不眼红任何人，他先挑的；老李也不眼红，因为他眼中有两块一样大，而且都比第三块大。那么不论老王挑走哪块，他都有机会拿到两大块中的一块；最妙的是老高也不会眼红。因为剩给他的肯定不是被切过的那块，而最初的三块在他眼里本来是一样的。那么切了的那块尽管在别人眼里是大的，在他看来却比自己手里的小。哈哈，地主好得意啊，不仅使三个长工都各自满意，还有切出来的一小点可以给自己当零食。
人手又多干劲又足，地主家成了优秀管理的典型，县令都亲自坐轿前来观摩。听罢主人的自夸，芝麻官笑了。他一边摆弄着那块切下来的边角料，一边捻着胡子说：“你这不是还有一小部分没分完吗？他们聪明点的话说你克扣工钱，怎么办？”地主一愣：“可是，如果用同样的分法来分这一小部分，不是有更小的一块剩下来吗？那不是分起来没完没了了？”
县太爷分饼妙
县令的办法是这样的：假设刚才被切了两刀的饼最后归了老李（归老王的话可以类推），就让老王来把这剩下的一块切成三份，然后规定挑的顺序为老李，老高，老王。这就保证了每个人都满意。为什么呢？首先老李先挑，他没啥好抱怨。老高呢，本来就觉得老李上次那块比自己的小，剩下的全给他也不吃亏；老王那块和自己的差不多，但可以在他之前挑，因此也不用眼红老王。最后老王也不眼红他们，因为是他掌的刀。地主听得下巴都快掉了，晕晕乎乎送走了县太爷。回家仔细想了一遍，这逻辑确实高明。
从此地主家成了方圆百里之内有名的科学管理户，并于年底被选为县代表送去京城进修。进修班里圣上亲自驾到御授了一堂课，听得地主直拍大腿：“果然是天子，吾等草包顶多做到芝麻官儿了！”
皇上说啥了呢？皇上说，你们别看切饼分配像是为了防止人类的嫉妒心而搞出来的权宜之策，那都是数学！对，不是心理学、社会学，是数学！一系列的推理中蕴涵着逻辑，而逻辑可以化为符号式的语言。比如用三个点表示三个人，另外三个点表示三块饼，谁拿哪块饼就把两个点用线段连起来。整个问题就被抽象成了一些节点和边构成的网络图。这叫啥？这叫图论。图论是离散数学的一个分支，利用人们已经发现的定理，就能对“分饼图”进行推导，证明有没有让大家都满意的最佳方案。
地主充满崇拜地问：“皇上您圣明，可我咋还是不太明白呢？咋就把那么长的推理变成了点和线？还证明？”皇上龙颜不悦地皱了皱眉头：“你以为我啥都知道啊？这不是洋人弄出来的玩意儿嘛！”
链接
“公平分配“是现代数学中赛局理论研究的重要问题之一。而“分饼”所代表的一类案例属于公平分配中的“切蛋糕算法”范畴。文中提到的三人分饼法在20世纪60年代由两位数学家Selfridge和Conway各自独立发现，并由后继研究者推广到任意n人公平分配。如果在问题中加入各种条件，就能衍生出更加复杂而又有趣的新问题。