数学竞赛中的数论问题(8)

个男孩的有a组，顺序相邻的3人中恰有一个女孩的有b组，求证3a?b．

证明 现将小孩记作ai(i?1,2,…,n)，且数字化

?1,　ai表示男孩时ai??

?1, a表示女孩时i?则“3人组”数值化为

Ai?ai?ai?1?ai?2?3,　　 ai,ai?1,ai?2均为男孩???3,　　ai,ai?1,ai?2均为女孩 ???1,　　 ai,ai?1,ai?2恰有一个女孩??1,　　a,a,a恰有一个男孩ii?1i?2?其中an?j?aj．

又设取值为3的Ai有p个，取值为?3的Ai有q个，依题意，取值为1的Ai有b个，取值为?1的Ai有a个，得

a1?a2?…?an)?a(1?a??)a(?2a?a?4…)?an?(a?a1 3(2a33 ?3p?(?3)q?(?1)a?b?3(p?q)?(b?a)， 可见3a?b．

例25 （1956，中国北京）证明n?除时余2．

分析 只需说明

3)321n?n?1对任何正整数n都是整数，并且用322n?3n?1?321n?n?为整数，但不便说明“用3除时余2”，应说明222n?n?1??2n?1?31n3?n2?n?是3的倍数．作变形

222 n?32n?2n?2??2n?1?321n?n?1??1,?3,8??1 ， 228命题可证．

证明 已知即

n?n?1??2n?1?31n3?n2?n?1??1， ①

222因为相邻2个整数n,?n?1?必有偶数，所以n?3321n?n?1为整数．又①可变为 2236

2n?2n?2??2n?1?31n3?n2?n?1??1，

228因为相邻3个整数2n,?2n?2?,?2n?1?必有3的倍数，故2n?2n?2??2n?1?能被3整除；又?3,8??1，所以

2n?2n?2??2n?1?8能被3整除；得n3?321n?n?1用3除时22余2．

五、同余

根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题．

例26 正方体的顶点标上?1或?1，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14个数之和不能为0．

证明 记14个数的和为S，易知，这14个数不是?1就是?1，若八个顶点都标上?1，则S?14，命题成立．

对于顶点有?1的情况，我们改变?1为?1，则和S中有4的数a,b,c,d改变了符号，用S表示改变后的和，由

a?b?c?d?0?mod2?，

知 S?S?2a?b?c?d?0?mod4?，

//这表明，改变一个?1，和S关于模4的余数不变，重复进行，直到把所有的?1都改变为?1，则

S?S/?1?1???1?14?2?mod4?，

所以，S?0．

例27 设多项式f?x??a0x?a1xnn?1???an?1x?an的系数都是整数，并且有一个

奇数?及一个偶数?使得f???及f???都是奇数，求证方程f?x??0没有整数根．

证明 由已知有

f????1?mod2??a0?a1?a2???an?1?mod2?， ①

f????1?mod2??an?1?mod2?， ②

若方程f?x??0存在整数根x0，即f?x0??0． 当x0为奇数时，有

f?x0??0?mod2??a0?a1?a2???an?0?mod2?，

37

与①矛盾．

有x0为偶数时，有

f?x0??0?mod2??an?0?mod2?，

与②矛盾．

所以方程f?x??0没有整数根．

六、不定方程

未知数的个数多于方程个数的整系数代数方程，称为不定方程．求不定方程的整数解，叫做解不定方程． 解不定方程通常要解决3个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解．

例28 解方程7x?19y?213． 解法1 由?7,19??1知方程有整数解． 观察特解，列表

y 1 2 x 19725 3 ? 7

?x0?25,?x?25?19t,得一个特解?从而通解为?

y?2,y?2?7t.??0方法总结：第1步，验证?a,b?c，经常是?a,b??1． 第2步，求特解（观察、列举、辗转相除等）．

第3步，代入公式．

解法2 由?7,19??1知方程有整数解． 用辗转相除法求特解，再得通解．先求 7x?19y?1 的一个解，由

19?2?7?5 7?1?5?2

5?2?2?1逆过来有

1?5?2?2?5??7?5??2?5?3?7?2 ??19?2?7??3?7?2

?19?3?7???8?

38

同乘以213，有

7??8?213??19?3?213??213， 得 ??x??1704?19t,

y?639?7t.?解法3 由?7,19??1知方程有整数解． 用柯西方法求特解，将方程变为 x?令

213?19y3?2y， ?30?3y?773?2y?t1为整数，有 77t?3t?1 y?1， ?3t1?1?122t?1令1?t2为整数，有

2 t1?2t2?1

代入得y?2?7t2,x?25?19t2．

方法总结：第1步，将系数较小的那个未知数用另一个未知数来表示

第2步，将表达式形式分离为整数部分与分数部分（实际上也是整数）设分数部分为t1，又得一个不定方程．

第3步，重复上述步骤，设逐次的分数部分为t2,t3,?,tn，那么方程的系数越来越小；对?a,b??1，经过有限次操作，最后方程的两个未知数中必有一个系数为1，从而得到

tn?1?dtn?e，（d,e为整数）

第4步，将上式按顺序倒代上去，逐步求出tn?2,?,t2,t1,x,y，即得不定方程整数解得通解

解法4 用同余法，由7x?19y?213有 19y?213?3?38?mod7? ， 但?7,19??1，有

y?2?mod7?，

得 y?2?7t，

39

进而 x?213?19y213?19?2?7t???25?19t．

77方法总结：ax?by?c?ax?c?modb?或by?c?moda?． 例29 求方程x?2xy?2009的整数解． 解 由2009的分解式，有 x232?x?2y??12?2009?72?41，

?x2?1,?x?1,?x??1,??有 ? ?y?1004,y?1005,??x?2y?2009,??x2?72,?x?7,?x??7,? ????x?2y?41,?y?17,?y?24.例30 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，?直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为 ．（1988，高中联赛）

解法1 设甲、乙两队的队员按出场顺序分别为A1,A2,A3,A4,A5,A6,A和

B1,B2,B3,B4,B5,B6,B7．如果甲方获胜，设Ai获胜的场数是xi，则0?xi?7,1?i?7而

且

x1?x2???x7?7 ， ①

容易证明以下两点：在甲方获胜时

（i）不同的比赛过程对应着方程①的不同非负整数解；

（ii）方程①的不同非负整数解对应着不同的比赛过程，例如，解（2，0，0，1，3，1，0）对应的比赛过程为：A1胜B1和B2；B3胜A1、和A3；A4胜B3后负于B4；A5胜B4、B5和B6但负于B7；最后A6胜B7结束比赛．下面求方程①的非负整数解个数，设yi?xi?1，问题等价于方程

y1?y2?y3?y4?y5?y6?y7?14，

正整数解的个数，将上式写成

1?1?1?1?1?1?1?1?1?1?1?1?1?1?14，

从13个加号取6个的方法数C13种．得甲方获胜的不同的比赛过程有C13种．

同理，乙方获胜的不同的比赛过程也有C13种，合计2C13?3432种比赛过程 解法2 设甲、乙两队的队员按出场顺序分别为A1,A2,A3,A4,A5,A6,A和

40

7666

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学竞赛中的数论问题(8)在线全文阅读。