当前位置:首页 >> 学科竞赛 >>

江苏省金湖县实验中学高中数学奥赛辅导:抽屉原理


把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个 或两个以上的苹果。 抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出 来并用以证明一些数论中的问题,因此,也称 为狄利克雷原则。它是组合数学中 一个重要的原理。把它推广到一般情形有以下几种表现形式。

形式 一: 证明:设把 n+1 个元素分为 n 个集合 A1,A2,…,A

n,用 a1,a2,…,an 表示这 n 个集合里相应的元素个数,需要证明至少存在某个 ai 大于或等于 2 (用反证法)假设结论不成立,即对每一个 ai 都有 ai<2,则因为 ai 是整数, 应有 ai≤1,于是有: a1+a2+…+an≤1+1+…+1=n<n+1 这与题设矛盾。 所以,至少有一个 ai≥2,即必有一个集合中含有两个或两个以上的元素。 形式二: 设把 n·m+1 个元素分为 n 个集合 A1,A2,…,An,用 a1,a2,…,an 表示 这 n 个集合里相应的元素个数,需要证明至少存在某个 ai 大于或等于 m+1。 (用反证法)假设结论不成立,即对每一个 ai 都有 ai<m+1,则因为 ai 是整 数,应有 ai≤m,于是有: a1+a2+…+an≤m+m+…+m=n·m n个m <n·m+1

这与题设相矛盾。 所以,至少有存在一个 ai≥m+1 高斯函数: 对任意的实数 x, [x]表示“不大于 x 的最大整数”. 例如:[3.5]=3,[2.9]=2, [-2 .5]=-3,[7]=7,…… 一般地,我们有:[x]≤x<[x]+1 形式三: 证明:设把 n 个元素分为 k 个集合 A1,A2,…,Ak,用 a1,a2,…,ak 表 示这 k 个集合里相应的元素个数,需要证明至少存在某个 ai 大于或等于[n/k]。 (用反证法)假设结论不成立,即对每一个 ai 都有 ai<[n/k],于是有: a1+a2+…+ak<[n/k]+[n/k]+…+[n/k] k 个[n/k] =k·[n/k]≤k·(n/k)=n ∴ a1+a2+…+ak<n 这与题设相矛 盾。 所以,必有一个集合中元素个数大于或等于[n/k] 形式四: 证明:设把 q1+q2+…+qn-n+1 个元素分为 n 个集合 A1,A2,…,An,用 a1,a2,…,an 表示这 n 个集合里相应的元素个数,需要证明至少存在某个 i,使 得 ai 大于或等于 qi。

(用反证法)假设结论不成立,即对每一个 ai 都有 ai<qi,因为 ai 为整数,应 有 ai≤qi-1,于是有: a1+a2+…+an≤q1+q2+…+qn-n <q1+q2+…+qn-n+1 这与题设矛盾。 所以,假设不成立,故必有一个 i,在第 i 个集合中元素个数 ai≥qi

形式五: 证明: (用反证法 )将无穷多个元素分为有限个集合,假设这有限个集合中的 元素的个数都是有限个,则有限个有限数相加,所得的数必是有限数,这就与题 设产生矛盾,所以,假设不成 立,故必有一个集合含有无穷多个元素。

例题1:400 人中至少有两个人的生日相同. 分析:生日从 1 月 1 日排到 12 月 31 日,共有 366 个不相同的生日,我们把 366 个不同的生日看作 366 个抽屉,400 人视为 400 个苹果,由表现形式 1 可知, 至少有两人在同 一个抽屉里,所以这 400 人中有两人的生日相同. 解:将一年中的 366 天视为 366 个抽屉,400 个人看作 400 个苹果,由抽屉 原理的表现形式 1 可以得知:至少有两人的生日相同.

例题2:边长为 1 的正方形中,任意放入 9 个点,求证这 9 个点中任取 3 个点组

成的三角形中,至少有一个的面积不超过 1/8.

1 解:将边长为 1 的正方形等分成边长为 2
形内.现特别取出这个正方形来加以讨论.

的四个小正方形,视这四个正方

形为抽屉,9 个点任意放入这四个正方形中,据形式 2,必有三点落入同一个正方

把落在这个正方形中的三点记为 D、E、 F.通过这三点中的任意一点(如 E)作平行线,如图可知: S△DEF=S△DEG+S△EFG

1 1 1 1 1 ? ( ? h) ? ≤ 2 ×h+ 2 2 2 2 h 1 h ? ? = 4 8 4
1 = 8

E D G F
C

例题3:任取 5 个整数,必然能够从中选出三个,使它们的和能够被 3 整除. 证明:任意给一个整数,它被 3 除,余数可能为 0,1,2,我们把被 3 除余 数为 0,1,2 的整数各归入类 r0,r1,r2.至少有一类包含所给5个数中的至少两 个.因此可能出现两种情况: 1°.某一类至少包含三个数; 2°.某两类各含 两个数,第三类包含一个数. 若是第一种情况,就在至少包含三个数的那一类中任取三数,其和一定能被 3 整除; 若是第二种情况,在三类中各取一个数,其和也能被 3 整除. 综上所述,原命题正确.

例题4:九条直线中的每一条直线都将正方形分成面积比为 2∶3 的梯形 ,证明: 这九条直线中至少有三条经过同一点. 证明:如图,设 PQ 是一 条这样的直线,作这两个梯形的中位线 MN

P A E K M H F Q J I N B

D

C

∵这两个梯形的高相等 ∴它们的面积之比等于中位线长 的比,即|MH|∶|NH| ∴点 H 有确定的位置 (它在正方形一对对边中点的连线上,并且|MH|∶|NH|=2∶3). 由几何上的对称性,这种点共有四个,即,图中的 H、J、I、K.已知的九条适 合条件的分割直线中的每一条必须经过 H、J、I、K 这四点中的一点.把 H、J、I、 K 看成四个抽屉,九条直线当成9个苹果,即可得出必定有3条分割线经过同一 点.

例题5:某校派出学生 204 人上山植树 15301 株,其中最少一人植树 50 株,最 多一人植树 100 株,则至少有 5 人植树的株数相同. 证明:按植树的多少,从 50 到 100 株可以构造 51 个抽屉,则个 问题就转化 为至少有 5 人植树的株数在同一个抽屉里.

(用反证法)假设无5人或5人以上植树的株数在同一个抽屉里,那只有5人以 下植树的株数在同一个抽屉里, 而参加植树的人数为 204 人, 所以, 每个抽屉最 多 有 4 人,故植树的总株数最多有: 4(50+51+…+100)

(50 ? 100) ? 51 =4× 2
=15300 <15301 得出矛盾. 因此,至少有5人植树的株数相同.

练习: 1.边长为 1 的等边三角形内有 5 个点,那么这 5 个点中一定有距离小于 0.5 的两 点.

2.边长为 1 的等边三角形内,若有 n2+1 个点,则

1 至少存在 2 点距离小于 n

.

3.求证:任意四个整数中,至少有两个整数的差能够被 3 整除. 4.某校高一某班有 50 名新生,试说明其中一定有二人的熟人一样多.

5. 某个年级有 202 人参加考试, 满分为 100 分, 且得分都为整数, 总得分为 10101 分,则至少有 3 人得分相同.


相关文章:
江苏省金湖县实验中学高中数学奥赛辅导:抽屉原理
江苏省金湖县实验中学高中数学奥赛辅导:抽屉原理 隐藏>> 把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个 或两个以上的苹果。 抽屉原则有...
江苏省金湖县实验中学高中数学奥赛辅导:集合与简易逻辑
江苏省金湖县实验中学高中数学奥赛辅导:集合与简易逻辑_学科竞赛_高中教育_教育...提示:利用余数构造 n 个集合,根据抽屉原理,至少有两个整数放在一个集合里,它们...
高中数学竞赛讲义-抽屉原理
高中数学竞赛讲义-抽屉原理_学科竞赛_高中教育_教育专区。数学教育网---数学试题...初中数学竞赛辅导资料(8... 3页 免费 高中竞赛辅导讲义抽屉原... 4页 免费...
奥赛专题 -- 抽屉原理
江苏省金湖县实验中学高... 暂无评价 8页 免费 抽屉原理公考专题 22页 2下载...高中数学奥赛辅导系列-函... 8页 免费奥​赛​专​题​ ​-​-...
抽屉原理与高中数学竞赛
摘 要 本论文首先讨论了抽屉原理的一般含义和它的两种推广形式;其次给出了抽屉原理在 整除问题、面积问题、染色问题、六人集会问题以及生日问题等高中数学竞赛问题中...
浅谈抽屉原理在高中数学竞赛中的运用
浅谈抽屉原理高中数学竞赛中的运用 浅谈抽屉原理高中数学竞赛中的运用 抽屉原理在数学问题中有一类与“存在性”有关的问题,例如:“13 个人中至少有两个人出生...
高中数学奥赛辅导 第七讲 抽屉原则、容斥原理
高中数学奥赛辅导 第七讲 抽屉原则、容斥原理_学科竞赛_高中教育_教育专区。数学...? an | xn | 共有k n 个正数,由抽屉原则知 必有二数会落在同一个小...
高中竞赛专题:抽屉原理
高中竞赛专题:抽屉原理_理学_高等教育_教育专区。数学竞赛竞赛讲座 10 --抽屉原则 --抽屉原则大家知道,两个抽屉要放置三只苹果,那么一定有两只苹果放在同一个抽屉...
抽屉原理类问题的解题方法
抽屉原理类问题的解题方法_数学_自然科学_专业资料。抽屉原理类问题的解题方法时间:2008-5-12 11:23:32 做抽屉问题关键是确定 “抽屉”和“苹果”,当题目中出现...
浅谈抽屉原理在高中数学竞赛中的运1
浅谈抽屉原理高中数学竞赛中的运1_调查/报告_表格...总而言之, 抽屉原理的运用比较灵活, 在竞赛辅导中...抽屉原理中学数学竞赛... 3页 2下载券 中学数学...
更多相关标签: