高中数学竞赛讲解之抽屉原则素材新人教版

1 抽屉原则抽屉原则 在解决存在性问题时 抽屉原则是一个强有力的工具 抽抽屉屉原原则则 将一个元素个数不少于 的集合划分为 个子集 nm 1 A 2 A m A 则至少有一个子集 2 其元素个数 1 k A k m 1 1 k n A m 其中 表示的最大整数 xx 推推论论 把一个元集划分为个子集 则至少有一个集合含有至少nm nm 两个元素 我们称这里的子集 为个 抽屉 应用抽屉原则解题的关 1 A 2 A m Am 键是构造合适的抽屉 在不同的实际问题中抽屉的表现形式是不一样的 即使 是对同一问题也可以从不同角度制造不同的抽屉 抽抽屉屉原原则则 I 从个互不相交的有限集中 取出个元素构m 1 A 2 A m A1km 成一个集合 则中至少有个元素属于某个 2 SS1k 1 p Ap m 抽抽屉屉原原则则 将一个元素不多于的集合划分为个子集 nSm 1 A 2 A m A 则至少存在一个集合 2 其元素数目 1 k A k m k n A m 抽抽屉屉原原则则 把一个无限集划分为有限个子集 则至少存S 1 A 2 A m A 在一个集合 2 仍为无限集 1 p Ap m 例例1 已知集合 是正整数 是的子集 满足 1S 23 3nnTS 对任意 其中 可以相同 都有 求所有这种集合xyzT xyzxyzT 的元素个数的最大值 T 解解析析 考虑中那些较大的数 取 显然 其中S 0 1Tn 2n 3n 任三数之和大于 故 3n 0 max2TTn 另一方面 作三元子集列 0 An 2n 3n k Ak 2nk 2nk 1k 2 1n 则 对于的任一个元子集 必包含有某个 1 0 n k k SA S21n T k A 若 则其中有元素 0 AT 3nnnn 2 若某个 则其中有元素 k AT 1k 2 1n 2 2 nkkknk 于是 max21Tn 所以 max2Tn 抽屉原则应用过程中的抽屉制造实质就是对问题涉及的某些对象进行分类 因此 首先应弄清楚对哪些对象分类 分多少类 按什么规则分 例例2 从 中任意选个数 证明 一定存在两个数的差恰12 38391996 好等于 96 解解析析 按模的余数 把整数分类为类 现有个数 96012 95961996 且 故由抽屉原则可知 在这个数中必有个数属于同199696 2076 199621 一类 即这个数中任意两数的差都是的倍数 2196 如果这个数中 每两个数之差都不是 那么这样的最小的个数是 219621 1 0 96ar 2 2 96ar 3 4 96ar 21 2 20 9638403839ar 095 r 这与已知条件不符 所以 选出的个数中一定存在两数之差恰好等于 199696 例例3 一位棋手参加周 天 的集训 每天至少下一盘棋 每周至多下1177 盘棋 证明 这位棋手必定在连续的几天内恰好下盘棋 1221 解解析析 用表示这位棋手在第 天至第 天 包括第 天在内 所下的棋的总盘 i S1ii 数 由于棋手每天至少下一盘棋 所以 177 i 1277 SSS 又由于棋手每周至多下盘棋 所以12 77 12 11132S 要证明存在 使 这只需证明在 ij177ji 21 ij SS 1 S 2 S 77 S 1 21S 中有两项相同即可 77 21S 事实上 上面的个数中最小的 最大77 2154 1 的 77 21 13221 153S 由抽屉原则 I 必有两数相同 例例4 试卷上共有 4 道选择题 每题有 3 个可供选择的答案 一群学生参 加考试 结果是对于其中任何 3 人 都有一个题目的答案互不相同 问参加考 3 试的学生最多有多少人 解解析析 设每题的 3 个选择支为 如果参加考试学生有 10 人 则由抽abc 屉原则 知 第一题答案分别为 的三组学生中 必有一组不超过 3 人 abc 去掉这组学生 余下的学生中选出 7 人 则他们对第一题的答案只有两种 对 于这 7 人关于第二题应用抽屉原则 知其中必可选出 5 人 他们关于前两题的 答案都只有两种可能 对于这 5 人关于第三题应用抽屉原则 又知可选出 4 人 关于第四题应用抽屉原则 知必可选出 3 人 他们关于 4 个题目的答案 都只有两种 这不满足题中的要求 可见 所求的最多人数不超过 9 另一方 面 如果 9 个人的答案如下表所示 则每 3 人都至少有一个问题的答案互不相 同 123456789 1aaabbbccc 2abcabcabc 3abccabbca 4abcbcacab 所以 所求的人数最多为 9 例例5 设 是任意一个具有性质的正整数的无 1 a 2 a n a 1 1 kk aak 穷序列 求证 这个数列中有无穷多个可以表示为 m a mpq axaya 其中 是适当的正整数 且 pqxypq 解解析析 在给定的数列中任意取一项 因为是正整数 把全体正整数按 q a q a 的剩余类分类 由于正整数 有无穷多个 所以由抽屉mod q a 1 a 2 a n a 原则 上述个分类中至少有一类含有数列中的无穷多项 再由最小数原理 q a 这无穷多个项中一定有一个最小的项 于是对这个剩余类中的其他任意一项 p a 都有 m a 且 mod mpq aaa mp aa 所以为某个正整数 取 即有 mpq aaa y y 1x mpq axaya 例例6 在不超过的非零自然数中任意取 10 个数 证明 这 10 个数中一91 定有两个数的比值在区间 内 2 3 3 2 解解析析 不超过 91 正整数共 91 个 要把这些数分成组 使x 人数 题目 人数 4 10 1 12 x 可取的最大值是 9 现将 这个数分为 9 组 x12 909191 1 2 3 45 6 78 9 10 1112 16 1718 25 2627 39 4041 60 6162 91 这 9 个组的每个组中任意两数之比适合 由抽屉原则 I 从这 9 个k 23 32 k 组中任意取 10 个数必有两数取自同一组 其比值在 内 2 3 3 2 在这里显然抽屉的个数不能多于 9 个 分类的规则是使每个抽屉中的任意 两数之比落在区间 内 2 3 3 2 例例7 对一个的格阵用红 蓝两色进行染色 如果对任意一种染色方5 n 案总可找到由 3 行 3 列相交出的同色的 9 个方格 求的最小值 n 解解 析析 对于每一例 我们考虑相对 均匀 的染法 将其中 3 个方格染上 一种颜色 其余 2 个方格染上另一种颜色 这样的不同染色方法共有 种 3 5 220C 这提示我们 将格阵的前 20 列用上述 20 种不同染法染色 后 20 列5 40 也依前 20 列的方法对应进行染色 这样的话 无法找到满足题意的同色的 格阵 故至少应为 41 3 3 n 如果还是上述 均匀 的染法 那么只要再多一列 即 就必定出41n 现满足题意的的同色格阵 如果不全是 均匀 的染法 是否还能3 3 41n 出现 的同色格阵呢 3 3 我们得换一个思路 若 因每列红 蓝格数必不相等 所以 至少41n 有 21 列 每列染某种颜色的格数大于染另一种颜色的格数 不妨设至少有 21 列每列的红格数大于蓝格数 即每列至少有 3 个红格 可退一步 设这 21 列 每列恰好有 3 个红格 则对应的染色方法有种 3 5 10C 由抽屉原则知 21 列中必有 3 列染法相同 这三列的红色方格即构成的3 3 同色格阵 故的最小值为 41 n 5 例例8 在区间 里任意取个不同的数 为了总可找到 1 1000n 1 a 2 a n a 两个数 使得 i a j a ij 1i jn 3 01 3 ijij aaa a 成立 确定的最小值 并证明之 n 解析解析 不等式成立的一个充分条件是 3 01 3 ijij aaa a 3 3 01 ij aa 令 则问题转化为在区间 里任意取个不同的数 3 ii aa 3 jj aa 1 10n 1 a 2 a 从中总存在两数 使得 n a i a j a ij 1i jn 01 ij aa 将区间 分成长度小于 1 且互不重叠的区间 则至少要分出 10 个这样 1 10 的区间 如 由抽屉原则 I 知 即 12 23 9 9 5 9 5 1011n 可 这说明所求的最小值不超过 11 n 当时 令 那么10n 3 i ai 1i 2 10 ij 3 3 1 3 ij aaijij ijij 不适合条件 故所求的为 11 n 例例9 一个圆内有 6000 个点 其中任意三点都不共线 1 能否用直线把这个圆分成 2000 块 使每块恰含有 3 个点 如何分 2 若每块中三点满足 两两之间的距离皆为整数且不超过 9 则以每块 中的三点为顶点作三角形 这些三角形中大小完全一样的三角形至少有多少个 解解析析 1 圆内个点可确定条直线 因是个有限的数 所以6000 2 6000 C 2 6000 C 一定存在圆的一条切线 使它不平行于这条直线中的任何一条 记这条切 2 6000 C 线为 将 在圆上作平行移动 显然个点将被逐个越过 如同时越过两个ll6000 点 则连接此两点的直线必与 平行 这与 取法不合 于是 在 越过 个点lll3 且未遇上第4个点时作圆的一条弦 同理 当越过第 点时作弦 1 l45 6 2 l 如此可作出条弦 将圆分成块 每块都含 个点 199920003 2 以上述每块中的三点连成一个三角形 共可得到个三角形 可以2000 求得 边长均为整数 最长边不超过 的三角形的个数为 995 设三角形的三边长分别为 均为整数 不访设 abcabc9abc 6 当且时 有如下表 9c abc 的取值b可取之值a三角形的个数 551 6 4563 7 345675 8 2345 87 91 2345 99 即当时 可以得到不同的三角形个 同理 当 9c 258c 7654 3 时 不同的三角形的个数分别是 212016129 6421 故边长均为整数 且最长边不超过 的大小不同的三角形总个数是9 12469 12 16202595 根据抽屉原则 个三角形中大小完全一样的三角形至少有2000 个 2000 122 95 例例10 用种颜色给直角坐标平面中某些整点染色 使得任何半径为 的kc 圆内部至少有一个染了色的整点 求证 存在一个个顶点染了相同颜色且各4 边平行于坐标轴的矩形 解析解析 取 则在任意一个边长为的正方形内部能作一个半径21nc 1n 为 的圆 从而正方形内部至少有一个染了色的整点 于是在每个以 c 1rn 1 sn 为顶点的正方形内部至少可标出 rnn 1 sn 1rn snn rnn snn 一个染色的整点 r s A r s x r s y r sZ 对于每个给定的 考虑个点 这个点的横坐r1kn 0r A 1r A r kn A1kn 标为 这个值之一 由抽屉原则 必有至少个点的1rn 2rn rnn n1k 横坐标相同 而这些横坐标相同的点染的颜色只有种可能 从而存在两个横k 坐标相同的点同色 即存在 使得 且 同 12 0sskn 1 r s x 2 r s x 1 r s A 2 r s A 色 设它们均为第种颜色 则称 为色坐标对 j 1 jk 1 r s Y 2 r s Yj 1 1 r s Y 2 2 r s Yknn 取 故存在至少个同色坐标对相同 设为 2 2 knn tkC 1k 11 r s Y 12 r s Y 21 r s Y 22 r s Y 11 k rs Y 12 k rs Y 其中 所以对应的个点对 121 0 k rrrt 1k 11 r s A 12 r s A 21 r s A 22 r s A 的染色仅有种可能 每个点对染一种颜色 故有两个点对 11 k rs A 12 k rs A k 7 同色 设为 和 同色 这里 故以 1 ir s A 2 ir s A 1 j r s A 2 j r s A11ijk 1 ir s A 2 ir s A 为顶点的矩形即满足要求 1 j r s A 2 j r s A 例例11 某次考试有 5 道选择题 每题都有 4 个不同答案供选择 每人每题 恰 选1个答案 在 2000 份答案中发现存在一个 n 使得任何 n 份答卷中都存在 4 份 其中每两份的答案都至多 3 题相同 求 n 的最小可能值 解解析析 将每道题的种答案分别记为 每份试卷上的答案记为 41234 g 其中 令hij kghij 1k 23 4 1hij k 2hij k 3hij k 4hij k 共得个四元组 由 故由抽屉hij 1k 23 42562000256 7208 原则知有 份考卷上的答案属于同一个四元组 取出这 份考卷后 余下的88 份中仍有 份属于同一个四元组 再取出这 份考卷 余下的份中又1992881984 有 份属于