1、 这 样 的 整 数 ， 其 中 一 个 可 被 另 一 个 整 除 。证 明 之 前 ， 先 介 绍 一 种 正 整 数 的 表 示 方 法 。 正 整 数 有 奇 数 有 偶 数 ，而 任 何 一 个 偶 数 ， 都 可 以 通 过 提 取 因 数 2， 变 为 奇 数 与 若 干 个 2乘 积的 形 式 ， 例 如 8=1x2x2x2,24=3x2x2x2， 写 成 一 般 形 式 即 奇 数 x2n（其 中 n=1,2,3） ， 而 这 个 奇 数 绝 不 会 超 过 这 个 偶 数 的 一 半 。 下 面来 证 明 例 3。证 明 ： 找 出 鸽 子 ： 1到 200中 任 意 选
2、出 的 101个 整 数 。构 造 鸽 巢 ： 用 奇 数 x2n的 形 式 ， 把 1到 200的 整 数 全 部 列 出 ，1， 1x21， 1x22， 1x273， 3x21， 3x22， 3x265， 5x21， 5x22， 5x2599， 99x21199这 样 ， 就 把 1到 200的 全 部 整 数 列 出 ， 共 100行 。鸽 巢 原 理 ： 101个 整 数 放 到 100行 内 ， 必 然 有 两 个 整 数 在 同 一 行 ， 这两 个 数 表 示 为 p=ax2m， q=ax2n,其 中 ， a为 奇 数 ， 1 a 199， m、 n为正 整 数 ， 不 妨 设
3、n mq/p=(ax2n)/(q=ax2m)= 2n-m。二 、 鸽 巢 原 理 的 加 强 形 式1、 定 理 2： 如 果 要 把 多 于 mxn（ 比 如 mxn+1） 个 物 体 放 进 n个 盒 子 ，那 么 至 少 有 一 个 盒 子 包 含 m+1个 或 m+1个 以 上 的 物 体 。例 4： 空 间 有 六 个 点 ， 其 中 任 何 三 点 都 不 共 线 ， 任 何 四 点 都 不 共 面 ，在 每 两 点 之 间 连 接 直 线 段 后 涂 色 ， 将 每 一 条 这 样 的 线 段 图 成 红 色 或蓝 色 ， 求 证 ： 不 论 如 何 涂 色 ， 一 定 存 在
4、一 个 三 角 形 ， 它 的 三 边 有 相同 的 颜 色 。证 明 ： 找 出 鸽 子 ： 从 一 点 出 发 ， 连 接 的 空 间 直 线 段 有 5条 ， 即 2x2+1条 。 构 造 鸽 巢 ： 红 色 和 蓝 色 。 鸽 巢 原 理 ： 根 据 定 理 2， 则 至 少 有 三 条线 段 的 颜 色 是 相 同 的 。 如 图 ： 三 条 实 线 段 颜 色 相 同 ， 虚 线 连 接 三 条线段 的 端 点 。 三 条 虚 线 段 颜 色 不 同 时 ， 则 与实 现 三 条 实 线 段 构 成 颜 色 三 边 颜 色 相 同的 三 角 形 。 三 条 虚 线 段 颜 色 相
5、同 ， 但 与 三条 实 线 段 颜 色 不 同 时 ， 由 虚 线 段 构 成 的 三角 形 就 已 经 符 合 结 论 了 。2、 定 理 3： 设 ql， q2， q3， ， qn 是 正 整 数 ， 如 果 将 ql+q2+qn-n+1个 物 体 体 放 进 n个 盒 子 内 ， 那 么 或 者 第 一 个 盒 子 至 少 包 含 ql个 物体 ， 或 者 第 二 个 盒 子 至 少 包 含 q2个 物 体 ， ， 或 者 第 n个 盒 子 至 少包 含 qn个 物 体 。证 明 ： ql+q2+qn-n+1=(ql-1)+(q2-1)+(qn-1)+1根 据 鸽 巢 原 理 ， 可
6、得 第 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： 个
7、 果 篮 装 有 苹 杲 、 香 蕉 和 橘 子 。 为 了 保 证 篮 子 中 或 者 至 少 有 8个 苹 果， 或 者 至 少 有 6个 香 蕉 ， 或 者 至 少 有 9个 橘 子 ， 则 放 人 篮 子 中 的 水 果 的 最 小 件 数是 多 少 ？解 ： 根 据 定 理 3可 得 ， 所 需 的 水 果 最 小 件 数 为 8+6+9-3+1=21件 。3、 从 定 理 3得 到 的 一 个 推 论推 论 3： 设 n和 r都 是 正 整 数 。 如 果 把 n(r-1)+1个 物 体 分 配 到 n个 盒 子 中 ， 那 么 至 少 有 一 个 盒 子 含 有 r或 更 多 个
8、物 体 。证 明 ： n(r-1)+1=nr-n+1， 令 定 理 3中 ql=q2=qn=r， 则 结 论 成 立 。4、 由 推 论 3得 到 的 3个 平 均 原 理平 均 原 理 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个 物 体
9、外 ， 其 余盒 子 均 为 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， 则 必 至 少 有 一
10、 个 大 于 或 等 于r。平 均 原 理 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个 。 反 过 来 ，
11、如 果 平 均 数 要 小 于 r+1， 那 个 必 然 一 个 盒 子 中 的 物 体 数 量 要 小 于 或 等 于 r。证 明 ： (ql+q2+qn)/n= n(r+1)-1/n=r+1-1/n (r+1),r N+。平 均 原 理 3： 如 果 n个 非 负 整 数 ， ql， q2， q3， ， qn的 平 均 数至 少 等 于 r， 即 (ql+q2+qn)/n r,那 么 这 n个 数 中 ， 至 少 有 一个 整 数 大 于 等 于 r。证 明 ： 令 平 均 原 理 中 的 r-1=u， 则 结 论 成 立 。例 5： 有 两 个 碟 子 ， 其 中 一 个 比 另 一 个
12、 小 ， 它 们 都 被 分 成 200个 均 等的 扇 形 。 在 大 碟 子 中 ， 任 选 100个 扇 形 并 着 成 红 色 ， 而 其 余 的 100个扇 形 着 成 蓝 色 。 在 小 碟 子 中 ， 每 一 个 扇 形 或 者 着 成 红 色 ， 或 者 着 成蓝 色 ， 所 着 红 色 扇 形 和 蓝 色 扇 形 的 数 目 没 有 限 制 。 然 后 ， 将 小 碟 子放 到 大 碟 子 上 面 使 两 个 碟 子 的 中 心 重 合 。 证 明 ： 能 够 将 两 个 碟 子 的扇 形 对 齐 使 得 小 碟 子 和 大 碟 子 上 相 同 颜 色 重 合 的 扇 形 的 数 目 至 少 是 100个 。证 明 ： 设 小 碟 子 蓝 色 扇 形 的 数 量 为 x， 红 色 扇 形 的 数 量 为 y。 大 碟 子不 动 ， 转 动 小 碟 子 ， 每 转 2 /200角 度 ， 就 有 一 次 对 应 ， 于 是 共 有 200次 对 应 。 大 碟 子 的 红 色 扇 形 有 100个 ， 小 碟 子 的 红 色 扇 形 有 x个 ， 那么 转 动 一 周 ， 小 碟 子 每 个 红 色 扇 形 与 大 碟 子 对 应 100次 ， 所 以 红 色 扇形
个人主页
