数学竞赛教案讲义(17)——整数问题

1、第十七章整数问题第十七章整数问题一、常用定义定理1整除：设 a,b Z,a 0，如果存在 q Z 使得 b=aq，那么称 b 可被 a 整除，记作 a|b ，且称 b 是 a 的倍数 ,a 是 b 的约数。 b 不能被 a 整除，记作 a b.2带余数除法：设 a,b 是两个给定的整数，a 0，那么，一定存在唯一一对整数q 与 r ，满足 b=aq+r,0 r|a|，当 r=0 时 a|b 。 3辗转相除法： 设 u ,u是给定的两个整数，u 0，011uu,由2可得下面k+1 个等式： u =q u +u ,0u2|u| ；1000121u1=q1 u2 +u3,0u 3u2；u =q u

2、+u ,0u4u ；22343uk-2 =qk-2 u1+uk-1 +uk,0u kuk-1 ；uk-1 =qk-1 uk+1,0u k+11 且 n 为整数，则np1a1 p2a2pkak ，其中 pj (j=1,2,k) 是质数（或称素数），且在不计次序的意义下，表示是唯一的。6同余：设 m 0, 若 m|(a-b) ，即 a-b=km，则称 a 与 b 模同 m同余，记为 a b(modm)，也称 b 是 a 对模 m的剩余。7完全剩余系： 一组数 y1,y 2,y s 满足：对任意整数a 有且仅有一个yj 是 a 对模 m的剩余，即 a yj (modm)，则 y1,y 2, ,y s

3、 称为模 m的完全剩余系。8 Fermat 小定理：若 p 为素数， pa,(a,p)=1 ，则 ap-1 1(modp) ，且对任意整数a, 有 apa(modp).9若 (a,m)=1 ，则 a ( m) 1(modm),(m) 称欧拉函数。p1a1 p2a2pkak ，则 (m)= mk110（欧拉函数值的计算公式）若m(1).i 1pi11（孙子定理）设m1,m2, ,mk 是 k 个两两互质的正整数，则同余组：x b1(modm1),x b2(modm2), ,x bk(modmk) 有唯一解，x 1 1 2 2k k(modM)，M 1 Mb + M 2 Mb+ + M kMb其中

4、 M=m1m2mk； M i = M ，i=1,2,k ； M i M i 1(modmi ),i=1,2,k.mi二、方法与例题1奇偶分析法。例 1有 n 个整数，它们的和为0，乘积为 n，（ n1），求证： 4|n 。2不等分析法。1第十七章整数问题例 2试求所有的正整数n，使方程 x3+y3+z3=nx2y2z2 有正整数解。3无穷递降法。例 3确定并证明方程a2+b2+c2=a2b2 的所有整数解。4特殊模法。例 4证明：存在无穷多个正整数，它们不能表示成少于10 个奇数的平方和。5最小数原理。例 5证明：方程x4+y4 =z2 没有正整数解。6整除的应用。3例 6求出所有的有序正整数

5、数对(m,n) ，使得n1 是整数。mn17进位制的作用2第十七章整数问题例 7 能否选择 1983 个不同的正整数都不大于 105，且其中没有 3 个正整数是等差数列中的连续项？证明你的结论。三、习题精选1试求所有正整数对(a,b)，使得 (ab-a 2+b+1)|(ab+1).2设 a,b,c N+，且 a2 +b2-abc 是不超过c+1 的一个正整数，求证：a2+b2-abc 是一个完全平方数。3确定所有的正整数数对(x,y)，使得 x y，且 x2+1 是 y 的倍数， y2+1 是 x 的倍数。4求所有的正整数n，使得存在正整数m,(2 n-1)|(m 2+9).5求证：存在一个具

6、有如下性质的正整数的集合A，对于任何由无限多个素数组成的集合，存在 k 2 及正整数m A 和 nA，使得 m和 n 均为 S 中 k 个不同元素的乘积。6求最小的正整数n( 4) ，满足从任意n 个不同的整数中能选出四个不同的数a,b,c,d使20|(a+b-c-d).7. 对于正整数a,n, 定义 Fn(a)=q+r ，其中 q,r为非负整数， a=qn+r 且 0 r n，求最大正整数A ， 使 得 存 在 正 整 数n1,n 2,n 6 ， 对 任 意 正 整 数a A ， 都 有Fn6( Fn( Fn4(Fn(Fn2( Fn( a) ) =1，并证明你的结论。5318设 x 是一个

7、n 位数，问：是否总存在非负整数y 9 和 z 使得 10n+1z+10x+y 是一个完全平方数？证明你的结论。9设 a,b,c,d N+, 且 abcd,ac+bd=(b+d+a-c)(b+d-a+c)。证明： ab+cd 不是素数。w.w.w.k.s.5.u.c.o.m第十八章组合一、方法与例题1抽屉原理。例 1 设整数 n 4,a 1,a 2, ,a n 是区间 (0,2n) 内 n 个不同的整数， 证明：存在集合 a 1,a 2, ,a n 的一个子集，它的所有元素之和能被2n 整除。 w.w.w.k.s.5.u.c.o.m 证明（ 1 ） 若 na,a, ,a ,则 n个 不 同 的

8、 数 属于 n-1个 集 合 1,2n-1 ，12n2,2n-2,n-1,n+1。由抽屉原理知其中必存在两个数ai ,a j (i j)属于同一集合，从而a +a =2n 被 2n 整除；ij（2）若 n a 1,a 2, ,a n ，不妨设 an =n，从 a1,a 2, ,a n-1 (n-1 3)中任意取3 个数 ai, aj, ak(ai,aj0) 不被 n整除，考虑 n 个数 a ,a,a+a ,a +a +a , ,a +a + +a。121212312n-1）若这 n 个数中有一个被n 整除，设此数等于 kn，若 k 为偶数， 则结论成立； 若 k 为奇数，则加上 an=n 知结

9、论成立。）若这 n 个数中没有一个被n 整除，则它们除以 n 的余数只能取 1,2,n-1 这 n-1 个值，3第十七章整数问题由抽屉原理知其中必有两个数除以 n 的余数相同， 它们之差被 n 整除，而 a2-a 1 不被 n 整除，故这个差必为 ai, aj , ak-1 中若干个数之和，同）可知结论成立。2 极端原理。例 2 在 nn 的方格表的每个小方格内写有一个非负整数，并且在某一行和某一列的交叉点处如果写有 0，那么该行与该列所填的所有数之和不小于n。证明：表中所有数之和不小于 1n2 。2证明 计算各行的和、各列的和，这2n 个和中必有最小的，不妨设第m 行的和最小，记和为 k，则

10、该行中至少有n-k 个 0，这 n-k 个 0 所在的各列的和都不小于n-k，从而这 n-k 列的数的总和不小于(n-k)2，其余各列的数的总和不小于k2，从而表中所有数的总和不小于2 2 (n kk) 21 2.(n-k) +k n223. 不变量原理。俗话说，变化的是现象，不变的是本质，某一事情反复地进行，寻找不变量是一种策略。例 3设正整数n 是奇数，在黑板上写下数1，2， ， 2n，然后取其中任意两个数a,b, 擦去这两个数，并写上|a-b|。证明：最后留下的是一个奇数。证明 设 S 是黑板上所有数的和，开始时和数是S=1+2+2n=n(2n+1) ，这是一个奇数， 因为|a-b| 与

11、 a+b 有相同的奇偶性，故整个变化过程中S 的奇偶性不变，故最后结果为奇数。例 4数 a1, a2, ,an 中每一个是 1 或 -1，并且有 S=a1a2a3a4+ a2a3 a4 a5+ +ana1a2a3 =0. 证明：4|n.证明 如果把 a1, a2, ,an 中任意一个 ai 换成 -ai，因为有 4 个循环相邻的项都改变符号，S模 4 并不改变，开始时 S=0，即 S 0，即 S 0(mod4) 。经有限次变号可将每个 ai都变成1，而始终有 S 0(mod4) ，从而有 n 0(mod4) ，所以 4|n 。4构造法。例 5是否存在一个无穷正整数数列a1,a2a3 ，使得对任

12、意整数 A，数列 anA n 1 中仅有有限个素数。3， 证明 存在。取 a =(n!) 即可。当 A=0 时， a 中没有素数；当 |A| 2 时，若 n |A|nn则 an+A 均为 |A| 的倍数且大于 |A|，不可能为素数；当A= 1 时， an 1=(n! 1) ?(n!)2n!+1 ，当 3 时均为合数。从而当A 为整数时， (n!)3+A中只有有限个素数。例 6 一个多面体共有偶数条棱，试证：可以在它的每条棱上标上一个箭头，使得对每个顶点，指向它的箭头数目是偶数。 证明 首先任意给每条棱一个箭头，如果此时对每个顶点，指向它的箭头数均为偶数，则命题成立。若有某个顶点A，指向它的箭头

13、数为奇数，则必存在另一个顶点B，指向它的箭头数也为奇数（因为棱总数为偶数），对于顶点A 与 B，总有一条由棱组成的“路径”连结它们，对该路径上的每条棱，改变它们箭头的方向，于是对于该路径上除A， B 外的每个顶点，指向它的箭头数的奇偶性不变，而对顶点A， B，指向它的箭头数变成了偶数。如果这时仍有顶点，指向它的箭头数为奇数，那么重复上述做法，又可以减少两个这样的顶点，由于多面体顶点数有限，经过有限次调整，总能使和是对每个顶点，指向它的箭头数为偶数。命题成立。5染色法。例 7 能否在 5 5 方格表内找到一条线路，它由某格中心出发，经过每个方格恰好一次，再回到出发点，并且途中不经过任何方格的顶点

14、？ 解 不可能。将方格表黑白相间染色，不妨设黑格为13 个，白格为12 个，如果能实现，4第十七章整数问题因黑白格交替出现，黑白格数目应相等，得出矛盾，故不可能。6凸包的使用。给定平面点集A，能盖住 A 的最小的凸图形，称为A 的凸包。例 8试证：任何不自交的五边形都位于它的某条边的同一侧。 证明 五边形的凸五包是凸五边形、凸四边形或者是三角形， 凸包的顶点中至少有 3 点是原五边形的顶点。 五边形共有5 个顶点， 故 3 个顶点中必有两点是相邻顶点。连结这两点的边即为所求。7赋值方法。例 9由 2 2 的方格纸去掉一个方格余下的图形称为拐形，用这种拐形去覆盖5 7 的方格板，每个拐形恰覆盖3

15、 个方格， 可以重叠但不能超出方格板的边界，问：能否使方格板上每个方格被覆盖的层数都相同？说明理由。 解 将 5 7 方格板的每一个小方格内填写数-2 和 1。如图 18-1 所示，每个拐形覆盖的三个数之和为非负。 因而无论用多少个拐形覆盖多少次，盖住的所有数字之和都是非负的。另一方面，方格板上数字的总和为12 (-2)+23 1=-1 ，当被覆盖 K 层时，盖住的数字之和等于-K ，这表明不存在满足题中要求的覆盖。-21-21-21-21111111-21-21-21-21111111-21-21-21-28图论方法。例 10 生产由六种颜色的纱线织成的双色布，在所生产的双色布中，每种颜色的

16、纱线至少与其他三种颜色的纱线搭配过。证明：可以挑出三种不同的双色布，它们包含所有的颜色。证明 用点 A1， A2， A3 ，A4， A5， A6 表示六种颜色，若两种颜色的线搭配过，则在相应的两点之间连一条边。 由已知， 每个顶点至少连出三条边。 命题等价于由这些边和点构成的图中有三条边两两不相邻 （即无公共顶点） 。因为每个顶点的次数 3，所以可以找到两条边不相邻，设为 A1A2， A3A4。（ 1）若 A5 与 A6 连有一条边，则 A1A2， A3A4， A5A6 对应的三种双色布满足要求。（ 2）若 A5 与 A6 之间没有边相连，不妨设 A5 和 A1 相连， A2 与 A3 相连，

17、若 A4 和 A6 相连，则A1A2， A3 A4， A5A6 对应的双色布满足要求；若A4 与 A6 不相连，则 A6 与 A1 相连， A2 与 A3 相连， A1 A5， A2A6，A3A4 对应的双色布满足要求。综上，命题得证。二、习题精选1药房里有若干种药， 其中一部分药是烈性的。 药剂师用这些药配成 68副药方， 每副药方中恰有 5 种药，其中至少有一种是烈性的， 并且使得任选3 种药恰有一副药方包含它们。 试问：全部药方中是否一定有一副药方至少含有4 种烈性药？（证明或否定）221 个女孩和 21 个男孩参加一次数学竞赛， （ 1）每一个参赛者最多解出6 道题；（ 2）对每一个女

18、孩和每一个男孩至少有一道题被这一对孩子都解出。求证：有一道题至少有 3 个女孩和至少有 3 个男孩都解出。3求证：存在无穷多个正整数n ，使得可将3n 个数 1, 2, , 3n 排成数表a1, a2 anb1, b2bnc1, c2cn5第十七章整数问题满足：（ 1） a1+b1+c1= a2+b2+c2= an+bn+cn=，且为 6 的倍数。（ 2） a1+a2 + +an= b1+b2+ +bn= c1+c2+ +cn =，且为 6 的倍数。4给定正整数n，已知克数都是正整数的k 块砝码和一台天平可以称出质量为1，2， ， n克的所有物品，求k 的最小值 f(n)。5空间中有1989 个点，其中任何3 点都不共线，把它们分成点数各不相同的30 组，在任何 3 个不同的组中各取一点为