小学六年级数学竞赛讲座 第7讲 小学定理的证明.pdf

第七讲第七讲 小学定理的证明小学定理的证明 模块一 代数 例 1 试用不同的方法证明 等差数列求和 S1 1 2 n aan 等比数列求和 S2 1 1 1 n aq q 完全平方数求和 S3 1 21 6 n nn 证明 1 在等差数列 a1 a2 a3 an中 a1 an a2 an 1 ak an k S1 a1 a2 a3 an S1 an an 1 an 2 a1 所以 2S1 a1 an a2 an 1 an a1 n a1 an 所以 S1 1 2 n aan 2 在等比数列 a1 a2 a3 an中 a1q a2 a2q a3 an 1 q an 且 an a1 q n 1 S2 a1 a2 a3 an q S2 a1 q a2 q a3 q an 1 q an q 式 式得 q 1 S2 an q a1 a1 qn 1 所以 S2 1 1 1 n aq q 3 用和的立方公式证明 n 1 3 n3 3n2 3n 1 于是 23 13 3 12 3 1 1 33 23 3 22 3 2 1 43 33 3 32 3 3 1 n 1 3 n3 3n2 3n 1 将这 n 个等式两边相加得 23 33 43 n3 n 1 3 13 23 33 43 n3 3 12 22 32 n2 3 1 2 3 n n 所以 n 1 3 1 3 12 22 32 n2 3 1 2 n n n 整理得 3 12 22 32 n2 n3 3n2 3n 3 1 2 n n n n n 1 n 2 3 1 2 n n 1 21 2 n nn 所以 12 22 32 n2 1 21 6 n nn 例 2 证明当下式各个变量都是正数时 不等式成立 22222 12121 12 2 aabbaba b 证明 当 a b 都是正数时 a b 2ab 所以 2222 1212 aabb 2222 1212 aabb 22222222 11122122 a ba ba ba b 2222 111 22 122 2a bab a ba b 2 1 12 2 aba b 模块二 数论 例 3 若 a b 的最大公约数是 d 则存在整数 m n 使得 ma nb d 证明 不妨设 a b a b d 用辗转相除法 a r1b t1 0 t1 b d a d b 得到 d t1 若 t1 0 则 b d a r1b 取 m 0 n 1 所以 ma nb d 若 t1 0 则 b r2t1 t2 0 t20 x n 1 则 n 也不能整除 x a b 取整数集 A 为所有小于 p 的集 A 构成 p 的完全剩余系 即 A 中不存在两个数同余 p B 是 A 中所有的元素乘以 a 组成的集合 因为 A 中的任何两个元素之差都不能被 p 整除 所以 B 中的任何两个元素之差也不能被 p 整除 因此 即 在这里 W 1 2 3 p 1 且 W p 1 因此将整个公式除以 W 即得到 2 证明 首先证明下面这个命题 对于集合 Zn x1 x2 x n 其中 xi i 1 2 n 是不大于 n 且与 n 互质的正整数 即 n 的一个 化简剩余系 或称为简系 或称缩系 考虑集合 S a x1 mod n a x2 mod n a n mod n 则 S Zn 1 由于 a n 互质 xi也与 n 互质 则 a xi也一定与 n 互质 因此对于任意 xi a xi mod n 必然是 Zn的 一个元素 2 对于 Zn中的两个元素 xi和 xj 如果 xi xj 则 a xi mod n a xj mod n 这个由 a n 互质和消去律 可以得出 所以很显然 S Zn 既然这样 那么 a x1 mod n a x2 mod n a x n mod n x1 x2 x n mod n 考虑上面等式的左边和右边 左边等于 a x1 x2 x n mod n 右边等于 x1 x2 x n mod n 而 x1 x2 x n mod n 和 n 互质 根据消去律 可以从等式两边约去 就得到 a n 1 mod n 模块三 几何 例 5 给定顶点坐标均是整点 或正方形格点 的简单多边形 证明其面积 A 和内部格点数目 i 边上格点 数目 b 的关系满足 A i 2 b 1 匹克公式 证明 因为所有简单多边形都可切割为一个三角形和另一个简单多边形 考虑一个简单多边形 P 及跟 P 有一条共同边的三角形 T 若 P 符合皮克公式 则只要证明 P 加上 T 的 PT 亦符合皮克公式 与及三角形符合皮克公式 就可根 据数学归纳法 对于所有简单多边形皮克公式都是成立的 多边形多边形 设 P 和 T 的共同边上有 c 个格点 P 的面积 iP 1 2 bP 1 T 的面积 iT 1 2 bT 1 PT 的面积 iT iP c 2 1 2 bT c 2 bP c 2 1 iPT 1 2 bPT 1 第一个括号是因为合并时要加上共用边的 c 个后还要减去这个共用边的两个顶点 第二个是因为合 并后共用边的 c 个不见了 但是减去后会多减两个端点 所以要加上 三角形三角形 证明分三部分 证明以下的图形符合皮克定理 所有平行于轴线的矩形 以上述矩形的两条邻边和对角线组成的直角三角形 所有三角形 因为它们都可内接于矩形内 将矩形分割成原三角形和至多 3 个第二点提到的直角三 角形 矩形矩形 设矩形 R 长边短边各有 m n 个格点 AR m 1 n 1 iR m 2 n 2 bR 2 m n 4 iR 1 2 bR 1 m 2 n 2 m n 2 1 mn m n 1 m 1 n 1 直角三角形直角三角形 易见两条邻边和对角线组成的两个直角三角形全等 且 i b 相等 设其斜边上有 c 个格点 b m n c 3 i 1 2 m 2 n 2 c 2 i 1 2 b 1 m 2 n 2 c 2 2 m n c 3 2 1 1 2 m 2 n 2 1 2 m n 3 1 2 m 1 n 1 例 6 如图为三角形 ABC 求证 1 点 D 在 BC 内 E 在 AC 内 F 在 AB 内 AD BE CF 共点的充分必要条件是 1 AFBDCE FBDCEA 2 点 D 在 BC 外 E 在 AC 内 F 在 AB 内 D E F 共线的充分必要条件是 1 AFBDCE FBDCEA 证明 塞瓦定理 1 AOC BOC SAF FBS AOB AOC SBC DCS BOC AOB SCE EAS 所以1 AOCAOBBOC BOCAOCAOB SSSAFBDCE FBDCEASSS 2 梅涅劳斯定理 过点 A 作 AG DF 交 BC 的延长线于点 G 则 模块四 组合 例 7 考虑一个有 n 个元素的排列 若一个排列中所有的元素都不在自己原来的位置上 那么这样的排列就 称为原排列的一个错排 则错排 Dn一共有多少种 证明 当 n 个编号元素放在 n 个编号位置 元素编号与位置编号各不对应的方法数用 D n 表示 那么 D n 1 就表示 n 1 个编号元素放在 n 1 个编号位置 各不对应的方法数 其它类推 第一步 把第 n 个元素放在一个位置 比如位置 k 一共有 n 1 种方法 第二步 放编号为 k 的元素 这时有两种情况 1 把它放到位置 n 那么 对于剩下的 n 1 个元素 由于第 k 个元素放到了位置 n 剩下 n 2 个元素 就有 D n 2 种方法 第 k 个元素不把它放到位置 n 这时 对于这 n 1 个元素 有 D n 1 种方法 综上得到 D n n 1 D n 2 D n 1 特殊地 D 1 0 D 2 1 下面通过这个递推关系推导 通项公式 为方便起见 设 D k k N k k 1 2 n 则 N 1 0 N 2 1 2 n 3 时 n N n n 1 n 1 N n 1 n 1 N n 2 即 nN n n 1 N n 1 N n 2 于是有 N n N n 1 N n 1 N n 2 n 1111 2 1 123 NN nnn 1 n n 因此 N n 1 N n 2 1 1 1 n n N 2 N 1 2 1 2 相加 可得 N n 21 1 1 1 2 1 nn nn 因此 D n n 21 1 1 1 2 1 nn nn 此即 错排公式错排公式 用容斥原理证明错排公式 正整数 1 2 3 n 的全排列有 n 种 其中第 k 位是 k 的排列有 n 1 种 当 k 分别取 1 2 3 n 时 共有 n n 1 种排列是至少放对了一个的 由于所求的是错排的种数 所以应当减去这些排列 但是此时把同时有两个数不错排的排列多排除了一次 应补上 在补上时 把同时有三个数不错排的排列多补上了一次 应排除 继续这一过程 得到错排的排列种数为 G F E D CB A D n n n 1 n 2 n 3 1 n n n 即 D n n 21 1 1 1 2 1 nn nn 例 8 1 一个图可以被一笔画的充要条件是它是连通的且奇数点个数不多于 2 奇点定义为有奇数条边与 之相连 偶点类似 2 一个连通图可以被一笔画 且这个一笔画的起点和终点重合 则称这个一笔画的线路叫作欧拉环 一 个图存在欧拉环的充要条件是图中每个点都是偶数点 3 如果连通图有 2k 个奇顶点 那么它可以用 k 笔画成 并且至少要用 k 笔画成 证明 1 必要性 如果一个图能一笔画成 那么对每一个顶点 要么路径中 进入 这个点的边数等于 离 开 这个点的边数 这时点的度为偶数 要么两者相差一 这时这个点必然是起点或终点之一 注意到有起 点就必然有终点 因此奇数点的数目要么是 0 要么是 1 要么是 2 即奇数点的个数不多于 2 充分性 如果图中没有奇顶点 那么随便选一个点出发 就可以用一笔画画出 如果恰好有 1 个奇数 点 那就从这个奇数点开始 也可以画出 如果有两个奇数点 就以其中一个奇数点开始 最后以另一个奇 数点结束即可 2 必要性 如果一个连通图能一笔画成 且起点与终点重合 那么由 1 知道 图中的奇数点可能有 0 个 1 个 或 2 个 而如果有 1 个奇数点 那么把这个点当 做起点 一笔画玩之后 终点不会是这个点 所以不能只有 1 个奇数点 同样如果有 2 个奇数点 那么这两 个不同的点一个是起点 另一个是终点 这也是不对的 所以欧拉环一定是每个点都是偶数点 3 每一笔 一笔画 最多用到 2 个奇数点 现在有 2k 个奇数点 所以最少需要用 2k 笔才能把所有的奇 数点都连上 一个连通图有 2k 个奇数点 那么我们可以把这 2k 的点分成 k 组 每两个点为一组 每组中这两个点 一个作为起点 另一个作为终点 形成 k 个一笔画 最后合为用 k 笔画成的连通图 随随 堂堂 练练 习习 1 证明 13 23 n3 2 1 2 n n 证明 n 1 4 n4 4n3 6n2 4n 1 所以 n4 n 1 4 4n3 6n2 4n 1 14 4 13 6 12 4 1 1 24 14 4 23 6 22 4 2 1 34 24 4 33 6 32 4 3 1 44 34 4 43 6 42 4 4 1 n4 n 1 4 4n3 6n2 4n 1 将这 n 个式子相加且两端消去相同的项得 n4 4 13 23 33 n3 6 12 22 32 n2 4 1 2 3 n n 所以 4 13 23 33 n3 n4 6 12 22 32 n2 4 1 2 3 n n n4 6 1 21 6 n nn 4 1 2 n n n 32 231 22 1 n nnnn 22 1 n n 所以 13 23 n3 2 1 2 n n 证明 2 n 1 4 n4 4n3 6n2 4n 1 所以 24 14 4 13 6 12 4 1 1 34 24 4 23 6 22 4 2 1 44 34 4 33 6 32 4 3 1 n 1 4 n4 4n3 6n2 4n 1 将这 n 个式子相加且两端消去相同的项得 n 1 4 14 4 13 23 33 n3 6 12 22 32 n2 4 1 2 3 n n 所以 4 13 23 33 n3 n 1 4 6 12 22 32 n2 4 1 2 3 n n 1 n 1 4 6 1 21 6 n nn 4 1 2 n n n 1 n 1 4 n n 1 2n 1 2n n 1 n 1 n 1 n 1 3 n 2n 1 2n 1 n 1 n3 3n2 3n 1 2n2 3n 1 n 1 n3 n2 n2 n 1 2 所以 13 23 n3 2 1 2 n n 2 1 小明从家到学校走了两段路 第一段时间是 t1 速度是 v1 第二段时间是 t2 速度是 v2 则这一路 平均速度是多少 2 将两袋盐分别放到两杯质量是 n1 n2的水中 浓度分别是 m1 m2 则将这两杯水混合后 浓度是多少 解 1 第一段路长是 t1 v1 第二段路长是 t2 v2 所以总路程是 t1v1 t2v2 总时间是 t1 t2 所以平均速度为 1 122 12 t vt v tt 2 在第一杯溶液中水的质量是 n1 浓度是 m1 所以溶液的质量是 1 1 1 n m 盐的质量是 1 1 1 1 n m m 在第二杯溶液中水的质量是 n2 浓度是 m2 所以溶液的质量是 2 2 1 n m 盐的质量是 2 2 2 1 n m m 盐的总量是 1 122 12 11 m nm n mm 而溶液的总量是 1 1 1 n m 2 2 1 n m 所以混合后的浓度是 1 122 12 12 12 11 11 m nm n mm nn mm 1 1221212 121221 mnm nmm nn nnn mn m 3 对于同余方程组 x a1 mod n1 x a2 mod n2 x am mod nm 只要对 i j 都有 ni nj 1 则这 个方程组有解 证明 先研究两个同余方程所成的组 x a1 mod n1 x a2 mod n2 由于 n1 n2 1 所以存在两个整数 p q 使得 p n1 q n2 1 将此式两边同乘以 a1 有 a1 p n1 a1 q n2 a1 则 a1 q n2 a1 mod n1 将此式两边同乘以 a2 有 a2 p n1 a2 q n2 a2 则 a2 p n1 a2 mod n2 于是 a2 p n1 a1 q n2 a1 mod n1 且 a2 p n1 a1 q n2 a2 mod n2 也就是这个方程组有解 x a2 p n1 a1 q n2 将这个解减去 n1n2的若干倍 就可以得到一个最小解 然后将 n1n2看做一个整体 再与 n3重复上面的做法 由于 n1n2与 n3互质 于是一定也可以求出一个满足条件的最小解 经过 m 1 次运算 得到原同余方程组的解 4 对于任意正整数 a am的末尾至多 4 位一循环 证明 a 的末位数字 a2的末位数字 a3的末位数字 a4的末位数字 a5的末位数字 0 0 0 0 0 1 1 1 1 1 2 4 8 6 2 3 9 7 1 3 4 6 4 6 4 5 5 5 5 5 6 6 6 6 6 7 9 3 1 7 8 4 2 6 8 9 1 9 1 9 所以对于任意正整数 a am的末尾至多 4 位一循环 5 直角三角形斜边长度的平方等于两直角边长度平方和 1 赵爽弦图证法 以直角三角形的斜边 c 为边作一个正方形 以两条直角边 a b 作一个外弦 图 则中间的正方形的边长为 a b 于是 c2 4 1 2 ab b a 2 2ab b2 2ab b2 a2 b2 2 用拼图法证明 画两个相同的正方形 它们的边长都是 a b 左边的正方形由四个直角三角形和一个正方形组成 面积 c2 4 1 2 ab 右边的正方形是由两个正方形和两个长方形组成 面积 a2 b2 2ab 由 c2 4 1 2 ab a2 b2 2ab 得到 c2 a2 b2 6 如图 AM 是 BAC 的角平分线 证明 ABBM ACCM 证明 从 M 点分别向 AB AC 做垂线