登陆注册
6108500000018

第18章 抽屉原则

现在有五本书要放到四个抽屉里去,放法是很多的,有的抽屉可以不放,有的可以放一本,有的可以放二本、三本、四本甚至放五本。但是,随便怎样放法,至少总可以找到一个抽屉里至少放上二本书的。

如果每一个抽屉代表一个集合,每一本书就代表一个元素。假使有n+1或比n+1多的元素要放到n个集合里去,那也没有疑问,其中必定至少有一个集合里至少放进二个元素。这就是“抽屉原则”的抽象涵义。

现在我们班上有54个同学,我说,这54个同学中至少有二个人是同一个星期出生的。你一定会惊奇,我怎么会知道的呢?这很简单,按照我们学校目前招生的情况,学生们的生日不会相差一年,因为一年之中只有53个星期,现在学生有54人,我们运用抽屉原则的知识,把星期作为抽屉,学生作为书本,那么,这53个抽屉里,至少有一个抽屉放进至少二本书的,也就是至少有二个同学在同一星期出生。这不是很容易解答的吗?

一般的情况,书本的数目并不一定比抽屉数目多1,可以更多一些,例如多6本、7本放到四个抽屉里。如果更多呢?例如21本书放到4个抽屉里,道理也是一样,也就是无论怎样放法,至少可以找到一个抽屉里至少有6本书。这样的情况,即把(m×n+1)或比(m×n+1)多的元素放到n个集合里的话,无论怎样放法,其中必定至少有一个集合里至少放进m+1个元素。

我们来试试看,假使在一个平面上有任意六个点,无三点共线,每二点用红色或蓝色的线段连起来,都连好以后,能不能找到一个由这些线段构成的三角形,它们的三条边是同一颜色的?

我们可以随便选择其中任何一点,可以看到这一点到其他五个点之间连接了5条线段,这5条线段中,至少有三条是同一颜色,假定是红色。现在我们单独来看这三条红色的线段吧,这三条线段的另一端不是也有不同颜色的线段连接起来构成三角形的吗?假使其中有一条是红色的,那么,这条红色的线段和其他原来连接的两条红色线段就组成了一个我们所要找的三角形。假使这三条都是蓝色的呢,那么,这三条蓝色线段本身组成的也是我们所要找的三角形。所以,无论你怎样着色,在这任意六个点之间所有的线段中至少能找到同一种颜色的一个三角形。

假使在一场乒乓赛中,从所有的队员里任选六个人,你能证明他们当中必然有三个人互相握过手,或者彼此都没有握过手吗?

同类推荐
  • 骆驼祥子

    骆驼祥子

    《骆驼祥子》是老舍的代表作,也是现代文学史的重要收获。小说以二十年代末期北京市民的生活为背景,以人力车夫祥子坎坷、悲惨的生活遭遇为主线,向读者展示了底层贫苦市民努力改变命运却四处碰壁的图景,深刻揭露了那个时代对贫民大众生存的挤压。
  • 我和老师互换身份

    我和老师互换身份

    《爆笑校园·小学生搞笑故事会:我和老师互换身份》故事精彩生动,都源自于小学生身边的故事,读完我,你能积累很多实用的写作素材。《爆笑校园·小学生搞笑故事会:我和老师互换身份》故事都出自儿童文学作家的笔下,每个故事都是优秀的范文,读了我,一定会让你的写作水平更上一层楼。《爆笑校园·小学生搞笑故事会:我和老师互换身份》中的每个故事都很有启发性,同学们读后会领悟成长的真谛。
  • 美洲寓言(语文新课标课外必读第八辑)

    美洲寓言(语文新课标课外必读第八辑)

    国家教育部颁布了最新《语文课程标准》,统称新课标,对中、小学语文教学指定了阅读书目,对阅读的数量、内容、质量以及速度都提出了明确的要求,这对于提高学生的阅读能力,培养语文素养,陶冶情操,促进学生终身学习和终身可持续发展,对于提高广大人民的文学素养具有极大的意义。
  • 做最有出息的女孩

    做最有出息的女孩

    《做最有出息的女孩》一定会让你欣喜地发现,此书能够帮你找到想要的一切答案。围绕女孩的性别和心理特征,《做最有出息的女孩》深入分析并解答了她们成长过程中颇需关注的问题,涉及女孩性格的塑造、气质的修炼、习惯的培养、知识的储备、交际能力的锻炼以及青春期的教育等,涵盖女孩绚丽多彩生活的方方面面。
  • 海的女儿(语文新课标课外必读第二辑)

    海的女儿(语文新课标课外必读第二辑)

    国家教育部颁布了最新《语文课程标准》,统称新课标,对中、小学语文教学指定了阅读书目,对阅读的数量、内容、质量以及速度都提出了明确的要求,这对于提高学生的阅读能力,培养语文素养,陶冶情操,促进学生终身学习和终身可持续发展,对于提高广大人民的文学素养具有极大的意义。
热门推荐
  • BOOS来袭,霸宠不乖妻

    BOOS来袭,霸宠不乖妻

    他说一手遮天的帝王,她是市长家的千金,当强者遇到强者又会是怎样的一番景象?“小熙儿,你又不乖咯”他邪魅的说“我要出去,北冥轩”她恶狠狠的盯着他说“可以啊,取悦我”“哎呀,小北北,小冥冥,小轩轩,人家想出去吗”“阿伟,陪夫人一起”“我不,我要一个人出去,北冥轩,你这是剥夺我的人身自由权,人身自由权”“你都是我的,何来剥夺一说?”
  • 异世卡尔

    异世卡尔

    拥有Dota元素召唤师卡尔天赋的地球少年在魔法世界的征途
  • 大咒師

    大咒師

    寒天阳没有修炼的资质,更没有任何神兵利器在手,只是一个被掌门捡回来的一个体弱多病随时一命呜呼的人,同时还惨受同门欺凌的人……梦中频频出现的神秘女子,寒天阳真正的身份疑云笼罩。机缘巧合之下,咒术开启。种种谜团接踵解开,受万年的唾弃,受世人的仇视。真相?是报复世人的开始,还是重现大咒师的辉煌……
  • 词坛丛话

    词坛丛话

    本书为公版书,为不受著作权法限制的作家、艺术家及其它人士发布的作品,供广大读者阅读交流。
  • 深埋心底的恋爱

    深埋心底的恋爱

    职场生活耽误了许多青春年华,当大龄剩男遇见大龄剩女心中泛起涟漪,却是谁都没有挺破爱情的窗户纸。他们能不能抓住青春岁月尾巴步入婚姻的殿堂,请欣赏短篇小说《深埋心底的恋爱》。
  • 傲尘嚣

    傲尘嚣

    平生多磨砺,男儿自横行。身份卑微就要受人奴役?不!他绝不接受命运的摆布,誓要取回自己的尊严!从此,一个叫沐尘的少年,倔傲的走上了荆棘满布的修炼之路。一块莫名得来的黑铁,竟隐藏着焚天魔焰的收服之法;阴差阳错下,他居然成了人人敬畏的炼阵师……什么家族天才、什么宗门高手、什么隐世强者,只管放马来战,谁怕谁?风云变幻,五大古族延续数百年的恩怨,也该是时候解决了!心高寂寥,醉傲尘嚣名留扬。灭世浩劫将至,问谁能颠峰之上,笑看云起风生……
  • 偕我千岁

    偕我千岁

    杨姑娘要渡河,龟先生问,你要往哪里去。姑娘道,从哪里来,往哪里去。龟先生道,此河甚险,不可强渡。杨姑娘浅浅一笑,纵身一跃,千年宿怨轮转。
  • 猎狗王

    猎狗王

    讲述一只忠诚母猎狗一生的故事,再次赞扬人与狗的奇妙关系
  • 废柴凤女:邪魅魔王,快接招

    废柴凤女:邪魅魔王,快接招

    她是凤王府绝色五小姐,出了名的痴傻废柴,被兄姐欺辱溺水而亡;她是天界凤族新任首领,凤体被毁,十魂破散,族人被屠。当魂落凡间,再次睁眼,寒芒四射,命运从此颠覆!!!欺她痴傻?赤金级智魂归位,阴谋诡计她信手拈来。笑她废柴?破除封印、十魂归位、万兽共尊、重塑凤体……举世,为之战栗。凤傲九天,却不小心被腹黑妖孽缠上,碧落黄泉,生死相随。“只是……情魂归位,怎么还是冷面禁欲系?”被踹下床的魔王嘟囔道。推荐新文女扮男装《空间神医:国民男神是女生》
  • 孔子与儒家学派

    孔子与儒家学派

    《中国文化知识读本