共你痴痴爱在男生版:鸽洞原理(悬赏很多分)
来源:百度文库 编辑:偶看新闻 时间:2024/05/05 05:31:26
抽屉原理
桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,抽屉原理的一般含义为:“如果每个抽屉代表一个集合,
抽屉原理有时也被称为鸽巢原理(“如果有五个鸽子笼,
一. 抽屉原理最常见的形式
原理1 把多于n个的物体放到n个抽屉里,
[证明](反证法):如果每个抽屉至多只能放进一个物体,
原理2 把多于mn个的物体放到n个抽屉里,则至少有一个抽屉里有m+
[证明](反证法):若每个抽屉至多放进m个物体,
原理1 2都是第一抽屉原理的表述
第二抽屉原理:
把(mn-1)个物体放入n个抽屉中,
[证明](反证法):若每个抽屉都有不少于m个物体,
二.应用抽屉原理解题
抽屉原理的内容简明朴素,易于接受,
例1:400人中至少有两个人的生日相同.
解:将一年中的366天视为366个抽屉,
又如:我们从街上随便找来13人,
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,
例2: 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,
解 :从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),
上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题,
抽屉原理虽然简单,但应用却很广泛,它可以解答很多有趣的问题,
(一) 整除问题
把所有整数按照除以某个自然数m的余数分为m类,
例1 证明:任取8个自然数,必有两个数的差是7的倍数。
分析与解答 在与整除有关的问题中有这样的性质,如果两个整数a、b,
例2:对于任意的五个自然数,
证明∵任何数除以3所得余数只能是0,1,2,
[0],[1],[2]
①若这五个自然数除以3后所得余数分别分布在这3个抽屉中,
②若这5个余数分布在其中的两个抽屉中,则其中必有一个抽屉,
③若这5个余数分布在其中的一个抽屉中,很显然,
例2′:对于任意的11个整数,证明其中一定有6个数,
证明:设这11个整数为:a1,a2,a3……a11 又6=2×3
①先考虑被3整除的情形
由例2知,在11个任意整数中,必存在:
3|a1+a2+a3,不妨设a1+a2+a3=b1;
同理,剩下的8个任意整数中,由例2,必存在:3 | a4+a5+a6.设a4+a5+a6=b2;
同理,其余的5个任意整数中,有:3|a7+a8+a9,设:
②再考虑b1、b2、b3被2整除.
依据抽屉原理,b1、b2、b3这三个整数中,
则:6|b1+b2,即:6|a1+a2+a3+a4+a5+
∴任意11个整数,其中必有6个数的和是6的倍数.
例3: 任意给定7个不同的自然数,求证其中必有两个整数,
分析:注意到这些数队以10的余数即个位数字,以0,1,…,
(二)面积问题
例:九条直线中的每一条直线都将正方形分成面积比为2:
证明:如图,设直线EF将正方形分成两个梯形,作中位线MN。
(三)染色问题
例1正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),
证明:把两种颜色当作两个抽屉,把正方体六个面当作物体,
例2 有5个小朋友,
分析与解答 首先要确定3枚棋子的颜色可以有多少种不同的情况,可以有:
例3:假设在一个平面上有任意六个点,无三点共线,
解:首先可以从这六个点中任意选择一点,
例3′(六人集会问题)证明在任意6个人的集会上,
例3”:17个科学家中每个人与其余16个人通信,
解:不妨设A是某科学家,他与其余16位讨论仅三个问题,
若这6位中有两位之间也讨论甲问题,则结论成立。
若C,D,E中有两人也讨论乙问题,则结论也就成立了。否则,
三.制造抽屉是运用原则的一大关键
例1 从2、4、6、…、30这15个偶数中,任取9个数,
分析与解答 我们用题目中的15个偶数制造8个抽屉:
凡是抽屉中有两个数的,都具有一个共同的特点:
例2:从1、2、3、4、…、19、20这20个自然数中,
分析与解答在这20个自然数中,差是12的有以下8对:{20,
另外还有4个不能配对的数{9},{10},{11},{12}
例3: 从1到20这20个数中,任取11个数,必有两个数,
分析与解答 根据题目所要求证的问题,应考虑按照同一抽屉中,
{1,2,4,8,16},{3,6,12},{5,10,
从这10个数组的20个数中任取11个数,根据抽屉原理,
例4:某校校庆,来了n位校友,彼此认识的握手问候.
分析与解答 共有n位校友,每个人握手的次数最少是0次,
在有些问题中,“抽屉”和“物体”不是很明显的,需要精心制造“
抽屉原理
把八个苹果任意地放进七个抽屉里,不论怎样放,
形式一:证明:设把n+1个元素分为n个集合A1,A2,…,
a1+a2+…+an≤1+1+…+1=n<n+
形式二:设把n•m+1个元素分为n个集合A1,A2,…,
a1+a2+…+an≤m+m+…+m=n•m<n•m+1
n个m 这与题设相矛盾。所以,至少有存在一个ai≥m+1
高斯函数:对任意的实数x,[x]表示“不大于x的最大整数”.
例如:[3.5]=3,[2.9]=2,[-2.5]=-3,[
形式三:证明:设把n个元素分为k个集合A1,A2,…,Ak,
a1+a2+…+ak<[n/k]+[n/k]+…+[n/k] =k•[n/k]≤k•(n/k)=n
k个[n/k] ∴ a1+a2+…+ak<n 这与题设相矛盾。所以,必有一个集合中元素个数大于或等于[n/
形式四:证明:设把q1+q2+…+qn-n+
所以,假设不成立,故必有一个i,在第i个集合中元素个数ai≥
形式五:证明:(用反证法)将无穷多个元素分为有限个集合,
例题1:400人中至少有两个人的生日相同.分析:
解:将一年中的366天视为366个抽屉,
例题2:任取5个整数,必然能够从中选出三个,
证明:任意给一个整数,它被3除,余数可能为0,1,2,
若是第一种情况,就在至少包含三个数的那一类中任取三数,
例题3:某校派出学生204人上山植树15301株,
证明:按植树的多少,从50到100株可以构造51个抽屉,
(用反证法)假设无5人或5人以上植树的株数在同一个抽屉里,
4(50+51+…+100)=4× =15300<15301得出矛盾.因此,
练习:1.边长为1的等边三角形内有5个点,
2.边长为1的等边三角形内,若有n2+1个点,
3.求证:任意四个整数中,至少有两个整数的差能够被3整除.
4.某校高一某班有50名新生,
5.某个年级有202人参加考试,满分为100分,
“任意367个人中,必有生日相同的人。”
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,
... ...
大家都会认为上面所述结论是正确的。
“把m个东西任意分放进n个空抽屉里(m>n),
在上面的第一个结论中,由于一年最多有366天,
抽屉原理的一种更一般的表述为:
“把多于kn个东西任意分放进n个空抽屉(k是正整数),
利用上述原理容易证明:“任意7个整数中,
如果问题所讨论的对象有无限多个,抽屉原理还有另一种表述:
“把无限多个东西任意分放进n个空抽屉(n是自然数),
抽屉原理的内容简明朴素,易于接受,
1958年6/7月号的《美国数学月刊》上有这样一道题目:
“证明在任意6个人的集会上,或者有3个人以前彼此相识,
这个问题可以用如下方法简单明了地证出:
在平面上用6个点A、B、C、D、E、
六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例,
弹簧的原理(答得好有悬赏分)
为什么我的悬赏分上限只有100分,而看见很多朋友的悬赏是200分?
数学题(悬赏分:20!)
韩歌(悬赏10分!)
火影忍者(悬赏10分)
应用题(悬赏15分)
悬赏分~~~~
悬赏分5分
悬赏分5分
悬赏分5分
??????????????悬赏分:20分
最近没设悬赏分,突然少了110分(悬赏分)如何找会来
歇后语(对最佳答案追加悬赏分)
重分悬赏!!!(闲人勿进)
本地连接的问题(悬赏5分)
PHOTOSHOP 提问(多分悬赏)
采纳者(追加悬赏分)
无法运行sfc(追加悬赏分)
文字游戏(答对者追加悬赏分)
求藏头诗(追加20分悬赏)
超女(悬赏分:100)
6年级应用题(悬赏5分)
历史(关于孙中山)有悬赏分!!!
求藏头诗(高手快进200分悬赏)