把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个或两个以上的苹果。
抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。
形式一:
证明:设把n +…,An ,用a1,a2,…,an 表示这n 个集合里相应的元素个数,需要证明至少存在某个ai 大于或等于2
(用反证法)假设结论不成立,即对每一个ai 都有ai <++…+++…+=<+ai≥2,即必有一个集合中含有两个或两个以上的元素。
形式二:
设把n·m+…,An ,用a1,a2,…,an 表示这n 个集合里相应的元素个数,需要证明至少存在某个ai 大于或等于m +<+++…+++…+=
n个m
<++==-=-=……
一般地,我们有:[x]≤x<+…,Ak ,用a1,a2,…,ak 表示这k 个集合里相应的元素个数,需要证明至少存在某个ai 大于或等于[n/k]。
(用反证法)假设结论不成立,即对每一个ai 都有ai <++…+<…+[n/k] k个[n/k]
=·(n/k)=++…+k <
这与题设相矛盾。
所以,必有一个集合中元素个数大于或等于[n/k]
形式四:
证明:设把q1++…+-+…,An ,用a1,a2,…,an 表示这n 个集合里相应的元素个数,需要证明至少存在某个i ,使得ai 大于或等于qi 。
(用反证法)假设结论不成立,即对每一个ai 都有ai <-++…+++…+-<++…+-+)的四个小正方形,视这四个正方形为抽屉,9个点任意放入这四个正方形中,据形式2,必有三点落入同一个正方形内. 现特别取出这个正方形来加以讨论.
把落在这个正方形中的三点记为D 、E 、F. 通过这三点中的任意一点(如E )作平行线,如图可知:
S△DEF=+
≤×h+
=
=
例题3:任取5个整数,必然能够从中选出三个,使它们的和能够被3整除. 证明:任意给一个整数,它被3除,余数可能为0,1,2,我们把被3除余数为0,1,2的整数各归入类r 0,r1,r2°.某一类至少包含三个数;
2°.某两类各含两个数,第三类包含一个数.
若是第一种情况,就在至少包含三个数的那一类中任取三数,其和一定能被3整除;
若是第二种情况,在三类中各取一个数,其和也能被3整除.
综上所述,原命题正确.
例题4:九条直线中的每一条直线都将正方形分成面积比为2∶3的梯形,证明:这九条直线中至少有三条经过同一点.
证明:如图,设PQ 是一条这样的直线,作这两个梯形的中位线MN
∵这两个梯形的高相等
∴它们的面积之比等于中位线长的比,即|MH|∶|NH|
∴点H 有确定的位置
(它在正方形一对对边中点的连线上,并且|MH|∶|NH|=,100株可以构造51个抽屉,则个问题就转化为至少有5人植树的株数在同一个抽屉里.
(用反证法) 假设无5人或5人以上植树的株数在同一个抽屉里,那只有5人以下植树的株数在同一个抽屉里,而参加植树的人数为204人,所以,每个抽屉最多有4人,故植树的总株数最多有:
4(50+51+…+100)
=×
=15300
<15301
练习:
1.边长为1的等边三角形内有5个点,那么这5个点中一定有距离小于0.5的两点.
2.边长为1的等边三角形内,若有n2+.
3.求证:任意四个整数中,至少有两个整数的差能够被3整除.
4.某校高一某班有50名新生,试说明其中一定有二人的熟人一样多.
5.某个年级有202人参加考试,满分为100分,且得分都为整数,总得分为10101分,则至少有3人得分相同 .
2013年北京公务员考试行测抽屉原理中投票问题分析
【例1】(2011-安徽-13) 有120名职工投票从甲、乙、丙三人中选举一人为劳模,每人只能投一次,且只能选一个人,得票最多的人当选。统计票数的过程中发现,在前81张票中,
甲得21票,乙得25票,丙得35票。在余下的选票中,丙至少再得几张选票就一定能当选?
( )
A.15 B.18
C.21 D.31
【答案】A
【分析】乙和丙的票数较接近,乙对丙的威胁最大,考虑最坏的情况,在剩余的39张票中,只在乙丙中分配。先分给乙10张,此时乙丙都得35票,还剩29票,如果乙和丙均再得14张选票,二者票数相同,丙仍然不能保证当选,于是丙需要再得1张选票,即在最后29票中只要分15票给丙,就可以保证丙必然当选。所以选A 。
这样解,能解出答案,但是过程有点繁琐。其实我们还可以整体思考,乙和丙的票数较接近,乙对丙的威胁最大,120张选票减去甲的21张选票,剩余99张,如果乙和丙均已经得到了49张选票,这时候是最坏的情况,如果丙再得1张选票,一定能当选,所以这时丙得票49+1=50张,因此在35票的基础上,需要再得15张选票。
【解析】整体考虑,乙丙共可以分120-21=99张选票,均得到49张时,丙仍然保证不了能当选,再得剩下的1张选票,即丙得到50张选票时,保证当选,所以还需要50-35=15张,选A 。
现在大家应该知道这类问题的整体思考方法了吧,让我们试试下面两道例题:
【例2】 (黑龙江2010-49,广东2009-12) 某单位有52人投票,从甲、乙、丙三人中选出一名先进工作者。在计票过程中的某时刻,甲得17票,乙得16票,丙得11票,如果规定得票比其他两人都多的候选人才能当选。那么甲要确保当选,最少要再得票( ) 张?
A. 1张 B. 2张
C. 3张 D. 4张
【答案】D
【解析】整体考虑,乙对甲威胁最大,甲乙共可以分52-11=41张选票,甲乙均得到20张时,甲仍然保证不了能当选,再得剩下的1张选票,即甲得到21张选票时,保证当选,所以还需要21-17=4张,选D 。
【例3】(河北2009-108)100名村民选一名代表,候选人是甲、乙、丙三人,每人只能投票选举一人,得票最多的人当选。开票中途累计前61张选票中,甲得35票,乙得10票,丙得16票。在尚未统计的选票中,甲至少再得多少票就一定当选?
A. 11 B. 12
C. 13 D. 14
【答案】A
【解析】整体考虑,丙对甲威胁最大,甲丙共可以分100-10=90张选票,甲乙均得到45张时,甲仍然保证不了能当选,需要甲得46票、丙得44票时,甲才可以保证当选,所以还需要46-35=11张,选A 。
把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个或两个以上的苹果。
抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。
形式一:
证明:设把n +…,An ,用a1,a2,…,an 表示这n 个集合里相应的元素个数,需要证明至少存在某个ai 大于或等于2
(用反证法)假设结论不成立,即对每一个ai 都有ai <++…+++…+=<+ai≥2,即必有一个集合中含有两个或两个以上的元素。
形式二:
设把n·m+…,An ,用a1,a2,…,an 表示这n 个集合里相应的元素个数,需要证明至少存在某个ai 大于或等于m +<+++…+++…+=
n个m
<++==-=-=……
一般地,我们有:[x]≤x<+…,Ak ,用a1,a2,…,ak 表示这k 个集合里相应的元素个数,需要证明至少存在某个ai 大于或等于[n/k]。
(用反证法)假设结论不成立,即对每一个ai 都有ai <++…+<…+[n/k] k个[n/k]
=·(n/k)=++…+k <
这与题设相矛盾。
所以,必有一个集合中元素个数大于或等于[n/k]
形式四:
证明:设把q1++…+-+…,An ,用a1,a2,…,an 表示这n 个集合里相应的元素个数,需要证明至少存在某个i ,使得ai 大于或等于qi 。
(用反证法)假设结论不成立,即对每一个ai 都有ai <-++…+++…+-<++…+-+)的四个小正方形,视这四个正方形为抽屉,9个点任意放入这四个正方形中,据形式2,必有三点落入同一个正方形内. 现特别取出这个正方形来加以讨论.
把落在这个正方形中的三点记为D 、E 、F. 通过这三点中的任意一点(如E )作平行线,如图可知:
S△DEF=+
≤×h+
=
=
例题3:任取5个整数,必然能够从中选出三个,使它们的和能够被3整除. 证明:任意给一个整数,它被3除,余数可能为0,1,2,我们把被3除余数为0,1,2的整数各归入类r 0,r1,r2°.某一类至少包含三个数;
2°.某两类各含两个数,第三类包含一个数.
若是第一种情况,就在至少包含三个数的那一类中任取三数,其和一定能被3整除;
若是第二种情况,在三类中各取一个数,其和也能被3整除.
综上所述,原命题正确.
例题4:九条直线中的每一条直线都将正方形分成面积比为2∶3的梯形,证明:这九条直线中至少有三条经过同一点.
证明:如图,设PQ 是一条这样的直线,作这两个梯形的中位线MN
∵这两个梯形的高相等
∴它们的面积之比等于中位线长的比,即|MH|∶|NH|
∴点H 有确定的位置
(它在正方形一对对边中点的连线上,并且|MH|∶|NH|=,100株可以构造51个抽屉,则个问题就转化为至少有5人植树的株数在同一个抽屉里.
(用反证法) 假设无5人或5人以上植树的株数在同一个抽屉里,那只有5人以下植树的株数在同一个抽屉里,而参加植树的人数为204人,所以,每个抽屉最多有4人,故植树的总株数最多有:
4(50+51+…+100)
=×
=15300
<15301
练习:
1.边长为1的等边三角形内有5个点,那么这5个点中一定有距离小于0.5的两点.
2.边长为1的等边三角形内,若有n2+.
3.求证:任意四个整数中,至少有两个整数的差能够被3整除.
4.某校高一某班有50名新生,试说明其中一定有二人的熟人一样多.
5.某个年级有202人参加考试,满分为100分,且得分都为整数,总得分为10101分,则至少有3人得分相同 .
2013年北京公务员考试行测抽屉原理中投票问题分析
【例1】(2011-安徽-13) 有120名职工投票从甲、乙、丙三人中选举一人为劳模,每人只能投一次,且只能选一个人,得票最多的人当选。统计票数的过程中发现,在前81张票中,
甲得21票,乙得25票,丙得35票。在余下的选票中,丙至少再得几张选票就一定能当选?
( )
A.15 B.18
C.21 D.31
【答案】A
【分析】乙和丙的票数较接近,乙对丙的威胁最大,考虑最坏的情况,在剩余的39张票中,只在乙丙中分配。先分给乙10张,此时乙丙都得35票,还剩29票,如果乙和丙均再得14张选票,二者票数相同,丙仍然不能保证当选,于是丙需要再得1张选票,即在最后29票中只要分15票给丙,就可以保证丙必然当选。所以选A 。
这样解,能解出答案,但是过程有点繁琐。其实我们还可以整体思考,乙和丙的票数较接近,乙对丙的威胁最大,120张选票减去甲的21张选票,剩余99张,如果乙和丙均已经得到了49张选票,这时候是最坏的情况,如果丙再得1张选票,一定能当选,所以这时丙得票49+1=50张,因此在35票的基础上,需要再得15张选票。
【解析】整体考虑,乙丙共可以分120-21=99张选票,均得到49张时,丙仍然保证不了能当选,再得剩下的1张选票,即丙得到50张选票时,保证当选,所以还需要50-35=15张,选A 。
现在大家应该知道这类问题的整体思考方法了吧,让我们试试下面两道例题:
【例2】 (黑龙江2010-49,广东2009-12) 某单位有52人投票,从甲、乙、丙三人中选出一名先进工作者。在计票过程中的某时刻,甲得17票,乙得16票,丙得11票,如果规定得票比其他两人都多的候选人才能当选。那么甲要确保当选,最少要再得票( ) 张?
A. 1张 B. 2张
C. 3张 D. 4张
【答案】D
【解析】整体考虑,乙对甲威胁最大,甲乙共可以分52-11=41张选票,甲乙均得到20张时,甲仍然保证不了能当选,再得剩下的1张选票,即甲得到21张选票时,保证当选,所以还需要21-17=4张,选D 。
【例3】(河北2009-108)100名村民选一名代表,候选人是甲、乙、丙三人,每人只能投票选举一人,得票最多的人当选。开票中途累计前61张选票中,甲得35票,乙得10票,丙得16票。在尚未统计的选票中,甲至少再得多少票就一定当选?
A. 11 B. 12
C. 13 D. 14
【答案】A
【解析】整体考虑,丙对甲威胁最大,甲丙共可以分100-10=90张选票,甲乙均得到45张时,甲仍然保证不了能当选,需要甲得46票、丙得44票时,甲才可以保证当选,所以还需要46-35=11张,选A 。