tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

抽屉原理(高中)


抽屉原理
一.抽屉原理的各种形式: 抽屉原理 1:n+1 个元素分成 n 类,至少有 1 类中的元素不止 1 个. 抽屉原理 2:n· 个元素分成 n 类,至少有 1 类中的元素不止 m+1 个. m+1 k-1? 即:k 个元素分成 n 类,至少有 1 类中的元素不止? ? n ?+1 个.(k,n∈N*) m m 抽屉原理 3:n 个数之和为 m,则其中必有一数≥

,也必有一数≤ . n n 抽屉原理 4 把一个无限集 A 分成有限个集合的并集, Ai?A, 即 且

∪A =A,A ∩A =?(i,j=1,2,……,
n i=1
i i j

n;i≠j) .则至少有一个 A 的子集 Ak(1≤k≤n),它有无限多个元素. 例 1.把大小两个圆盘各划分成 2n 个相等的扇形格,在每格都用黑、白两色之一涂色,使两盘总计, 黑格与白格都各有 2n 格.然后把两个圆盘的圆心固定于同一点,并让小盘在上成为一个转盘.试证:可将 小盘转到某一适当位置,使两个圆盘上的格子对齐,并使二盘对应格子颜色不同的不少于 n 对. 证明:让小盘逐格转动,每次都记下颜色不同的格子对齐的数目,当转动了 2n-1 次后,小盘转动了 一周,共记了 2n 次.于是,小盘上每个格子都与大盘上的每个格子对齐一次. 设小盘上有 k 个黑格,2n-k 个白格,则大盘上有 2n-k 个黑格,k 个白格. 颜色不同的格子对齐的数目为 k2+(2n-k)2=4n2+2k2-4nk=2(k-n)2+2n2≥2n2. ∴至少有一次转动对齐后,使二盘对应格子颜色不同的数目≥? 2n2-1? ? 2n ?+1=n.

例 2.从 1,2,3,…,3n(n≥2)这 3n 个正整数中任意取出 n+2 个数,求证:其中必有两个数,其差 大于 n 而小于 2n. 解:设取出的最大的数为 k,则把取出的数都加上 3n-k,这样做不会影响它们之间的差.此时最大数 为 3n,如果在取出的数中有一个在 n 与 2n 间(满足 n+1≤x≤2n-1 的数),则这数与 3n 即为所求.若无任 何数在此二数之间,则作抽屉(1,2n),(2,2n+1),(3,2n+2),…,(n,3n-1),共 n 个抽屉,除去 3n 这 个数外,还有 n+1 个数,于是必有两个数落入同一抽屉,此二数即满足要求. 例 3.任取一个正实数 a,求证:在 a,2a,3a,…,(n-1)a 这 n-1 个数中,至少有一个数,它与最 1 接近的整数之差不超过 . n 解:取这 n-1 个数的小数部分{a},{2a},{3a},…,{(n-1)a},则此 n-1 个数都在区间[0,1)内, n-1 1 1 1 2 把区间[0,1)分成 n 个小区间,每个区间的长都为 :[0, ),[ , ),…,[ ,1). n n n n n 1 若此 n-1 个数中有某一个落入头尾两个区间之一,则原数即与最近的整数相差不超过 .此 n-1 个 n 数不可能没有任何一个落入头尾两个区间中,因若此 n-1 个数中没有任何一个落入头尾两个区间,则此 n -1 个数必落入了其余 n-2 个区间内,于是必有两个数落入同一区间,设为{ta},{sa},(1≤t<s≤n-1), 1 此时|(s-t)a|< ,而 0<s-t<n-1,令 k=s-t,于是必有{ka}落入头尾两个区间之一.故证. n 例 4.M 是 1985 个不同的正整数的集合,M 中每个数的质因数都小于 26,求证:从 M 中一定可以选 出四个不同的数,使它们的积等于一个完全四次方数. 解:M 中的任一个数的质因子只能是 2、3、5、7、11、13、17、19、23 这 9 个数中的某些数.设 a∈M, 则按这 9 个质因子的指数为奇或为偶可把所有 1985 个数分成 29=512 类,由抽屉原理,任取 513 个 M 中的
1

数必有两个数属于同一类, 于是可得(1985-511)÷ 2=737 对数, 每对数都属于同一类, 于是, 737 对数中, 这 每对两数的乘积都是完全平方数,即每个质因子的指数都是偶数.即每个质因子的指数除以 4 后的余数都 只能是 0 或 2,再按这 9 个质因子的指数是 0 或 2 把这 737 个数分类,又可得 512 类,现在 737 个数放入 这 512 类,必有两数同一类,此二数的乘积就是完全四次方数,而乘得此二数的原来 4 个数即为所求. 例 5.6 个代表队共有 1978 名运动员,编上号码 1,2,3,…,1978 号,证明至少有一个运动员,他 的号码等于其两个队友号码的和或者等于某一个队友号码的两倍. 1978-1 解:不妨设第 1 个代表队人数最多,则其人数≥[ ]+1=330 人,设其中最大的号码为 a1,用 a1 6 减其它 329 个号码,得到的差如果在此 329 个数中,则命题已成立.如果这 329 个差都不是第一个代表队 329-1 的号码,那么不妨设其中有[ ]+1=66 个号码在第二个队中,同样设这 66 个号码最大的为 b1,用它减 5 其余 65 个号码, b1-bi=(a1-at)-(a1-as)=as-at 如果在第一或第二个队的号码中, 差 则命题已证, 若不在, 65-1 则此 65 个数必有[ ]+1=17 人同一队,设为第三队,又设其中最大者为 c1,用 c1 减其余 16 个数,其差 4 c1-ci=(b1-bi)-(b1-bj)=bj-bi,而 bj-bi=(a1-at)-(a1-as)=as-at,若在第一,二,三队的号码中,则命 16-1 5-1 题可证,依此类推,若无,则[ ]+1=6,[ ]+1=3 个,其差或是前面某队的号码,或是第 6 队的号码, 3 2 问题总能成立. 例 6.S 是{1,2,3,…,1989}的一个子集,而且 S 中任两个数的差不能是 4 或 7,那么 S 中最多可 有多少个元素?(1989 年第七届美国数学邀请赛) 解:取前 11 个自然数 1、2、3、4、5、6、7、8、9、10、11,排成一个圈:1、5、9、2、6、10、3、 7、11、4、8.这样排好后,任意相邻两数都不能同时被取出,否则其差为 4 或 7.而在这 11 个数中任取 6 数, 就会在上面这个圈中取出了相邻的两个数, 于是这 11 个数中, 最多只能取出 5 个满足要求的数. 例如, 取 1,3,4,6,9 这五个数满足要求. 1989=11× 180+9, 于是把这 1989 个数从 1 开始每连续 11 个数为一组, 每组都取出 5 个数: 11k+1, 11k+3, 11k+4,11k+6,11k+9(k=0,1,2,…,180)共取出 181× 5=905 个数.即 S 中最多可有 905 个元素. 当取出的数超过 905 个时,总有某组数中取出的数超过 6 个,于是就会出现差为 4 或 7 的两个数.从 而 905 为所求. 例 7.一位棋手参加 11 周(77 天)的集训,每天至少下 1 盘棋,每周至多下 12 盘棋,证明这个棋手 必在连续的几天内恰好下了 21 盘棋. 解:这名棋手在 77 天内最多下了 11× 12=132 盘棋. 不妨记他从开始起第 n 天共下了 an 盘棋,则有 a1<a2<…<a77. 再取 77 个数: 1+21, 2+21, a77+21, a a …, 这样共得 77× 2=154 个数. 但这些数最大 不超过 132+21=153. 于是必有两个数相等,这就是说,必有 ai+21=aj(i<j),即从第 i+1 天起,到第 j 天这连续 j-i 天中,这 名棋手共下了 21 盘棋. 例 8.设有小数 A=0.a1a2a3…,如果 ai+2 是 ai+1+ai 的个位数字(i=1,2,3,…),求证:A 是有理数. 解:把 ai,ai+1 组成一组:(ai,ai+1),(i=1,2,3,…),则所有这些组只有以下 100 种可能的取法:(0, 0),(0,1),(0,2),…,(0,9);(1,0),(1,1),(1,2),…,(1,9);…(9,0),(9,1),(9,2),…,(9, 9).而取(a1,a2),(a2,a3),…,(a100,a101),(a101,a102)这 101 组,于是必有两组相同,设为(ai,ai+1),(ai, aj+1),(i<j).于是可得 ai+2=aj+2,ai+3=aj+3,…,即 A 为循环小数,故 A 为有理数. 例 9.已知菲波拉契数列
2

0,1,1,2,3,5,8,13,21,…… (从第三项起,每项都等于它的前面两项的和).试问,它的前 100000001 项中,是否有某一项的末四 位数字全为 0?(不算第 1 项) 分析:添一项可以看作 0000,考虑每一项的末四位数字,末四位数字共有 104 种,(从 0000 到 9999), 而每项的末四位数字都是由其前面两项的末四位数字求和而得出. 解:记每一项 ai 的末四位数字为 xi,由于该数列的每一项都是其前两项的和,由于 xi 有 104 种,xi+1 也 有 104 种,所以有序数对(xi,xi+1)共有 108 种,但对于每一项都有一个有序数对(xi,xi+1)与之对应: (x0,x1),(x1,x2),…,(x100000000,x100000001),共有 100000001 个数对,从而必有两个数对完全一样, 设(xi,xi+1)与(xj,xj+1)相同(i<j). 则有 xi= xj ,xi+1= xj+1,由于 xi-1= xi+1- xi, xj-1= xj+1- xj,故又有 xi-1=xj-1,这样又有 (xi-1,xi)=(xj-1,xj),(xi-2,xi-1)=(xj-2,xj-1),…,直至(x0,x1)与(xj-i,xj-i+1),即 xj-i 与 x0 相同,即 aj-i 的末 四位数字全是 0. 事实上该数列的 7501 项的末四位全是 0. 当两项相邻时的情况. 例 10.设 m、n 都是自然数,任给一个有 nm+1 项的数列(该数列各项互不相等) a1,a2,……,anm+1 证明可以从中选出 m+1 项,按原来的顺序组成递增数列或选出 n+1 项按原来的顺序组成递减数列. 说明:先举一个例说明:m=n=2,在一个 5 项的数列 1,8,3,2,5 中,可以选出一个 3 项的递增数 列:1,3,5;但未能选出 3 项的递减数列来. 解:对于 mn+1 项的数列 a1,a2,…,anm+1 中每一项 ai,都可以从这项开始向后找出以该项为首项的 项数最多的递增数列来,设这样的数列有 xi 项,同时也能找出以该项为首项的项数最多的递减数列来,设 这样的数列有 yi 项,这样,对于每一项 ai,都有一对数(xi,yi)与之对应,这就得到了 mn+1 个数对(可 以看成是 mn+1 个坐标) . 如果所有 xi 都不大于 m,所有 yi 都不大于 n,即 xi=1,2,…,m;且 yi=1,2,…,n.于是这样的数 对只能有 nm 种,将每一种都看成是一个抽屉,但共有 nm+1 个数对,于是根据抽屉原理,必有 2 个数对落 入同一抽屉.设为 ai 与 aj, (i<j),它们都对应着坐标(h,k),这表示从这两个数中的任一个开始,可以向后 找出 h 项组成递增数列,也可向后找出 k 项组成递减数列. 若 ai<aj,则从 aj 起共有 h 项组成递增数列,但加上 ai 后应有 h+1 项,即与 ai 对应的数不应为 h,同样 若 ai>aj,也将引出矛盾. 这说明必有某个 xi 满足 xi>m,或者某个 yi 满足 yi>n 命题得证. 例 11.设实数 x1,x2,x3,…,xn 满足 x12+x22+x32+…+xn2=1 证明对每一个整数 k≥2,存在不全为 0 的整数 a1,a2,…,an,满足 |ai|≤k-1,(i=1,2,…,n) 使 (k-1) n |a1x1+a2x2+…+anxn|≤ n . k -1 证明:对于|ai|≤k-1,有 (a1x1+a2x2+…+anxn)2≤(a12+a22+…+an2)(x12+x22+…+xn2)≤a12+a22+…+an2 ≤(k-1)2+(k-1)2+…+(k-1)2=n(k-1)2. 所以, |a1x1+a2x2+…+anxn|≤(k-1) n. ⑴ 现在取{a1,a2,…,an}?{0,1,2,…,k-1},则共可有 kn 种取法,其每一种取法都满足⑴式. (k-1) n 把区间[0,(k-1) n]分成 kn-1 等份,每份长为 n . k -1
3

则 kn 个数落入此区间内,必有二数落入同一份内.设为 a?1x1+a?2x2+…+a?nxn 与 a?1x1+a?2x2+…+a?nxn, 则它们的差: (a?1-a?1)x1+(a?2-a?2)x2+…+(a?n-a?n)xn= a1x1+a2x2+…+anxn. 必满足|ai|≤k-1 (i=1,2,…,n),且|a1x1+a2x2+…+anxn|≤ (k-1) n . kn-1

例 12.一个棱柱以五边形 A1A2A3A4A5 及 B1B2B3B4B5 分别为上下底,这两个多边 A5 形的每一条边及线段 AiBj(i,j=1,2,3,4,5)均涂上红色与绿色,每个以棱柱的顶 A1 A4 点为顶点,以涂色线段为边的三角形都有两边颜色不同.求证:上底与下底 10 条边 A2 A3 的颜色相同. 证明:首先证明此棱柱的上底面的棱颜色相同.否则必有两条相邻边颜色不 B5 B4 B1 同.不妨设 A1A5 为红,A1A2 为绿. B3 B2 5 条线段 A1Bi(i=1,2,3,4,5)中必有 3 条同色.设有 3 条同为红色.这 3 条红 色的线段中,总有两条是向相邻的两个顶点引出的,例如 A1B1、A1B2 都为红色.于 是在△ A1B1B2 中 B1B2 必为绿色. 又在△ A1A5B1 及△ A1A5B2 中,A5B1 及 A5B2 均必为绿色.这样就得△ A5B1B2 全为绿色.矛盾.这说明上 底面的 5 条棱同色. A5 同理,下底面的 5 棱也同色. A1 A4 下面再证明,上下底面 10 条棱颜色全同.反设上底面 5 条棱钱红,下底面 5 条 A2 A3 棱全绿.由上证,A1B1、A1B2 不能全红,但也不能全绿,故必一红一绿,设 A1B1 红, 则 A1B2 绿,同理得,A1B3 红,A1B4 绿,A1B5 红,此时,△ A1B1B5 又出现上证情况.故 B5 B4 得证. B1
B2 B3

练习题 1. 在 3× 4(cm)的长方形中,放置 6 个点,试证:可以找到两点,其距离不超过 5 cm. 解 先把长方形分成 5 个区域(如图),根据抽屉原理,必有两个点在同一个区域内,因而它们的距离不 超过 5 cm. 2. 是否存在由 10 个正整数组成的集合 A, A 的任一 6 元子集的元素和都 ⑴ 使 不能被 6 整除? ⑵ 对于任一由 11 个正整数组成的集合 A,证明:一定可以找到它的一个 6 元 子集,其和能被 6 整除. ⑴解:取 A={1,7,13,19,25,6,12,18,24,30},则 A 的任一六元子集的元素和都不能被 6 整 除. ⑵证明:对于任一元素都是正整数的 11 元集 A,总可以把这 11 个元配成 5 组,每组二个数的奇偶性 相同,于是同组两数的和为偶数,这样就得到 5 个偶数和.这 5 个偶数 mod 3 后,如果有 3 个数 mod 3 互 不同余,则此三数的和被 3 整除;如果这样的 3 个数不存在,即 mod 3 后只有至多两个剩余类,则其中必 有 1 类中至少有 3 个数,则此三个数的和被 3 整除.于是取加得这三个数的原来的六个数,其和被 6 整除. 3.把大小圆盘各划分成 n 个相等的扇形格,各依次填上实数 a1、a2、…、an 及 b1、b2、…、bn,然后 把把两圆盘圆心重叠做成转盘,试证:若 a1+a2+…+an<0, b1+b2+…+bn<0, 则必可以使转盘转到某个适当位置,使大小圆盘对应扇形上两个数的乘积的和为一个正数. 证明:让小盘逐格转动,每次都记下大小圆盘对应扇形上两个数的乘积的和,这样转过 n 次后,共得
4

到了 n 个和.由于大盘上的每个数字都要与小盘上的每个数字对应一次,故乘积 aibj(i,j=1,2,3,…, n)在这 n 个和中都出现一次且只出现一次,故这 n 个和的总和=(a1+a2+…+an)( b1+b2+…+bn)>0. ∴这 n 个和不可能都小于≤0,即其中至少有一个和为正数. 4.已知自然数 n(n>1),用小于 n 的自然数组成两个数组,每组内的数都各自两两不同,但两组间的数 不一定全不同.证明:若两组数的总个数不小于 n ,那么,一定可以从每一组中各选一个数,其和为 n. 证明:设所组成的两个数组分别为 A={a1、a2、…、ak}及 B={b1、b2、…、bh}.其中各个 ai 互不相同, 各个 bj 也互不相同.且 k+h≥n. 现取一数组 C={c1,c2,…,ch},使 cj=n-bj,于是各 cj 均为小于 n 的正数,也互不相同. 由于数组{ a1、a2、…、ak,c1,c2,…,ch }的元素都为小于 n 的正整数,但 k+h≥n.从而必有某个 cj=ai, 于是 ai+bj=n. 5.给定 13 个不同的实数 a1,a2,…,a13,求证:存在两个实数 ai,aj,(i?j),满足 0< ai-aj < 1+aiaj 2- 3 . 2+ 3

证明:令 tan?i=ai(-

?
2

<?i<

?
2

,i=1,2,…,13), 1- 1+ 3 2 3 2 1-cos = 1+cos ,

?
6 =tan

ai-aj 则有 tan(?i-?j)= < 1+aiaj

2- 3 = 2+ 3

?
6

?
12



故只要把这 13 个角按从大到小排列,并把区间(-

?
2

?
2

)分成 12 等分,则总有一个区间内落入了二

个所给的角?i,?j,(?i>?j),这两个角对应的实数即为所求. 6.在[1,1000]内任取 n 个互不相等的数 a1,a2,…,an,为了总可以找到两个数 ai,aj(1≤i<j≤n), 使得 ____ 0<ai-aj<1+3? aiaj 成立,试确定 n 的最小值并证明之. __ __ 解:设 ai>aj,且 0<? ai -? aj <1, 于是,立方之,得 ____ __ __ 0<ai-aj-3? aiaj (? ai -? aj )<1. ∴ ____ __ __ ____ 0< ai-aj<1+3? aiaj (? ai -? aj )<1+? aiaj .

____ 如果取 n=10,可令 ai=i3,此时当 i>j 时,ai-aj=i3-j3=(i-j)3+3ij(i-j)≥1+3ij=1+? aiaj 当取 n=11,及区间[i3,(i+1)3],(i=1,2,…,9).于是这 11 个数中必有两个数落入同一区间.由于这 些区间共有 10 个端点,故这 11 个数不可能只取这 9 个区间的端点值 i3,于是必存在两个数落入同一区间 且其中至少有一个数不是区间的端点.则此二数满足要求. 7.证明:存在着绝对值都小于一百万,不全为 0 的三个整数 a,b,c,使 |a+ 2 b+ 3 c|<10
-11


5

证明:令 A={x∈N |0≤x<106}.M={ r+s 2 +t 3 | r,s,t∈A}.d=(1 + 2 + 3 )· 6. 10 若 x∈M,则 x∈[0,d]. 把区间[0,d]分成 1018
-1

个长度为 l=

d 的子区间. 10 -1
18

由抽屉原理,M 中 1018 个数中必有两个数同在某个子区间内,此二数之差<l< 即此二数之差满足要求.

107 - <10 11. 1018-1

8.我们称 A1,A2,…,An 为集合 A 的一个 n 划分,如果 ⑴ A1∪A2∪…∪An=A; ⑵ Ai∩Aj=?,1≤i<j≤n. 求最小的正整数 m,使得对 A={1,2,…,m}的任意一个 14 划分 A1,A2,…,A14,一定存在某个集合 Ai(1 4 ≤i≤14),在 Ai 中有两个元素 a,b 满足 b<a≤ b.(中国西部 2001 数学奥林匹克) 3 分析:14 个集合相当于 14 个抽屉,取 15 个数,则必有一个抽屉中有两个数.若 15 个数中任意两个 4 的数都满足 b<a≤ b,则可求出最小的 m 值. 3 b+14 4 解:取 b,b+1,b+2,…,b+14,共 15 个数.若 ≤ ,即得 b≤42.即至少取 42+14=56 个数, b 3 就可保证对 A 的任一划分满足要求. 当 m≥56 时,取出其中 42,43,…,56,共 15 个数,则根据抽屉原理,必有两数 b,a(42≤b<a≤56) a 56 4 4 在同一划分中,由于 1< ≤ = ,即 b<a≤ b 成立. b 42 3 3 d 若 m<56.取 Ai={a|a≡i(mod 14),0<a<56},则对于 Ai 中任意两个数 c,d(c<d),显然,c≤42.故 ≥ c c+14 14 14 4 =1+ >1+ = ,即此时不存在满足要求的划分. c c 42 3

6


推荐相关:

高中竞赛专题:抽屉原理

高中竞赛专题:抽屉原理_理学_高等教育_教育专区。数学竞赛竞赛讲座 10 --抽屉原则 --抽屉原则大家知道,两个抽屉要放置三只苹果,那么一定有两只苹果放在同一个抽屉...


浅谈抽屉原理在高中数学竞赛中的运用

浅谈抽屉原理高中数学竞赛中的运用 浅谈抽屉原理高中数学竞赛中的运用 抽屉原理在数学问题中有一类与“存在性”有关的问题,例如:“13 个人中至少有两个人出生...


抽屉原理(高中)

抽屉原理习题精选 2页 免费 2011全国高中数学竞赛讲义... 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


浅谈抽屉原理在高中数学竞赛中的运1

浅谈抽屉原理高中数学竞赛中的运用 浅谈抽屉原理高中数学竞赛中的运用 抽屉原理在数学问题中有一类与“存在性”有关的问题,例如:“13 个人中至少有两个人出生...


抽屉原理与高中数学竞赛

摘 要 本论文首先讨论了抽屉原理的一般含义和它的两种推广形式;其次给出了抽屉原理在 整除问题、面积问题、染色问题、六人集会问题以及生日问题等高中数学竞赛问题中...


抽屉原理(中)

抽屉原理(中)_高考_高中教育_教育专区。7 一、抽屉原理 抽屉原理与极端原理 美国一家杂志上曾刊登这样一副漫画:三只鸽子同时往两个鸽笼里飞。这是一副含义深刻...


抽屉原理(上)

抽屉原理(上)_高考_高中教育_教育专区。7 一、抽屉原理 抽屉原理与极端原理 美国一家杂志上曾刊登这样一副漫画:三只鸽子同时往两个鸽笼里飞。这是一副含义深刻...


23(高中竞赛讲座)抽屉原理

高中数学竞赛讲座 23 23 抽屉原理在数学问题中有一类与“存在性”有关的问题,例如: 在数学问题中有一类与“存在性”有关的问题,例如:“13 个人中至少有两个人...


抽屉原理案例研究(原)

抽屉原理案例研究(原)_理化生_高中教育_教育专区。《抽屉原理》教学有效性研究与思考建构模型 化繁为简 建构模型 ---《 ---《抽屉原理》教学有效性研究与思考 ...


高中数学竞赛讲义-抽屉原理

高中数学竞赛讲义-抽屉原理_学科竞赛_高中教育_教育专区。数学教育网---数学试题-数学教案-数学课件-数学论文-竞赛试题-中高考试题信息 http://www.qyjzs.cn ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com