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

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

The King Auther and Merlin II

 

秦序网 摘录

 
    2016-8-3 22:28:39
Some time elapsed and the king noticed that at the dinners served for the 150 knights at the famous round table, neighbors often quarrelled and even fought. Arthur found this bad  for  the digestion and  so  once again he summoned Merlin and ordered him to find a way to seat the 150 knights around the table  so  that each  of  them should sit between two friends. Again, using his Supernatural powers Merlin saw immediately that none of the 149! seatings would do, and this he reported to the king. Again, the king bade him find one  or  explain why it was impossible. “Oh I  wish there were some simple reason  I  could give to you! With some luck there could be  a  knight having only one friend, and  so  you too could see immediately that what you demand from me is impossible. But alas!, there is no such simple reason here, and I cannot explain to you mortals why no such seating exists, unless you are ready to spend the rest  of  your life listening to my arguments!” The king was naturally unwilling to do that and  so  Merlin has lived imprisoned in  a  cave ever since.  (A  severe loss for applied mathematics!)
翻译仅供参考,如有不当之处欢迎斧正
过去了一段时间,亚瑟王在著名的圆桌招待这150个骑士的宴会上发现,相邻的骑士总是争吵甚至打起来。亚瑟发现这使得食欲不佳,就如同上次一样又一次召见墨林命他找出一种座位安排方式,让这150个骑士围着圆桌坐而且相邻的都是朋友。再一次,墨林使用超能力马上发现$149!$种可能的坐法中没有一种满足要求,由此他禀告亚瑟王。和上次一样,亚瑟王令他要么找出一种坐法,要么解释为何不存在。“噢,我多想给你简单的理由!如果幸运地,有个骑士只有一个朋友,那样您就能立马发现您我的命令是不可能办到的。但是哎呀,是没有和上次一样简单的理由,我也没法给你解释没有如此的坐法,除非你准备用余生听我的论证!”亚瑟王自然不愿意那样做,墨林从此也就被禁锢在一个山洞中了。(应用数学的一大损失!)
************************************************
这个问题本质上是一个图论中Hamilton圈的存在性问题,是一个NP-困难问题,到目前为止没有好算法。自然Merlin也没法在很短时间内给出完全的解释。
Reference Lovász, L., Plummer, M. D. Matching theory. 1986 edit
0
前一则: The King Auther and Merlin I 后一则: 楼高几何可穷千里
华罗庚
陈景润
关于秦序 | 联系秦序 | JaxEdit 珂齋 西土居
本站部分资料来自互联网和共享资源,版权归原作者及机构拥有,如发现侵犯了您的相关权益,请及时联系处理。
本站所有非原创资料仅供学习研究之用,未经原作者同意,不得私自用于商业目的,否则自行承担由此所产生的一切法律责任。
版权声明:凡注明来源为本站的任何作品,本站保留所有权利,未经同意不得用于商业用途,转载时请注明本站链接。
Copyright © 2015-2017 QINXU  All Rights Reserved  陇ICP备15001363号-2  版权所有 © 秦序网