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