數(shù)學(xué)競賽教案講義(17)——整數(shù)問題

1、第十七章整數(shù)問題第十七章整數(shù)問題一、常用定義定理1整除：設(shè) a,b Z,a 0，如果存在 q Z 使得 b=aq，那么稱 b 可被 a 整除，記作 a|b ，且稱 b 是 a 的倍數(shù) ,a 是 b 的約數(shù)。 b 不能被 a 整除，記作 a b.2帶余數(shù)除法：設(shè) a,b 是兩個給定的整數(shù)，a 0，那么，一定存在唯一一對整數(shù)q 與 r ，滿足 b=aq+r,0 r|a|，當(dāng) r=0 時 a|b 。 3輾轉(zhuǎn)相除法： 設(shè) u ,u是給定的兩個整數(shù)，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 為整數(shù)，則np1a1 p2a2pkak ，其中 pj (j=1,2,k) 是質(zhì)數(shù)（或稱素數(shù)），且在不計次序的意義下，表示是唯一的。6同余：設(shè) m 0, 若 m|(a-b) ，即 a-b=km，則稱 a 與 b 模同 m同余，記為 a b(modm)，也稱 b 是 a 對模 m的剩余。7完全剩余系： 一組數(shù) y1,y 2,y s 滿足：對任意整數(shù)a 有且僅有一個yj 是 a 對模 m的剩余，即 a yj (modm)，則 y1,y 2, ,y s

3、 稱為模 m的完全剩余系。8 Fermat 小定理：若 p 為素數(shù)， pa,(a,p)=1 ，則 ap-1 1(modp) ，且對任意整數(shù)a, 有 apa(modp).9若 (a,m)=1 ，則 a ( m) 1(modm),(m) 稱歐拉函數(shù)。p1a1 p2a2pkak ，則 (m)= mk110（歐拉函數(shù)值的計算公式）若m(1).i 1pi11（孫子定理）設(shè)m1,m2, ,mk 是 k 個兩兩互質(zhì)的正整數(shù)，則同余組：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 個整數(shù)，它們的和為0，乘積為 n，（ n1），求證： 4|n 。2不等分析法。1第十七章整數(shù)問題例 2試求所有的正整數(shù)n，使方程 x3+y3+z3=nx2y2z2 有正整數(shù)解。3無窮遞降法。例 3確定并證明方程a2+b2+c2=a2b2 的所有整數(shù)解。4特殊模法。例 4證明：存在無窮多個正整數(shù)，它們不能表示成少于10 個奇數(shù)的平方和。5最小數(shù)原理。例 5證明：方程x4+y4 =z2 沒有正整數(shù)解。6整除的應(yīng)用。3例 6求出所有的有序正整數(shù)

5、數(shù)對(m,n) ，使得n1 是整數(shù)。mn17進(jìn)位制的作用2第十七章整數(shù)問題例 7 能否選擇 1983 個不同的正整數(shù)都不大于 105，且其中沒有 3 個正整數(shù)是等差數(shù)列中的連續(xù)項？證明你的結(jié)論。三、習(xí)題精選1試求所有正整數(shù)對(a,b)，使得 (ab-a 2+b+1)|(ab+1).2設(shè) a,b,c N+，且 a2 +b2-abc 是不超過c+1 的一個正整數(shù)，求證：a2+b2-abc 是一個完全平方數(shù)。3確定所有的正整數(shù)數(shù)對(x,y)，使得 x y，且 x2+1 是 y 的倍數(shù)， y2+1 是 x 的倍數(shù)。4求所有的正整數(shù)n，使得存在正整數(shù)m,(2 n-1)|(m 2+9).5求證：存在一個具

6、有如下性質(zhì)的正整數(shù)的集合A，對于任何由無限多個素數(shù)組成的集合，存在 k 2 及正整數(shù)m A 和 nA，使得 m和 n 均為 S 中 k 個不同元素的乘積。6求最小的正整數(shù)n( 4) ，滿足從任意n 個不同的整數(shù)中能選出四個不同的數(shù)a,b,c,d使20|(a+b-c-d).7. 對于正整數(shù)a,n, 定義 Fn(a)=q+r ，其中 q,r為非負(fù)整數(shù)， a=qn+r 且 0 r n，求最大正整數(shù)A ， 使 得 存 在 正 整 數(shù)n1,n 2,n 6 ， 對 任 意 正 整 數(shù)a A ， 都 有Fn6( Fn( Fn4(Fn(Fn2( Fn( a) ) =1，并證明你的結(jié)論。5318設(shè) x 是一個

7、n 位數(shù)，問：是否總存在非負(fù)整數(shù)y 9 和 z 使得 10n+1z+10x+y 是一個完全平方數(shù)？證明你的結(jié)論。9設(shè) a,b,c,d N+, 且 abcd,ac+bd=(b+d+a-c)(b+d-a+c)。證明： ab+cd 不是素數(shù)。w.w.w.k.s.5.u.c.o.m第十八章組合一、方法與例題1抽屜原理。例 1 設(shè)整數(shù) n 4,a 1,a 2, ,a n 是區(qū)間 (0,2n) 內(nèi) n 個不同的整數(shù)， 證明：存在集合 a 1,a 2, ,a n 的一個子集，它的所有元素之和能被2n 整除。 w.w.w.k.s.5.u.c.o.m 證明（ 1 ） 若 na,a, ,a ,則 n個 不 同 的

8、 數(shù) 屬于 n-1個 集 合 1,2n-1 ，12n2,2n-2,n-1,n+1。由抽屜原理知其中必存在兩個數(shù)ai ,a j (i j)屬于同一集合，從而a +a =2n 被 2n 整除；ij（2）若 n a 1,a 2, ,a n ，不妨設(shè) an =n，從 a1,a 2, ,a n-1 (n-1 3)中任意取3 個數(shù) ai, aj, ak(ai,aj0) 不被 n整除，考慮 n 個數(shù) a ,a,a+a ,a +a +a , ,a +a + +a。121212312n-1）若這 n 個數(shù)中有一個被n 整除，設(shè)此數(shù)等于 kn，若 k 為偶數(shù)， 則結(jié)論成立； 若 k 為奇數(shù)，則加上 an=n 知結(jié)

9、論成立。）若這 n 個數(shù)中沒有一個被n 整除，則它們除以 n 的余數(shù)只能取 1,2,n-1 這 n-1 個值，3第十七章整數(shù)問題由抽屜原理知其中必有兩個數(shù)除以 n 的余數(shù)相同， 它們之差被 n 整除，而 a2-a 1 不被 n 整除，故這個差必為 ai, aj , ak-1 中若干個數(shù)之和，同）可知結(jié)論成立。2 極端原理。例 2 在 nn 的方格表的每個小方格內(nèi)寫有一個非負(fù)整數(shù)，并且在某一行和某一列的交叉點處如果寫有 0，那么該行與該列所填的所有數(shù)之和不小于n。證明：表中所有數(shù)之和不小于 1n2 。2證明 計算各行的和、各列的和，這2n 個和中必有最小的，不妨設(shè)第m 行的和最小，記和為 k，則

10、該行中至少有n-k 個 0，這 n-k 個 0 所在的各列的和都不小于n-k，從而這 n-k 列的數(shù)的總和不小于(n-k)2，其余各列的數(shù)的總和不小于k2，從而表中所有數(shù)的總和不小于2 2 (n kk) 21 2.(n-k) +k n223. 不變量原理。俗話說，變化的是現(xiàn)象，不變的是本質(zhì)，某一事情反復(fù)地進(jìn)行，尋找不變量是一種策略。例 3設(shè)正整數(shù)n 是奇數(shù)，在黑板上寫下數(shù)1，2， ， 2n，然后取其中任意兩個數(shù)a,b, 擦去這兩個數(shù)，并寫上|a-b|。證明：最后留下的是一個奇數(shù)。證明 設(shè) S 是黑板上所有數(shù)的和，開始時和數(shù)是S=1+2+2n=n(2n+1) ，這是一個奇數(shù)， 因為|a-b| 與

11、 a+b 有相同的奇偶性，故整個變化過程中S 的奇偶性不變，故最后結(jié)果為奇數(shù)。例 4數(shù) a1, a2, ,an 中每一個是 1 或 -1，并且有 S=a1a2a3a4+ a2a3 a4 a5+ +ana1a2a3 =0. 證明：4|n.證明 如果把 a1, a2, ,an 中任意一個 ai 換成 -ai，因為有 4 個循環(huán)相鄰的項都改變符號，S模 4 并不改變，開始時 S=0，即 S 0，即 S 0(mod4) 。經(jīng)有限次變號可將每個 ai都變成1，而始終有 S 0(mod4) ，從而有 n 0(mod4) ，所以 4|n 。4構(gòu)造法。例 5是否存在一個無窮正整數(shù)數(shù)列a1,a2a3 ，使得對任

12、意整數(shù) A，數(shù)列 anA n 1 中僅有有限個素數(shù)。3， 證明 存在。取 a =(n!) 即可。當(dāng) A=0 時， a 中沒有素數(shù)；當(dāng) |A| 2 時，若 n |A|nn則 an+A 均為 |A| 的倍數(shù)且大于 |A|，不可能為素數(shù)；當(dāng)A= 1 時， an 1=(n! 1) ?(n!)2n!+1 ，當(dāng) 3 時均為合數(shù)。從而當(dāng)A 為整數(shù)時， (n!)3+A中只有有限個素數(shù)。例 6 一個多面體共有偶數(shù)條棱，試證：可以在它的每條棱上標(biāo)上一個箭頭，使得對每個頂點，指向它的箭頭數(shù)目是偶數(shù)。 證明 首先任意給每條棱一個箭頭，如果此時對每個頂點，指向它的箭頭數(shù)均為偶數(shù)，則命題成立。若有某個頂點A，指向它的箭頭

13、數(shù)為奇數(shù)，則必存在另一個頂點B，指向它的箭頭數(shù)也為奇數(shù)（因為棱總數(shù)為偶數(shù)），對于頂點A 與 B，總有一條由棱組成的“路徑”連結(jié)它們，對該路徑上的每條棱，改變它們箭頭的方向，于是對于該路徑上除A， B 外的每個頂點，指向它的箭頭數(shù)的奇偶性不變，而對頂點A， B，指向它的箭頭數(shù)變成了偶數(shù)。如果這時仍有頂點，指向它的箭頭數(shù)為奇數(shù)，那么重復(fù)上述做法，又可以減少兩個這樣的頂點，由于多面體頂點數(shù)有限，經(jīng)過有限次調(diào)整，總能使和是對每個頂點，指向它的箭頭數(shù)為偶數(shù)。命題成立。5染色法。例 7 能否在 5 5 方格表內(nèi)找到一條線路，它由某格中心出發(fā)，經(jīng)過每個方格恰好一次，再回到出發(fā)點，并且途中不經(jīng)過任何方格的頂點

14、？ 解 不可能。將方格表黑白相間染色，不妨設(shè)黑格為13 個，白格為12 個，如果能實現(xiàn)，4第十七章整數(shù)問題因黑白格交替出現(xiàn)，黑白格數(shù)目應(yīng)相等，得出矛盾，故不可能。6凸包的使用。給定平面點集A，能蓋住 A 的最小的凸圖形，稱為A 的凸包。例 8試證：任何不自交的五邊形都位于它的某條邊的同一側(cè)。 證明 五邊形的凸五包是凸五邊形、凸四邊形或者是三角形， 凸包的頂點中至少有 3 點是原五邊形的頂點。 五邊形共有5 個頂點， 故 3 個頂點中必有兩點是相鄰頂點。連結(jié)這兩點的邊即為所求。7賦值方法。例 9由 2 2 的方格紙去掉一個方格余下的圖形稱為拐形，用這種拐形去覆蓋5 7 的方格板，每個拐形恰覆蓋3

15、 個方格， 可以重疊但不能超出方格板的邊界，問：能否使方格板上每個方格被覆蓋的層數(shù)都相同？說明理由。 解 將 5 7 方格板的每一個小方格內(nèi)填寫數(shù)-2 和 1。如圖 18-1 所示，每個拐形覆蓋的三個數(shù)之和為非負(fù)。 因而無論用多少個拐形覆蓋多少次，蓋住的所有數(shù)字之和都是非負(fù)的。另一方面，方格板上數(shù)字的總和為12 (-2)+23 1=-1 ，當(dāng)被覆蓋 K 層時，蓋住的數(shù)字之和等于-K ，這表明不存在滿足題中要求的覆蓋。-21-21-21-21111111-21-21-21-21111111-21-21-21-28圖論方法。例 10 生產(chǎn)由六種顏色的紗線織成的雙色布，在所生產(chǎn)的雙色布中，每種顏色的

16、紗線至少與其他三種顏色的紗線搭配過。證明：可以挑出三種不同的雙色布，它們包含所有的顏色。證明 用點 A1， A2， A3 ，A4， A5， A6 表示六種顏色，若兩種顏色的線搭配過，則在相應(yīng)的兩點之間連一條邊。 由已知， 每個頂點至少連出三條邊。 命題等價于由這些邊和點構(gòu)成的圖中有三條邊兩兩不相鄰 （即無公共頂點） 。因為每個頂點的次數(shù) 3，所以可以找到兩條邊不相鄰，設(shè)為 A1A2， A3A4。（ 1）若 A5 與 A6 連有一條邊，則 A1A2， A3A4， A5A6 對應(yīng)的三種雙色布滿足要求。（ 2）若 A5 與 A6 之間沒有邊相連，不妨設(shè) A5 和 A1 相連， A2 與 A3 相連，

17、若 A4 和 A6 相連，則A1A2， A3 A4， A5A6 對應(yīng)的雙色布滿足要求；若A4 與 A6 不相連，則 A6 與 A1 相連， A2 與 A3 相連， A1 A5， A2A6，A3A4 對應(yīng)的雙色布滿足要求。綜上，命題得證。二、習(xí)題精選1藥房里有若干種藥， 其中一部分藥是烈性的。 藥劑師用這些藥配成 68副藥方， 每副藥方中恰有 5 種藥，其中至少有一種是烈性的， 并且使得任選3 種藥恰有一副藥方包含它們。 試問：全部藥方中是否一定有一副藥方至少含有4 種烈性藥？（證明或否定）221 個女孩和 21 個男孩參加一次數(shù)學(xué)競賽， （ 1）每一個參賽者最多解出6 道題；（ 2）對每一個女

18、孩和每一個男孩至少有一道題被這一對孩子都解出。求證：有一道題至少有 3 個女孩和至少有 3 個男孩都解出。3求證：存在無窮多個正整數(shù)n ，使得可將3n 個數(shù) 1, 2, , 3n 排成數(shù)表a1, a2 anb1, b2bnc1, c2cn5第十七章整數(shù)問題滿足：（ 1） a1+b1+c1= a2+b2+c2= an+bn+cn=，且為 6 的倍數(shù)。（ 2） a1+a2 + +an= b1+b2+ +bn= c1+c2+ +cn =，且為 6 的倍數(shù)。4給定正整數(shù)n，已知克數(shù)都是正整數(shù)的k 塊砝碼和一臺天平可以稱出質(zhì)量為1，2， ， n克的所有物品，求k 的最小值 f(n)。5空間中有1989 個點，其中任何3 點都不共線，把它們分成點數(shù)各不相同的30 組，在任何 3 個不同的組中各取一點為