科学网 › 标签 › 抽屉原理

标签: 抽屉原理

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

六人集会问题: 热度 6 xying 2013-2-4 08:52; 好的智力游戏，挑战的是智力而不是知识，简单直观有确定的答案，但有一定的难度。问题的解决，不仅有征服高峰的快感，还常有开拓眼界的收获。上一个帖子“称球问题”就属于这一类。我这里再出一道题。为了让大家有收获，先给一个思路。我所学的许多知识中大约最直观的就是“ 抽屉原理 ”【 1 】了。它是组合数学的一个基本原理，最先是由德国数学家狄利克雷明确地提出来的，因此，也称为狄利克雷原理。这原理形象的说法是：将 10 个苹果放在 9 个抽屉，至少有一个抽屉会有 2 个或以上的苹果。如此等等，总之傻子都能明白的道理。把苹果换成鸽子，这原理也就叫“鸽巢原理”了。其实我在上面称球问题【 2 】的定理证明【 3 】中就几次用到抽屉原理，用决策树分析区分球的上限时也用过。只不过不说，人人也不打磕地通过了。这抽屉原理，用信息也能给出个解释，不过组合数学觉得用集合论就能说明白，就不用它来包装了。抽屉原理如果没有个不寻常的应用，那也没人会认这个账，早让奥卡姆的剃刀给切去了。下面题目，给大家一个验证的机会。 1958 年 6/7 月号的《美国数学月刊》上有这样一道题目：证明在任意 6 人的集会上，有 3 个人以前彼此都相识，或者有 3 个人以前彼此不相识，这两者必居其一。这道题的数目有限，自然可以用枚举法证明。但用抽屉原理，几句话就能说清，你知道该怎么证明吗？别看这道题简单，六人集会问题是组合数学中著名的拉姆塞定理的一个简单特例，它的思路可以得出另一些深入的结论。它们构成了组合数学中的“ 拉姆塞理论 ”【 4 】。 ××××× 你想出证明了吗？要是没有，下面是证明。在 6 人中任选一人（称为主人），他与其他 5 人的关系可以分成两类：认识的和不认识的。 5 人分 2 类，至少有一类是 3 人以上（抽屉原理）。假设主人认识的至少有 3 人，这 3 人如果互相全不认识，就满足问题中后一条件。否则，至少有两人认识，再加上主人，就有了互相认识的 3 个人，满足前一条件。因此，两条件必居其一。假设不认识的起码有 3 人，将前一假设论中“认识”与“不认识”的文字互换，完全对称地可以证明了结论。证毕。不过瘾，是不是？再出道题给大家思考。一个聚会中，大家见面握手。有人热情，有人冷淡，不见得都握的一样多。证明一定有两个人与一样多数量的人握了手。可能有讲究数学严谨性的人说：这题目不成立！反证法：要是聚会只有主人一个人，其他都没来，怎么有两个人握手的次数一样？ Q. E. D. 很幽默吧。在分 13 球的讨论中，也有类似的评论。有人说：这些球是玻色子，所以所有的那些解法都不成立，这提法还附有深入浅出的穷举法反证，以示严谨。我起先以为有人把四月一日的帖子发早了，后来见一再提醒大家，且有博文把问题“重新准确描述：有十三个球大小颜色形状完全相同，”还真叫人语塞。我更郁闷的是：这么多年，这么多人都兴致勃勃，绞尽脑汁地奔着这难题想，莫非还真有聪明人叫破了：“这是忽悠小孩子的皇帝新衣”？研读了一下，发现除了“玻色子”这词对小朋友有点难度外，这提法还真是善待小孩了。查了物理大辞典，“玻色子”在这儿的意思是：这些球外表不可区分，也就是说你把它们混着搁在一堆里，就认不出不同的出处了，所以别费心思在一堆里做什么组合。把这意思告诉小朋友，还真是个个雀跃，齐声说：以前都被忽悠了！为什么？好解了呀！ 13 个玻色子球，就有那么少数几个分堆的法子，不费脑筋考虑各种组合的效益，小朋友用穷举试几次也发现了 3 次是不可能分出次品。给自己压任务，琢磨称 4 次， 4 、 4 、 5 三堆一分，太容易了。实际上称 4 次都能分 31 个玻色子球，你让他分 13 个，差生都得满分。太没有挑战性了，这也叫智力题？难怪大人都不理会什么玻色子解释了。把分 13 球，或者 12 球的问题换成从玻色子球里挑出一个次品，除了这名词比较牛以外，真是没什么技术含量。把好好的一个挑战智力的问题变成乏味的儿童题。那是缺乏做事的常识了。其实真要别出机枢，在网上想整出点动静来，也不是没办法，比如说玩一篇从玻色子球中找出一个次品的通解。你看哈，既然在一堆里不能区分哪个从哪里来，那就别费心思颠来换去地组合，光考虑数量就行了。如果已经知道了次品是轻还是重，称 k 次可分 3**k （ 3 的 k 次方）球。如果未知轻重但外边有足够的正品球，称 k 次可分（ 3**k - 1 ） /2 个球而且知道了次品的轻重。证明？用数学归纳法， k=1 没问题；将 3**(k-1) 个球与正品球上天平比较，如果不平衡就知道了次品在这儿也知道它的轻重，再称 k-1 可解决；如果平衡，再称 k-1 次可解决天平外的（ 3** （ k-1 ） - 1 ） /2 个，加起来就对了。注意到这也同时分辨出次品的轻重。如果不求这轻重，再多搁一个在外边也成。好了，现在从不知次品轻重也没有正品球的起点开始，考虑怎么称 k 次。一开始把球分 3 堆，把两堆 3**(k-2) 个球上天平，如果不平衡，确定了外边是正品球，数出 3**(k-2) 个球把在天平上右边那些球换下来，再称，就能判断出次品是在原来天平哪一边了，而且知道次品是轻了还是重了。由上面分析可知，这样再称 k-2 次就能在这些球中判断出次品，且知轻重。第一次称时天平外有多少？（ 3** （ k-1 ） - 1 ） /2 个。如果第一次天平平衡，知道天平里都是正品了，用这些量外边这些球，由上面分析可知，称 k-1 可解决。注意到无论天平平衡不平衡，我们手里都是有充分的正品球。把这些数加起来，一共是 3** （ k-1 ） + （ 3** （ k-2 ） -1 ） /2 个，如果不要求判断次品的轻重，还能多出一个。这样称 2 、 3 、 4 、 5 次，可分 3 、 10 、 31 、 94 个玻色球，并知道次品轻重。或对不在乎次品轻重的能分 4 、 11 、 32 、 95 个。这是结构性证明，读了就知道该怎么操作了。。。这通解虽然没什么难度，如果用它垫底，再侃些什么玻色子球，借已有定论的东西炒作一下，马马虎虎算是沾着点技术含量，写反调文章才比口水帖强。玩游戏读文章做研究时，如果其中有歧义，聪明的人都会往有意义的方向想，而不会将它平庸化。这在玩游戏时是如此，做研究读论文时更应该如此。我在念研究生时，有个学弟，读到很经典论文证明中的一处错误，兴奋得不能自已。大家听了动静过来瞄一眼，都不吱声走开。我看久了实在不忍心，对他说：“这明显是一处笔误，大家最多只愣几分钟都顺过去了，就你还停在这儿。” 好了，大家也别停在这儿，那聚会握手题会解吗？会的，写个再罗嗦也不得超过 150 字的证明到评论里。【参考资料】【1】百度百科，抽屉原理 http://baike.baidu.com/view/8899.htm 【2】科学网博文，称球问题 http://blog.sciencenet.cn/home.php?mod=spaceuid=826653do=blogid=657778 【3】科学网博文，称球问题的通解 http://blog.sciencenet.cn/home.php?mod=spaceuid=826653do=blogid=658533 【4】维基百科，拉姆齐定理 http://zh.wikipedia.org/wiki/%E6%8B%89%E5%A7%86%E9%BD%90%E5%AE%9A%E7%90%86; 个人分类: 智力|15776 次阅读|12 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 抽屉原理

相关帖子

相关日志

关闭安全验证