第四講數(shù)論的方法技巧之二

2008-05-07 13:49:45

第四講數(shù)論的方法技巧之二

四、反證法

　　反證法即首先對命題的結論作出相反的假設，并從此假設出發(fā)，經過正確的推理，導出矛盾的結果，這就否定了作為推理出發(fā)點的假設，從而肯定了原結論是正確的。

　　反證法的過程可簡述為以下三個步驟：

　　1．反設：假設所要證明的結論不成立，而其反面成立；

　　2．歸謬：由“反設”出發(fā)，通過正確的推理，導出矛盾――與已知條件、公理、定義、定理、反設及明顯的事實矛盾或自相矛盾；

　　3．結論：因為推理正確，產生矛盾的原因在于“反設”的謬誤，既然結論的反面不成立，從而肯定了結論成立。

　　運用反證法的關鍵在于導致矛盾。在數(shù)論中，不少問題是通過奇偶分析或同余等方法引出矛盾的。

　　解：如果存在這樣的三位數(shù)，那么就有

　　100a+10b+c=（10a+b）+（10b+c）+（10a+c）。上式可化簡為 80a=b+c，而這顯然是不可能的，因為a≥1，b≤9，c≤9。這表明所找的數(shù)是不存在的。

　　說明：在證明不存在性的問題時，常用反證法：先假設存在，即至少有一個元素，它符合命題中所述的一切要求，然后從這個存在的元素出發(fā)，進行推理，直到產生矛盾。

　　例2 將某個17位數(shù)的數(shù)字的排列順序顛倒，再將得到的數(shù)與原來的數(shù)相加。試說明，得到的和中至少有一個數(shù)字是偶數(shù)。

　　解：假設得到的和中沒有一個數(shù)字是偶數(shù)，即全是奇數(shù)。在如下式所示的加法算式中，末一列數(shù)字的和d+a為奇數(shù)，從而第一列也是如此，因此第二列數(shù)字的和b+c≤9。將已知數(shù)的前兩位數(shù)字a，b與末兩位數(shù)字c，d去掉，所得的13位數(shù)仍具有“將它的數(shù)字顛倒，得到的數(shù)與它相加，和的數(shù)字都是奇數(shù)”這一性質。照此進行，每次去掉首末各兩位數(shù)字，最后得到一位數(shù)，它與自身相加是偶數(shù)，矛盾。故和的數(shù)字中必有偶數(shù)。

　　說明：顯然結論對（4k+1）位數(shù)也成立。但對其他位數(shù)的數(shù)不一定成立。如12+21，506+605等。

　　例3 有一個魔術錢幣機，當塞入1枚1分硬幣時，退出1枚1角和1枚5分的硬幣；當塞入1枚5分硬幣時，退出4枚1角硬幣；當塞入1枚1角硬幣時，退出3枚1分硬幣。小紅由1枚1分硬幣和1枚5分硬幣開始，反復將硬幣塞入機器，能否在某一時刻，小紅手中1分的硬幣剛好比1角的硬幣少10枚？

　　解：開始只有1枚1分硬幣，沒有1角的，所以開始時1角的和1分的總枚數(shù)為 0+1=1，這是奇數(shù)。每使用一次該機器，1分與1角的總枚數(shù)記為Q。下面考查Q的奇偶性。

　　如果塞入1枚1分的硬幣，那么Q暫時減少1，但我們取回了1枚1角的硬幣（和1枚5分的硬幣），所以總數(shù)Q沒有變化；如果再塞入1枚5分的硬幣（得到4枚1角硬幣），那么Q增加4，而其奇偶性不變；如果塞入1枚1角硬幣，那么Q增加2，其奇偶性也不變。所以每使用一次機器，Q的奇偶性不變，因為開始時Q為奇數(shù)，它將一直保持為奇數(shù)。

　　這樣，我們就不可能得到1分硬幣的枚數(shù)剛好比1角硬幣數(shù)少 10的情況，因為如果我們有P枚1分硬幣和（P+10）枚1角硬幣，那么1分和1角硬幣的總枚數(shù)為（2P+10），這是一個偶數(shù)。矛盾。

　　例 4在3×3的方格表中已如右圖填入了9個質數(shù)。將表中同一行或同一列的3個數(shù)加上相同的自然數(shù)稱為一次操作。問：你能通過若干次操作使得表中9個數(shù)都變?yōu)橄嗤臄?shù)嗎？為什么？

　　解：因為表中9個質數(shù)之和恰為100，被3除余1，經過每一次操作，總和增加3的倍數(shù)，所以表中9個數(shù)之和除以3總是余1。如果表中9個數(shù)變?yōu)橄嗟龋敲?/FONT>9個數(shù)的總和應能被3整除，這就得出矛盾！

　　所以，無論經過多少次操作，表中的數(shù)都不會變?yōu)?/FONT>9個相同的數(shù)。

五、構造法

　　構造法是一種重要的數(shù)學方法，它靈活多樣，數(shù)論中的許多問題都可以通過構造某些特殊結構、特殊性質的整數(shù)或整數(shù)的組合來解決。

　　例5 99⁹⁹和99！能否表示成為99個連續(xù)的奇自然數(shù)之和？

　　解：99⁹⁹能。因為99⁹⁹等于99個99⁹⁸之和，所以可以直接構造如下：

　　9999=（99⁹⁸-98）+（99⁹⁸-96）+…+

　　=（99⁹⁸-2）+99⁹⁸+（99⁹⁸+2）+…+

　　=（99⁹⁸+96）+（99⁹⁸+98）。

　　99！不能。因為99！為偶數(shù)，而99個奇數(shù)之和為奇數(shù)，所以99！不能表示為99個連續(xù)奇數(shù)之和。

　　說明：利用構造法證明存在性問題，只要把滿足題設要求的數(shù)學對象構造出來就行。

　　例6 從1，2，3，…，999這999個數(shù)中，要求劃去盡量少的數(shù)，使得余下的數(shù)中每一個數(shù)都不等于另外兩個數(shù)的乘積。應劃去哪些數(shù)？

　　解：我們可劃去2，3，…，30，31這30個數(shù)，因為劃去了上述這30個數(shù)之后，余下的數(shù)中，除1以外的任何兩個數(shù)之積將大于32²=1024＞999。

　　另一方面，可以通過構造三元數(shù)組來證明30是最少的個數(shù)。

　　（2，61，2×61），（3，60，3×60），（4，59，4×59），…，

　　（30，33，30×33），（31，32，31×32）。

　　上面寫出的這些數(shù)都是互不相同的，并且這些數(shù)中的最大數(shù)為 31×32=992。如果劃去的數(shù)少于30個，那么上述三元數(shù)組至少剩下一個，這樣就不滿足題設條件。所以，30是最少的個數(shù)。

六、配對法

　　配對的形式是多樣的，有數(shù)字的湊整配對，也有集合間元素與元素的配對（可用于計數(shù)）。傳說高斯8歲時求和（1+2+…+100）首創(chuàng)了配對。像高斯那樣，善于使用配對技巧，常常能使一些表面上看來很麻煩，甚至很棘手的問題迎刃而解。

　　例7 求1，2，3，…，9999998，9999999這9999999個數(shù)中所有數(shù)碼的和。

　　解：在這些數(shù)前面添一個數(shù)0，并不影響所有數(shù)碼的和。將這1000萬個數(shù)兩兩配對，因為0與9999999，1與9999998，…，4999999與5000000各對的數(shù)碼和都是9×7=63。這里共有5000000對，故所有數(shù)碼的和是63×5000000=315000000。

　　例8 某商場向顧客發(fā)放9999張購物券，每張購物券上印有一個四位數(shù)的號碼，從0001到9999號。若號碼的前兩位數(shù)字之和等于后兩位數(shù)字之和，則稱這張購物券為“幸運券”。例如號碼 0734，因 0+7=3+4，所以這個號碼的購物券是幸運券。試說明，這個商場所發(fā)的購物券中，所有幸運券的號碼之和能被101整除。

　　解：顯然，號碼為9999的是幸運券，除這張幸運券外，如果某個號碼n是幸運券，那么號碼為m=9999-n的購物券也是幸運券。由于9999是奇數(shù)，所以m≠n。

　　由于m+n=9999，相加時不出現(xiàn)進位，所以除去號碼是9999這張幸運券之外，其余所有幸運券可全部兩兩配對，而每一對兩個號碼之和均為9999，即所有幸運券號碼之和是9999的倍數(shù)。

　　因為9999=99×101，所以所有幸運券號碼之和能被101整除。