加入收藏    
秦序 珂斋 旗下专注于高中数学教育之 秦序网 欢迎各位莅临! 珂齋 西土居

高考真题 | 方法技巧 | 资讯 | 教学案 | 课件 | 检测题 | 教学探究 | 数学趣闻 | 家教

The King Auther and Merlin I

 

秦序网 摘录

 
    2016-8-3 22:22:43
In the court of King Arthur there dwelt 150 knights and 150 ladies-in-waiting. The king decided to marry them  off,  but the trouble was that some pairs hated each other  so  much that they would not even get married, let alone speak! King Arthur tried several times to pair them  off  but each time he ran into conflicts.  So  he summoned Merlin the Wizard and ordered him to find a pairing in which every pair was willing to marry. Now Merlin had supernatural powers and he saw immediately that none of the 150! possible pairings was feasible, and this he told the king. But Merlin was not only  a  great wizard, but  a  suspicious character as well, and King Arthur did not quite trust him. “Find a pairing  or I shall sentence you to be imprisoned in  a  cave forever!” said Arthur. Fortunately for Merlin, he could use his supernatural powers to find the reason why such a pairing could not-exist. He asked  a  certain 56 ladies to stand on one side of the king and 95 knights on the other side, and asked: “Is any one of you ladies, willing to marry any of these knights?”, and when all said “No!”, Merlin said: “O King, how can you command me to find a husband for each of these 56 ladies among the remaining 55 knights?”  So the king, whose courtly education did include the pigeonhole principle, saw that in this case Merlin had spoken the truth and he graciously dismissed him.
翻译仅供参考,如有不当之处欢迎斧正
在亚瑟王的宫廷中有150个骑士和150个侍女。亚瑟王决定让他们结婚,但问题是有很多对由于相互讨厌到宁可一个人过也不愿意和对方结婚。亚瑟王试了几次但每次都有麻烦,因此他召见巫师墨林并命令他找出一种能够使双方都愿意结婚的配对方式。因为墨林并不仅仅是一个巫师,而还有可以的能力,且亚瑟王并不相当信任他。亚瑟说:“找出一种配对方式,否则我将把你永远囚禁在山洞里!”幸运的是,墨林能用他的超自然能力发现为何不存在这样的配对的原因。他找了特定的56个侍女站在国王的一边,95个骑士在另一边,然后问这些侍女:“你们有人愿意嫁给这些其实中的一个吗?”,等到所有的侍女都说“不愿意!”时,莫林说:“噢,国王,你怎么能命令我在剩下的55名骑士中给这56个侍女每一个找一个丈夫呢?”尽管国王的典雅教育没包括鸽笼原理(抽屉原理),但还是觉察到墨林说的是真理,然后大方地免了对墨林的处罚。
*************************************************
这是一个图论中的匹配存在性问题,相对容易理解如果要一一配对,至少可选择数字不能少于自身(P. Hall定理有严格标准的描述)。如同这里的56个侍女,可选的骑士只有55个,那根据抽屉原理(鸽笼原理 detail.asp?id=3)至少有一个侍女找不到心仪的丈夫。
Reference Lovasz, L., Plummer, M. D. Matching theory. 1986 edit
0
前一则: 抽屉原理 (鸽笼原理) 后一则: The King Auther and Merlin II
华罗庚
陈景润
关于秦序 | 联系秦序 | JaxEdit 珂齋 西土居
本站部分资料来自互联网和共享资源,版权归原作者及机构拥有,如发现侵犯了您的相关权益,请及时联系处理。
本站所有非原创资料仅供学习研究之用,未经原作者同意,不得私自用于商业目的,否则自行承担由此所产生的一切法律责任。
版权声明:凡注明来源为本站的任何作品,本站保留所有权利,未经同意不得用于商业用途,转载时请注明本站链接。
Copyright © 2015-2017 QINXU  All Rights Reserved  陇ICP备15001363号-2  版权所有 © 秦序网