第四講 數(shù)論的方法技巧之二
四、反證法
反證法即首先對(duì)命題的結(jié)論作出相反的假設(shè)，并從此假設(shè)出發(fā)，經(jīng)過(guò)正確的推理，導(dǎo)出矛盾的結(jié)果，這就否定了作為推理出發(fā)點(diǎn)的假設(shè)，從而肯定了原結(jié)論是正確的。
反證法的過(guò)程可簡(jiǎn)述為以下三個(gè)步驟：
1．反設(shè)：假設(shè)所要證明的結(jié)論不成立，而其反面成立；
2．歸謬：由“反設(shè)”出發(fā)，通過(guò)正確的推理，導(dǎo)出矛盾――與已知條件、公理、定義、定理、反設(shè)及明顯的事實(shí)矛盾或自相矛盾；
3．結(jié)論：因?yàn)橥评碚_，產(chǎn)生矛盾的原因在于“反設(shè)”的謬誤，既然結(jié)論的反面不成立，從而肯定了結(jié)論成立。
運(yùn)用反證法的關(guān)鍵在于導(dǎo)致矛盾。在數(shù)論中，不少問(wèn)題是通過(guò)奇偶分析或同余等方法引出矛盾的。
解：如果存在這樣的三位數(shù)，那么就有
100a+10b+c=（10a+b）+（10b+c）+（10a+c）。上式可化簡(jiǎn)為 80a=b+c，而這顯然是不可能的，因?yàn)?/font>a≥1，b≤9，c≤9。這表明所找的數(shù)是不存在的。
說(shuō)明：在證明不存在性的問(wèn)題時(shí)，常用反證法：先假設(shè)存在，即至少有一個(gè)元素，它符合命題中所述的一切要求，然后從這個(gè)存在的元素出發(fā)，進(jìn)行推理，直到產(chǎn)生矛盾。
例2 將某個(gè)17位數(shù)的數(shù)字的排列順序顛倒，再將得到的數(shù)與原來(lái)的數(shù)相加。試說(shuō)明，得到的和中至少有一個(gè)數(shù)字是偶數(shù)。
解：假設(shè)得到的和中沒(méi)有一個(gè)數(shù)字是偶數(shù)，即全是奇數(shù)。在如下式所示的加法算式中，末一列數(shù)字的和d+a為奇數(shù)，從而第一列也是如此，因此第二列數(shù)字的和b+c≤9。將已知數(shù)的前兩位數(shù)字a，b與末兩位數(shù)字c，d去掉，所得的13位數(shù)仍具有“將它的數(shù)字顛倒，得到的數(shù)與它相加，和的數(shù)字都是奇數(shù)”這一性質(zhì)。照此進(jìn)行，每次去掉首末各兩位數(shù)字，最后得到一位數(shù)，它與自身相加是偶數(shù)，矛盾。故和的數(shù)字中必有偶數(shù)。
說(shuō)明：顯然結(jié)論對(duì)（4k+1）位數(shù)也成立。但對(duì)其他位數(shù)的數(shù)不一定成立。如12+21，506+605等。
例3 有一個(gè)魔術(shù)錢幣機(jī)，當(dāng)塞入1枚1分硬幣時(shí)，退出1枚1角和1枚5分的硬幣；當(dāng)塞入1枚5分硬幣時(shí)，退出4枚1角硬幣；當(dāng)塞入1枚1角硬幣時(shí)，退出3枚1分硬幣。小紅由1枚1分硬幣和1枚5分硬幣開(kāi)始，反復(fù)將硬幣塞入機(jī)器，能否在某一時(shí)刻，小紅手中1分的硬幣剛好比1角的硬幣少10枚？
解：開(kāi)始只有1枚1分硬幣，沒(méi)有1角的，所以開(kāi)始時(shí)1角的和1分的總枚數(shù)為 0+1=1，這是奇數(shù)。每使用一次該機(jī)器，1分與1角的總枚數(shù)記為Q。下面考查Q的奇偶性。
如果塞入1枚1分的硬幣，那么Q暫時(shí)減少1，但我們?nèi)』亓?/font>1枚1角的硬幣（和1枚5分的硬幣），所以總數(shù)Q沒(méi)有變化；如果再塞入1枚5分的硬幣（得到4枚1角硬幣），那么Q增加4，而其奇偶性不變；如果塞入1枚1角硬幣，那么Q增加2，其奇偶性也不變。所以每使用一次機(jī)器，Q的奇偶性不變，因?yàn)殚_(kāi)始時(shí)Q為奇數(shù)，它將一直保持為奇數(shù)。
這樣，我們就不可能得到1分硬幣的枚數(shù)剛好比1角硬幣數(shù)少 10的情況，因?yàn)槿绻覀冇?/font>P枚1分硬幣和（P+10）枚1角硬幣，那么1分和1角硬幣的總枚數(shù)為（2P+10），這是一個(gè)偶數(shù)。矛盾。
例 4在3×3的方格表中已如右圖填入了9個(gè)質(zhì)數(shù)。將表中同一行或同一列的3個(gè)數(shù)加上相同的自然數(shù)稱為一次操作。問(wèn)：你能通過(guò)若干次操作使得表中9個(gè)數(shù)都變?yōu)橄嗤臄?shù)嗎？為什么？
解：因?yàn)楸碇?/font>9個(gè)質(zhì)數(shù)之和恰為100，被3除余1，經(jīng)過(guò)每一次操作，總和增加3的倍數(shù)，所以表中9個(gè)數(shù)之和除以3總是余1。如果表中9個(gè)數(shù)變?yōu)橄嗟龋敲?/font>9個(gè)數(shù)的總和應(yīng)能被3整除，這就得出矛盾！
所以，無(wú)論經(jīng)過(guò)多少次操作，表中的數(shù)都不會(huì)變?yōu)?/font>9個(gè)相同的數(shù)。
五、構(gòu)造法
構(gòu)造法是一種重要的數(shù)學(xué)方法，它靈活多樣，數(shù)論中的許多問(wèn)題都可以通過(guò)構(gòu)造某些特殊結(jié)構(gòu)、特殊性質(zhì)的整數(shù)或整數(shù)的組合來(lái)解決。
例5 9999和99！能否表示成為99個(gè)連續(xù)的奇自然數(shù)之和？
解：9999能。因?yàn)?/font>9999等于99個(gè)9998之和，所以可以直接構(gòu)造如下：
9999=（9998-98）+（9998-96）+…+
=（9998-2）+9998+（9998+2）+…+
=（9998+96）+（9998+98）。
99！不能。因?yàn)?/font>99！為偶數(shù)，而99個(gè)奇數(shù)之和為奇數(shù)，所以99！不能表示為99個(gè)連續(xù)奇數(shù)之和。
說(shuō)明：利用構(gòu)造法證明存在性問(wèn)題，只要把滿足題設(shè)要求的數(shù)學(xué)對(duì)象構(gòu)造出來(lái)就行。
例6 從1，2，3，…，999這999個(gè)數(shù)中，要求劃去盡量少的數(shù)，使得余下的數(shù)中每一個(gè)數(shù)都不等于另外兩個(gè)數(shù)的乘積。應(yīng)劃去哪些數(shù)？
解：我們可劃去2，3，…，30，31這30個(gè)數(shù)，因?yàn)閯澣チ松鲜鲞@30個(gè)數(shù)之后，余下的數(shù)中，除1以外的任何兩個(gè)數(shù)之積將大于322=1024＞999。
另一方面，可以通過(guò)構(gòu)造三元數(shù)組來(lái)證明30是最少的個(gè)數(shù)。
（2，61，2×61），（3，60，3×60），（4，59，4×59），…，
（30，33，30×33），（31，32，31×32）。
上面寫(xiě)出的這些數(shù)都是互不相同的，并且這些數(shù)中的最大數(shù)為 31×32=992。如果劃去的數(shù)少于30個(gè)，那么上述三元數(shù)組至少剩下一個(gè)，這樣就不滿足題設(shè)條件。所以，30是最少的個(gè)數(shù)。
六、配對(duì)法
配對(duì)的形式是多樣的，有數(shù)字的湊整配對(duì)，也有集合間元素與元素的配對(duì)（可用于計(jì)數(shù)）。傳說(shuō)高斯8歲時(shí)求和（1+2+…+100）首創(chuàng)了配對(duì)。像高斯那樣，善于使用配對(duì)技巧，常常能使一些表面上看來(lái)很麻煩，甚至很棘手的問(wèn)題迎刃而解。
例7 求1，2，3，…，9999998，9999999這9999999個(gè)數(shù)中所有數(shù)碼的和。
解：在這些數(shù)前面添一個(gè)數(shù)0，并不影響所有數(shù)碼的和。將這1000萬(wàn)個(gè)數(shù)兩兩配對(duì)，因?yàn)?/font>0與9999999，1與9999998，…，4999999與5000000各對(duì)的數(shù)碼和都是9×7=63。這里共有5000000對(duì)，故所有數(shù)碼的和是63×5000000=315000000。
例8 某商場(chǎng)向顧客發(fā)放9999張購(gòu)物券，每張購(gòu)物券上印有一個(gè)四位數(shù)的號(hào)碼，從0001到9999號(hào)。若號(hào)碼的前兩位數(shù)字之和等于后兩位數(shù)字之和，則稱這張購(gòu)物券為“幸運(yùn)券”。例如號(hào)碼 0734，因 0+7=3+4，所以這個(gè)號(hào)碼的購(gòu)物券是幸運(yùn)券。試說(shuō)明，這個(gè)商場(chǎng)所發(fā)的購(gòu)物券中，所有幸運(yùn)券的號(hào)碼之和能被101整除。
解：顯然，號(hào)碼為9999的是幸運(yùn)券，除這張幸運(yùn)券外，如果某個(gè)號(hào)碼n是幸運(yùn)券，那么號(hào)碼為m=9999-n的購(gòu)物券也是幸運(yùn)券。由于9999是奇數(shù)，所以m≠n。
由于m+n=9999，相加時(shí)不出現(xiàn)進(jìn)位，所以除去號(hào)碼是9999這張幸運(yùn)券之外，其余所有幸運(yùn)券可全部?jī)蓛膳鋵?duì)，而每一對(duì)兩個(gè)號(hào)碼之和均為9999，即所有幸運(yùn)券號(hào)碼之和是9999的倍數(shù)。
因?yàn)?/font>9999=99×101，所以所有幸運(yùn)券號(hào)碼之和能被101整除。
試說(shuō)明分子m是質(zhì)數(shù)89的倍數(shù)。
解法一：仿照高斯求和（1+2+3+…+n）的辦法，將和
①②兩式相加，得
從而
2m×88！=89×k（k是正整數(shù)）。
因?yàn)?/font>89為奇質(zhì)數(shù)，所以89不能整除 88！，從而89|m。
解法二：作配對(duì)處理
將括號(hào)內(nèi)的分?jǐn)?shù)進(jìn)行通分，其公分母為
1×88×2×87×3×86×…×44×45=88！，
從而
m×88！=89×k（k=n×q）。
因?yàn)?/font>89為奇質(zhì)數(shù)，所以89不能整除88！，從而89|m。
七、估計(jì)法
估計(jì)法是用不等式放大或縮小的方法來(lái)確定某個(gè)數(shù)或整個(gè)算式的取值范圍，以獲取有關(guān)量的本質(zhì)特征，達(dá)到解題的目的。
在數(shù)論問(wèn)題中，一個(gè)有限范圍內(nèi)的整數(shù)至多有有限個(gè)，過(guò)渡到整數(shù)，就能夠?qū)赡艿那闆r逐一檢驗(yàn)，以確定問(wèn)題的解。
求這個(gè)數(shù)，并求出滿足題意的5組不同的真分?jǐn)?shù)。
解：因每一真分?jǐn)?shù)滿足
而所求的數(shù)整S是四個(gè)不同的真分?jǐn)?shù)之和，因此2＜S＜4，推知S=3。于是可得如下5組不同的真分?jǐn)?shù)：
例11 已知在乘積1×2×3×…×n的尾部恰好有106個(gè)連續(xù)的零，求自然數(shù)n的最大值。
分析：若已知n的具體數(shù)值，求1×2×…×n的尾部零的個(gè)數(shù)，則比較容易解決，現(xiàn)在反過(guò)來(lái)知道尾部零的個(gè)數(shù)，求n的值，不大好處理，我們可以先估計(jì)n大約是多少，然后再仔細(xì)確定n的值。
因此，乘積1×2×3×…×400中含質(zhì)因數(shù)5的個(gè)數(shù)為80+16+3=99（個(gè)）。又乘積中質(zhì)因數(shù)2的個(gè)數(shù)多于5的個(gè)數(shù)，故n=400時(shí)，1×2×…×n的尾部有99個(gè)零，還需 7個(gè)零，注意到425中含有2個(gè)質(zhì)因數(shù)5，所以
當(dāng)n=430時(shí)，1×2×…×n的尾部有106個(gè)零；
當(dāng)n=435時(shí)，1×2×…×n的尾部有107個(gè)零。
因此，n的最大值為434。
