第一节-鸽巢原理

鸽巢原理及其他鸽巢原理及其他 第一节第一节 鸽巢原理鸽巢原理 关于鸽巢原理的阐释 粗略地说就是如果有许多鸽子飞进不够多 的鸽巢内 那么至少要有一个鸽巢被两个或多个鸽子占据 一一 鸽鸽巢巢原原理理的的简简单单形形式式 1 1 定定理理1 1 如如果果要要把把n n 1 1个个物物体体放放进进n n个个盒盒子子 那那么么至至少少有有一一个个盒盒 子子包包含含两两个个或或更更多多的的物物体体 证明 用反证法进行证明 如果这n个盒子中的每一个都至多含有一 个物体 那么物体的总数最多是n 这与有n 1个物体矛盾 所以某 个盒子至少有两个物体 2 2 定定理理1 1的的说说明明 无论是鸽巢原理还是它的证明 都不能具体找出 含有两个或更多物体的盒子 它只是证明这样的盒子存在 即如果 人们检査每一个盒子 那么他们会发现有的盒子里面放有多个物体 另外 当只有n个 或更少 物体时 是无法保证鸽巢原理的结论的 这是因为可以在n个盒子的每一个里面放进一个物体 所以鸽巢原 理 成立的条件是至少为n 1个物体 3 3 鸽鸽巢巢原原理理的的两两个个简简单单应应用用 应应用用1 1 在13个人中存在两个人 他们的生日在同一个月份里 应应用用2 2 设有n对己婚大妇 至少要从这2n个人中选出多少人才能保 证能够选出一对夫妇 为了在这种情形下应用鸽巢原理 考虑n个房间 其中一个房间 对应一对夫妇 如果选择n十1个人并把他们中的每一个人放到他们 夫妻所对应的那个房间中去 那么就有一个房间含有两个人 也就 是说 已经选择了一对已婚夫妇 选择n个人使他们当中一对夫妻也 没有的两种方法是选择所有的丈夫和选择所有的妻子 因此 n 1是 保 证能有一对夫妇被选中的最小的人数 4 4 从从应应用用2 2得得出出的的两两个个推推论论 推推论论1 1 如果将n个物体放入n个盒子并且没有一个盒子是空的 那么 每个盒子恰好有一个物体 说明 以应用2为例 选择n个人 如果其中有一对夫妻 那么必然 有一个房间是空的 为了保证没有空房间 则必须从每对夫妻中选 一个人 即恰好从每对夫妻中选一个人 推推论论2 2 如果将n个物体放入n个盒子并且没有盒子被放入多于一个的 物体 那么每个盒子里恰好有一个物体 说明 以应用2为例 选择n个人 每个房间只能是夫妻中的一个人 2n个人 恰好每个从每对夫妻当中选择一个人 5 5 例例题题 例1 给定m个整数a1 a2 am 存在满足0 k l m的整 数k和l 使得ak 1 ak 2 al能够被m整除 分析 题目通俗化 即给定m个整数的序列 其中连续几个的和能被 m整除 所以考虑序列中连续和的情况 如果其中任何一个能被m整 除 那么结论就成立了 对此 只能先假设连续和不能被整除 即 有余数 解 找出鸽子 m个正整数连续和 即a1 a1 a2 a1 a2 a3 al a2 a3 am共m个和 构造鸽巢 连续和不能被整除 那么余数必然为1 2 m 1共 m 1个 如果余数为0或m 则已经整除结论成立 所以只能是m 1个 鸽巢原理 m个和 m 1个余数 那么必然有两个余数是相同的 因此存在整数k和l 0 k l m 使得al a2 a3 ak及al a2 a3 al除以m有相同的余数 不妨设 al a2 a3 ak cm r al a2 a3 al dm r 其中c d r为正整数 可得 ak 1 ak 2 al d c m 从而可得ak 1 ak 2 al能够被m整除 特例如下 设m 7 且整数为2 4 6 3 5 5 6 计算上面的和得到 2 6 12 15 20 25 31 这些整数被7除时余数分别为2 6 5 1 6 4 3 有两个等于 6的余数 这意味着结论 6 3 5 14可被7 整除 例2 一位国际象棋大师有11周的时间备战一场锦标赛 他决定每天至少 下一盘棋 但为了不使自己过于疲劳他还决定每周不能下超过12盘 棋 证明存在连续若干天 期间这位大师恰好下了 21盘棋 分析 问题通俗化即连续若干个正整数的和恰好为21 实际问题转 化为数学模型 即构造一个用来表示若干天下棋总盘数的数列 然 后用鸽巢原理证明 证明 找出鸽子 设a1是在第一天所下的盘数 a2是在第一天和第 二天所下的总盘数 a3是在第一天 第 二天和第三天所下的总盘数 11周总共77天 以此类推 a77表示77天下的总盘数 因为每天至少 要下一盘棋 故a1 1 因为在任意一周最多下12盘棋 所以a77 1 2x11 132 则有序列1 al a2 a3 a77 132 为一个严格递增序列 根据若 干个正整数的和为21这一提示 构造数序列al 21 a2 21 a3 21 a77 21 此序列也是 严格递增序列 由此可得al a2 a3 a77 al 21 a2 21 a3 21 a77 21共77 77 154个数 构造鸽巢 由1 al a2 a3 a77 132 则有 1 21 al 21 a2 21 a3 21 a77 21 132 21 153 由此可得al a2 a3 a77 al 21 a2 21 a3 21 a77 21是从1到153的正整数 鸽巢原理 al a2 a3 a77 al 21 a2 21 a3 21 a77 21共154个数 而这些数是 从1到153的正整数 从而可知其中必然存在两个数是相等的 而al a2 a3 a77严格递增 各不相等 al 21 a2 21 a3 2 1 a77 21也严格递增且各不相等 那么必然有如下相等的情况 存在一个正整数i和一个正整数j 使得ai aj 21 ai为大师在前i 天所下的盘数之和 aj为大师在前j天所下的盘数之和 ai aj 21即为大师从第j 1天 第j 2天到第i天 下了21盘棋 例3 从整数1 2 200中选出101个整数 证明 在所选的这 些整数之间存在两个这样的整数 其中一个可被另一个整除 证明之前 先介绍一种正整数的表示方法 正整数有奇数有偶数 而任何一个偶数 都可以通过提取因数2 变为奇数与若干个2乘积 的形式 例如8 1x2x2x2 24 3x2x2x2 写成一般形式即奇数x2n 其中n 1 2 3 而这个奇数绝不会超过这个偶数的一半 下面 来证明例3 证明 找出鸽子 1到200中任意选出的101个整数 构造鸽巢 用奇数x2n的形式 把1到200的整数全部列出 1 1x21 1x22 1x27 3 3x21 3x22 3x26 5 5x21 5x22 5x25 99 99x21 199 这样 就把1到200的全部整数列出 共100行 鸽巢原理 101个整数放到100行内 必然有两个整数在同一行 这 两个数表示为p ax2m q ax2n 其中 a为奇数 1 a 199 m n为 正整数 不妨设n m q p ax2n q ax2m 2n m 二二 鸽鸽巢巢原原理理的的加加强强形形式式 1 1 定定理理2 2 如如果果要要把把多多于于m mx xn n 比比如如m mx xn n 1 1 个个物物体体放放进进n n个个盒盒子子 那那么么至至少少有有一一个个盒盒子子包包含含m m 1 1个个或或m m 1 1个个以以上上的的物物体体 例4 空间有六个点 其中任何三点都不共线 任何四点都不共面 在每两点之间连接直线段后涂色 将每一条这样的线段图成红色或 蓝色 求证 不论如何涂色 一定存在一个三角形 它的三边有相 同的颜色 证明 找出鸽子 从一点出发 连接的空间直线段有5条 即2x2 1 条 构造鸽巢 红色和蓝色 鸽巢原理 根据定理2 则至少有三条 线段的颜色是相同的 如图 三条实线段颜色相同 虚线连接三条 线 段的端点 三条虚线段颜色不同时 则与 实现三条实线段构成颜色三边颜色相同 的三角形 三条虚线段颜色相同 但与三 条实线段颜色不同时 由虚线段构成的三 角形就已经符合结论了 2 2 定定理理3 3 设设q ql l q q2 2 q q3 3 q qn n 是是正正整整数数 如如果果将将q ql l q q2 2 q qn n n n 1 1个个物物体体体体放放进进n n个个盒盒子子内内 那那么么或或者者第第一一个个盒盒子子至至少少包包含含q ql l个个物物 体体 或或者者第第二二个个盒盒子子至至少少包包含含q q2 2个个物物体体 或或者者第第n n个个盒盒子子至至少少 包包含含q qn n个个物物体体 证明 ql q2 qn n 1 ql 1 q2 1 qn 1 1根据鸽巢原理 可得第i个盒子至少包含qi个物体 i 1 2 反正法 设第i个盒子含有少于qi个物体物体 那么物体的总数为 ql 1 q2 1 qn 1 ql q2 qn n 比物体总数少1个 与题设矛盾 故结论成立 说明 上述结论中 当物体总数为ql q2 qn n时 则有第i个盒子不含有qi或者更多个物体 i 1 2 只需 将qi 1个物体分配到第i个盒子即可实现 例5 个果篮装有苹杲 香蕉和橘子 为了保证篮子中或者至少有8个苹果 或者至少 有6个香蕉 或者至少有9个橘子 则放人篮子中的水果的最小件数 是多少 解 根据定理3可得 所需的水果最小件数为8 6 9 3 1 21件 3 3 从从定定理理3 3得得到到的的一一个个推推论论 推推论论3 3 设设n n和和r r都都是是正正整整数数 如如果果把把n n r r 1 1 1 1个个物物体体分分配配到到n n个个盒盒子子中中 那那么么至至少少有有一一个个盒盒子子含含有有r r或或更更多多个个 物物体体 证明 n r 1 1 nr n 1 令定理3中ql q2 qn r 则结论成立 4 4 由由推推论论3 3得得到到的的3 3个个平平均均原原理理 平平均均原原理理1 1 如果n个非负整数 ql q2 q3 qn的平均数 大于r 1 即 ql q2 qn n r 1 那么那么这n个数中 至少有一个整数大于r 1 即大于或等于r 分析 根据推论3 如果n r 1 1个物体平均分配到n个盒子中 除一个盒子为r个物体外 其余 盒子均为r 1个 反过来 如果平均数要大于r 1 那个必然一个盒子中的物体数量要大于或等于r 证法1 ql q2 qn n n r 1 1 n r 1 1 n r 1 r N 则必有qi r i 1 2 证法2 反证法 不妨设ql q2 qn r 1 即设这n个整数全部比r小 则有 ql q2 qn n r 1 与题设 r 1矛盾 所以这n个数不可能全部小于r 则必至少有一个大于或等于 r 平平均均原原理理2 2 如果n个非负整数 ql q2 q3 qn的平均数 小于r 1 即 ql q2 qn n r 1 那么那么这n个数中 至 少有一个整数小于r 1 分析 根据推论3 如果n r 1 1 因为平均数小于r 1 所以设为n r 1 1 其平均数才能小于r 1 个物体平均分配到n个盒子中 除一个盒 子为r个物体外 其余盒子均为r 1个 反过来 如果平均数要小于r 1 那个必然一个盒子中的物体数量要小于或等于r 证明 ql q2 qn n n r 1 1 n r 1 1 n r 1 r N 平平均均原原理理3 3 如果n个非负整数 ql q2 q3 qn的平均数 至少等于r 即 ql q2 qn n r 那么这n个数中 至少有一 个整数大于等于r 证明 令平均原理中的r 1 u 则结论成立 例5 有两个碟子 其中一个比另一个小 它们都被分成200个均等 的扇形 在大碟子中 任选100个扇形并着成红色 而其余的100个 扇形着成蓝色 在小碟子中 每一个扇形或者着成红色 或者着成 蓝色 所着红色扇形和蓝色扇形的数目没有限制 然后 将小碟子 放到大碟子上面使两个碟子的中心重合 证明 能够将两个碟子的 扇形对齐使得小碟子和大碟子上相同颜色重合的扇形的数目至少是1 00个 证明 设小碟子蓝色扇形的数量为x 红色扇形的数量为y 大碟子 不动 转动小碟子 每转2 200角度 就有一次对应 于是共有20 0次对应 大碟子的红色扇形有100个 小碟子的红色扇形有x个 那 么转动一周 小碟子每个红色扇形与大碟子对应100次 所以红色扇 形对应的次数共有100 x次 同理 蓝色对应的次数为100y 次 颜色相同的对应次数为100 x 100y 100 x y 100 200 20000次 那么每个位置颜色相同的平均次数为20000 200 100 根据平均原 理3 则有某个位置颜色相同的扇形数目至少为100个 习习 题题 1 在边长为1的正方形内任意放置5个点 求证其中必有两个点 这 两个点之间的距离不大于 2 2 证明 如图将正方形等分成4份 根据 定理1可知 必然有2个点落在正方形 的1 4区域内 这两点的距离小于1 4 小正方形的对角线长 2 2 2 在边长为1的正方形内任意放入9个点 证明 以这些点为顶点的 许许多多三角形中 必有一个三角形的面积不超过1 8 证明 如图 将正方形 用平行于边的平行线等 分为4分 取1 4 由 定理2可知 2x4 1 9个点放入4个盒子内 比然有一个盒子内有 2 1 3个点 现在讨论这三个点构成的三角形的面积 S ABC S AA C S AA B 1xhx1 2 1x 1 4 h x1 2 1 8 3 证明 每个由n2 1个实数构成的数列 a1 a2 an 1或者含有长度为n 1的递增子数列 或者含有长度为n l的递减子数列 分析 当n 1时 n2 1 2 即该数列的长度为2 n 1 2 即含有长度为2的单调子数列 两个实数构成实数列 必然是单调的 当n 2时 n2 1 5 即该数列的长度为5 n 1 3 按题意应该能从中找出长度为3 的单调子数列 这就是题目所要表达的意思 在证明之前 补充一下与数列相关的定义 数数列列 按照一定顺序排列起来的数串a1 a2 an an 1 叫数列 数数列列的的长长度度 数列项数的数量成为数量的长度 有有穷穷数数列列 数列的项数是有限的称为有穷数列 无无穷穷数数列列 数列的项数是无限的称为无穷数列 若al a2 a3 an an 1 则为单单调调递递增增数数列列 若al a2 a3 an an 1 则为单单调调递递减减数数列列 单调递增数列和单调递减数列统称为单单调调数数列列 由由相相等等的的数数构构成成的的数数列列也也可可称称为为单单调调数数列列 去掉上述单增和单减数列中的等号 则为严严格格单单调调数数列列 从原数列中抽出一部分 但不改变它们在原数列中的先后顺序 这 样得到的一个新数列称为原数列的子子数数列列 子数列用ai1 ai2 ain ain 1 表示 其脚标必须满足 1 1 i i1 1 i i2 2 i in n i in n 1 1 原原数数列列本本身身也也是是其其子子数数列列 原原数数列列中中抽抽出出1 1项项构构成成的的数数列列也也是是其其子子数数 列列 下面证明例3 证明 记原数列为a1 a2 an an 1 an 1 先考虑递减的情况 设以ai为首项的最长递减 数列的长度为Ni 下面看一个特例 任意写一个长度为5的数列如 5 9 88 22 31 以5为首项的递减数列的长度为1 以9为首项的递减 数列的长度为1 以88为首项的递减数列的长度为3 由此可知 Ni 1 且对于长度为n2 1的数列 Ni为n2 1个正整数 如果原数列中没有长度为n 1的递减数列 则Ni为1到n 之间的n2 1个正整数 根据定理2可知 其中必然有n 1个数是相等的 例如 n 3时 n2 1 10 10个数分配到1 2 3三个盒子中 必然有4个数都为1 或者 都为2 或者都为3 n 1个数相等记为Ni1 Ni2 Nin 1 其脚标适合1 i1 i2 in in 1 i n2 1 这就是说 原数列中有n 1个递减子数列的长度是相等的 任意 列出其中两个如下 ai1 ai5 ain ain 1 ai2 ai6 ain 2 ain 8 其脚标适合1 i1 i2 in in 1 i n2 1 比较ai1 ai2 两个不同的实数比较 必然有大小 作为递减数列 当ai1 ai2时 必然有数列 比数列 多一项 当ai1 ai2时 必然有数列 比数列 多一项 这与Ni1 Ni2 Nin 1是矛盾的 所以对于ai1 ai2的情况 必然有ai1 a i2成立 以此类推 n 1个长度相等的递减数列必然存在一个长度为 n 1的递增数列 对于ai1 ai2的情况也是如此 如果设原数列中没 有长度为n 1的递增子数列 同理可证必然存在一个长度为n 1的递 减子数列 4 一个国际社团的成员来自6个国家 共有1978人 用1 2 19 78编号 证明 该社团至少有一个成员的编号与他的同胞的编号之 和相等或是其一个同胞的编号的两倍 证明 该题目与下面的叙述是等价的 即把1 2 1978按任意方 式分成6组 则必有一组具备这样的性质 其中至少有一个数或是等 于同一组中其它两数的和 或是等于另一数的两倍 题题目目改改写写是是简简 化化明明确确题题目目的的一一种种方方法法 反证法 设任何一组数都不具备这样的性质 那么应该具备下列性 质 同同一一组组中中任任何何两两个个数数之之差差必必不不在在这这个个组组中中 若a b和b a这三个数在同一组中 则有a b a b 就具备欲证的性质了 由1978 6 329 根据定理1可知 必然存在一个数组A 其中至少 含有330个数 对于这330个数 记最大的为mA mA减去其它329个数 所得的差是既为正整数又小于1978的329个数 根据性质 可知 这329个数一定不在数组A中 必然在其它的5个 数组中 由329 5 65 根据定理1 必然存在一个数组B 其中至少含有上 面329个数中的66个数 对于这66个数 记最大的为mB mB减去其它65个数 所得的差是既为正整数又小于1978的65个数 根据性质 可知 这65个数一定不在