第四講 數論的方法技巧之二

4.1  反證法

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

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

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

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

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

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

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

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

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

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

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

說明：顯然結論對（4k+1）位數也成立。但對其他位數的數不一定成立。如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分的總枚數為 0+1=1，這是奇數。每使用一次該機器，1分與1角的總枚數記為Q。下面考查Q的奇偶性。

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

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

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

解：因為表中9個質數之和恰為100，被3除余1，經過每一次操作，總和增加3的倍數，所以表中9個數之和除以3總是余1。如果表中9個數變為相等，那么9個數的總和應能被3整除，這就得出矛盾！

所以，無論經過多少次操作，表中的數都不會變為9個相同的數。