抽屉原理

桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现
至少会有一个抽屉里面放两个苹果。这一现象就是我们所说的“抽屉原理”。
抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代
表一个元素,假如有n+1或多于n+1个元素放到n个集合中去,其中必定至少有
一个集合里有两个元素。” 抽屉原理有时也被称为鸽巢原理(“如果有五个鸽
子笼,养鸽人养了6只鸽子,那么当鸽子飞回笼中后,至少有一个笼子中装有2
只鸽子”)。它是组合数学中一个重要的原理。

 

第一抽屉原理
  原理1 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少
于两件; 抽屉原理[证明](反证法):如果每个抽屉至多只能放进一个物体
,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能.
  原理2 把多于mn(m乘以n)个的物体放到n个抽屉里,则至少有一个抽屉里有
不少于m+1的物体。
  [证明](反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn
个物体,与题设不符,故不可能
  原理3 把无穷多件物体放入n个抽屉,则至少有一个抽屉里 有无穷个物体
。.
  原理1 2 3都是第一抽屉原理的表述
第二抽屉原理
  把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)
个物体。
  [证明](反证法):若每个抽屉都有不少于m个物体,则总共至少有mn个物
体,与题设矛盾,故不可能

 

 

概述
  应用抽屉原理解题
  抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许
多有关存在性的证明都可用它来解决。
  例1:400人中至少有2个人的生日相同.
  解:将一年中的366天视为366个抽屉,400个人看作400个物体,由抽屉原
理1可以得知:至少有2人的生日相同. 400/366=1…34,1+1=2 又如:我们从街
上随便找来13人,就可断定他们中至少有两个人属相相同.
  “从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
  “从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”

 

 

 

制造抽屉是运用原则的一大关键
  例1 从2、4、6、…、30这15个偶数中,任取9个数,证明其中一定有两个
数之和是34。
  分析与解答 我们用题目中的15个偶数制造8个抽屉:
  此抽屉特点:凡是抽屉中有两个数的,都具有一个共同的特点:这两个数
的和是34。现从题目中的15个偶数中任取9个数,由抽屉原理(因为抽屉只有8
个),必有两个数可以在同一个抽屉中(符合上述特点).由制造的抽屉的特点
,这两个数的和是34。
  例2:从1、2、3、4、…、19、20这20个自然数中,至少任选几个数,就可
以保证其中一定包括两个数,它们的差是12。
  分析与解答在这20个自然数中,差是12的有以下8对:{20,8},{19,7},
{18,6},{17,5},{16,4},{15,3},{14,2},{13,1}。
  另外还有4个不能配对的数{9},{10},{11},{12},共制成12个抽屉(每
个括号看成一个抽屉).只要有两个数取自同一个抽屉,那么它们的差就等于12
,根据抽屉原理至少任选13个数,即可办到(取12个数:从12个抽屉中各取一
个数(例如取1,2,3,…,12),那么这12个数中任意两个数的差必不等于12
)。

时间: 2024-09-22 00:51:54

抽屉原理的相关文章

simhash算法原理及实现

转载自: 点击打开链接 背景 如何设计一个比较两篇文章相似度的算法?可能你会回答几个比较传统点的思路: 一种方案是先将两篇文章分别进行分词,得到一系列特征向量,然后计算特征向量之间的距离(可以计算它们之间的欧氏距离.海明距离或者夹角余弦等等),从而通过距离的大小来判断两篇文章的相似度. 另外一种方案是传统hash,我们考虑为每一个web文档通过hash的方式生成一个指纹(finger print). 下面,我们来分析下这两种方法. 采取第一种方法,若是只比较两篇文章的相似性还好,但如果是海量数据

初步探究Python程序的执行原理_python

1. 过程概述 Python先把代码(.py文件)编译成字节码,交给字节码虚拟机,然后虚拟机一条一条执行字节码指令,从而完成程序的执行.2. 字节码 字节码在Python虚拟机程序里对应的是PyCodeObject对象. .pyc文件是字节码在磁盘上的表现形式.3. pyc文件 PyCodeObject对象的创建时机是模块加载的时候,即import. Python test.py会对test.py进行编译成字节码并解释执行,但是不会生成test.pyc. 如果test.py加载了其他模块,如im

POJ题目分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

求职大数据处理面试问题汇总

1. 给定a.b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a.b文件共同的url? 方案1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G.所以不可能将其完全加载到内存中处理.考虑采取分而治之的方法. s 遍历文件a,对每个url求取 ,然后根据所取得的值将url分别存储到1000个小文件(记为 )中.这样每个小文件的大约为300M. s 遍历文件b,采取和a相同的方式将url分别存储到1000各小文件(记为 ).这样处理后,所有可

北大ACM试题分类

初级: 一.基本算法:  (1)枚举. (poj1018,poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法.  (4)递推.  (5)构造法.(poj3295,poj3239) (6.1)模拟法.(poj1008,poj1068,poj2632,poj1573,poj2993,poj2996,poj3087) (6.2)模拟法(高精度算法)(poj1001,poj1503,poj2389,poj2602,poj3982,21位大数

poj分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

《程序设计解题策略》——1.2 利用最小生成树及其扩展形式解题

1.2 利用最小生成树及其扩展形式解题 设G=(V,E,ω)是连通的有权无向图(节点集为V,边集为E,边权集为ω),连通图G中包含所有节点,且只有V-1条边的连通子图即为G的生成树.边权值和最小的生成树称为最小生成树.在现实生活中,最小生成树的原理和算法有着广泛的应用.程序设计竞赛中与最小生成树有关的试题一般有两类: 1) 构建最小生成树. 2) 应用最小生成树原理优化算法. 本节除了深入研讨最小生成树的性质和求解方法外,还给出了三种特殊类型生成树: 1) 最优比率生成树. 2) 最小k度限制生

十七道海量数据处理面试题与Bit-map详解

作者:小桥流水,redfox66,July.   前言     本博客内曾经整理过有关海量数据处理的10道面试题(十道海量数据处理面试题与十个方法大总结),此次除了重复了之前的10道面试题之后,重新多整理了7道.仅作各位参考,不作它用.     同时,程序员编程艺术系列将重新开始创作,第十一章以后的部分题目来源将取自下文中的17道海量数据处理的面试题.因为,我们觉得,下文的每一道面试题都值得重新思考,重新深究与学习.再者,编程艺术系列的前十章也是这么来的.若您有任何问题或建议,欢迎不吝指正.谢谢

ACM练级

一般要做到50行以内的程序不用调试.100行以内的二分钟内调试成功.acm主要是考算法的 ,主要时间是花在思考算法上,不是花在写程序与debug上.  下面给个计划你练练: 第一阶段: 练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来.  1.最短路(Floyd.Dijstra,BellmanFord)  2.最小生成树(先写个prim,kruscal要用并查集,不好写)  3.大数(