网站首页 用户注册 用户登录 网站地图
交流讨论区
资料交流区
学校展示区
 
语文   数学   英语   物理   化学   政治   生物   历史   地理   体育与健康   艺术教育   信息技术
 
数学频道首页   教学参考   课程资源   在线题库   竞赛园地   互动天地   数学史料   课外数学   小学数学
 

你的位置>中基网首页>数学频道首页>课外数学
打印  送给朋友  网友讨论 2002-8-15 阅读次数:2376 

抽屉原理和六人集会问题

“任意367个人中,必有生日相同的人。”
  “从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
  “从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”

  ... ...
  大家都会认为上面所述结论是正确的。这些结论是依据什么原理得出的呢?这个原理叫做抽屉原理。它的内容可以用形象的语言表述为:
  “把m个东西任意分放进n个空抽屉里(m>n),那么一定有一个抽屉中放进了至少2个东西。”
  在上面的第一个结论中,由于一年最多有366天,因此在367人中至少有2人出生在同月同日。这相当于把367个东西放入 366个抽屉,至少有 2个东西在同一抽屉里。在第二个结论中,不妨想象将5双手套分别编号,即号码为1,2,...,5的手套各有两只,同号的两只是一双。任取6只手套,它们的编号至多有5种,因此其中至少有两只的号码相同。这相当于把6个东西放入5个抽屉,至少有2个东西在同一抽屉里。
  抽屉原理的一种更一般的表述为:
 “把多于kn个东西任意分放进n个空抽屉(k是正整数),那么一定有一个抽屉中放进了至少k+1个东西。”
  利用上述原理容易证明:“任意7个整数中,至少有3个数的两两之差是3的倍数。”因为任一整数除以3时余数只有0、1、2三种可能,所以7个整数中至少有3个数除以3所得余数相同,即它们两两之差是3的倍数。
  如果问题所讨论的对象有无限多个,抽屉原理还有另一种表述:
  “把无限多个东西任意分放进n个空抽屉(n是自然数),那么一定有一个抽屉中放进了无限多个东西。”
  抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
  1958年6/7月号的《美国数学月刊》上有这样一道题目:
  “证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”
  这个问题可以用如下方法简单明了地证出:
  在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人。如果两人以前彼此认识,那么就在代表他们的两点间连成一条红线;否则连一条蓝线。考虑A点与其余各点间的5条连线AB,AC,...,AF,它们的颜色不超过2种。根据抽屉原理可知其中至少有3条连线同色,不妨设AB,AC,AD同为红色。如果BC,BD ,CD 3条连线中有一条(不妨设为BC)也为红色,那么三角形ABC即一个红色三角形,A、B、C代表的3个人以前彼此相识:如果BC、BD、CD 3条连线全为蓝色,那么三角形BCD即一个蓝色三角形,B、C、D代表的3个人以前彼此不相识。不论哪种情形发生,都符合问题的结论。

图1



  六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例,这个简单问题的证明思想可用来得出另外一些深入的结论。这些结论构成了组合数学中的重要内容-----拉姆塞理论。从六人集会问题的证明中,我们又一次看到了抽屉原理的应用。

  摘自中学数学


相 关 文 章

趣谈平分
按遗嘱分马
分期付款问题一点通
抽屉原理与电脑算命
自己就是一本活日历—— 对蔡勒(Zeller)公式的改进
建议班级购买一台饮水机
怎样烧开水最快最省煤气(1)
几何就在你身边
足球联赛的理论保级分数
生活中的平均数
商标中的几何图形
巧分乳酪
半数儿童高于平均体重?
如何规划迟到所引起的焦虑
让数学有趣起来

中基网首页   教育新闻   课程改革   招生咨询    行政管理    教育用品   教育社区    NCCT  北师大  NRCCE  附校中心
关于我们 网站地图 联系方式 版权声明 广告服务
-----------------------------------------------------------------------
中国基础教育网 版权所有,2000-2002
Copyright 2000_2002 cbe21.com.All Rights Reserved