剩余类造抽屉解证一类存在性竞赛题
- 资源简介:
约2400字。
用剩余类造“抽屉”解证一类存在性竞赛题
任意整数除以 ( 是大于 的正整数)所得余数只有 种情形,即余数为 ,把被 除所得余数相同者归为一类,称为以 为模的一个剩余类.如:整数按除以 余 还是 ,分为奇数和偶数.又如,整数除以 ,余数只能是 这 种情况,我们可把所有整数按除以 后的余数分 类,即 型数, 型数, 型数( 是整数).在数论中有一类存在性问题常可借助某正整数的剩余类构造“抽屉”给予解决,本文略举数例作剖析,旨在探索题型规律,总结解题方法.
1 直接以题中的已知数为模,获得作为“抽屉”的剩余类
例1从 到 的 个整数中,最多可以取出多少个数,使得这些数中没有两个数的差是 的倍数?
解 任何一个整数除以 的余数只能是: ,从这 类中各取一个数,这些数中没有两个数的差是 的倍数.故从 到 的 个整数中最多可以取出 个数,使得其中没有两个数的差是 的倍数.
例2求证:在任何 个整数中,总可以找到这样的 个数,它们的和是 的倍数.
分析 将模 的 个剩余类看作 个“抽屉”,分别放置形如 ( 是整数)的数.
证明 将所给的 个整数按照除以 的余数分为三类.
(1)如果每一类都不是空集,,那么在每类中分别取一个数,它们被 除的余数分别为 ,显然这三个数的和是 的倍数;
(2)如果这三类中有空集,那么在两个不空的类中必有某一类含有三个数,即必有三个数被 除的余数相同,这三个数的和是 的倍数.
因此,无论 个整数在模 的 个剩余类中如何分布,总能找到其和为 的倍数的三个数.
例3 任给 个不同的整数,证明其中必有两个数,其和或差是 的倍数.
分析 首先考虑什么样的两个整数的和或差可被 整除.设两个整数 ,若 ,则 ;若 ,而 ,则 ,只有这两种情况.但是如果按整数除以 的余数造抽屉,就有十个抽屉,对于已知条件中给定的 个数无法应用抽屉原理,所以要考虑如何造 个抽屉.根据上面考虑的两个整数被 除的两种情况,可把余数之和等于 的并成 类,这样分为:余数为 的数,余数为 或 的数,余数为 或 的数,余数为 或 的数,余数为 或 的数,余数为 的数,共 类,恰好构成 个抽屉.
证明 按照除以 的余数构造上述 个抽屉,这样任给的7个整数按照除以 的余数 ,放入6个抽屉中,必有1个抽屉中至少有两个数.这两数的和或差必是 的倍数.
资源评论
共有 0位用户发表了评论 查看完整内容我要评价此资源