高一證明題－jennin64

証明的過程都在寫在意見了，我想就用題目給的例子來示範一次，不過有一個前題，如果你一樣抱持著“我討厭鴿子”的心情來看的話，那麼你會讀不下去的。

數學很美，美就美在你會有個感覺：「哇！原來這樣也行！？」

回正題：
「2的5倍為10，3的37倍為111，4的25倍為100，...，試證:給一正整數n，總是可以找到n的某一倍數，其位數皆為0，1組成。」

先解釋題目的意思是：

給我一個數字 2時，問��能不能找到一個整數，都是由0、1組成，然後是2的倍數。答案是可以，10就是，那麼10是怎麼出來的？這個數字夠小，會99乘法表就可以知道。

那麼再給我一個數字3時，一樣能否找到相同規則的一組數字，且為3的倍數？
如果你夠耐心的話，3x1, 3x2,..., 3x37時找到111，發現也是可以。

現在題目說，每個正整數都可以找到一個這樣規則的倍數，然後要我們去証明真的可以。

但是我們總不可能每個數字都這樣一個個去乘，在數學証明中，有些型態其實只是一套操作方法，也就是所謂的SOP，例如輾轉相除法，你只要跟著這樣的步驟一步步的去做，就能找到兩數的最大公因數。

SOP不一定表示最快的方法，但是保証能找到。

那這一題的証明也就是一樣的，它是一個套有標準步驟的方法，至於這個方法怎麼想到的，有時候我也常常會想說：天啊！鬼才想得到。

不過就是有神鬼般的天才想到了，這時候我們就去模仿，學習它的過程，以這題來說，先學會如何操作它的過程，只要這樣做就可找到我們要的數字(由0 1所組成的倍數)。

那麼我把這套方法用實際的例子做幾個給你看。

先說這一題証明中出現的大步驟，細節寫在例子中。
一、找出足夠的幾組數字(n+1 組)
二、用餘數分類
三、看分類中至少有分到2個的那一類
四、把這個分類中拿出兩個數字
五、用大數減小數，減完的數字就是我們要的

先看2這個例子，我們找2+1個數字{1、11、111}
接著把這幾個數字拿來除以2，並觀察餘數
1÷2 = 0…1
11÷2 = 5…1
111÷2 = 55…1

任何正整數除以2的餘數都只有兩種結果，餘0、餘1
把這兩個結果當成籠子，把這3個數字當是鴿子來分類
把除以2後餘0的分一類、餘1的分一類

那麼餘0 或者餘1，一定有某一種情況會分到最少2個
以這題來說，餘1的情況分到了3個

那麼現在，把最少分到2個的這一類，拿兩個數出來，
然後大的減小的，減完的數就是我們要的
所以不論你拿 1、11 或 11、111 或1、111
那麼大數減小數後的結果都會是2的倍數，且這個結果都是由0 1所組成。

再來看3這個數字，那麼我們就找3+1=4個數字{1、11、111、1111}
接著把這幾個數字拿來除以3，並觀察餘數
1÷3 = 0…1
11÷3 = 3…2
111÷3 = 37…0
1111÷3 = 370…1

3這個數字在這4個數字除以3的過程中就找到結果了，
所以你可以直接就說你找到了，是111

不過這個倍數不是唯一，就像2的case一樣，所以我們還是用sop的步驟來找一次。

任一正整數除以3的餘數都會有三種結果，餘0、餘1、餘2
把這三個結果當成籠子，把這4個數字當鴿子來分類
把除以3後餘0的分一類、餘1的分一類、餘2的分一類

那麼餘0 或者餘1 或者餘2，一定有某一種情況會分到最少2個
以這題來說，餘1的情況分到了2個

那麼現在把分到2個的這一類，拿兩個數出來，也只有1、1111
然後大的減小的是 1111 - 1 = 1110
那麼1110必會是3的倍數，且由0 1所組成。

再來看4這個例子，我們找4+1個數字{1、11、111、1111、11111}
把這幾個數字拿來除以4，觀察餘數
1會餘1
11會餘3
111會餘3
1111會餘3

11111會餘3

任一正整數除以4的餘數都會有4種結果
這4種結果當籠子，這5個數字當鴿子
分類完餘3的結果中4個數字是{11、111、1111、1111}

那麼現在把分到大於2個的這一類，任拿兩個數出來大減小
減完的數必會是4的倍數，且由0 1所組成。

這樣子可以理解証明在寫什麼了嗎？証明寫的是一般情況，應該不然發現3的話要有4組數字，如果今天我問你2829這個字的那個倍數是符合規則的，此時不太可能手動找出2830個數字，然後用一樣的方法一個一個找，除非用電腦，所以証明會用一般式，任意n來表示。

那光是從這個步驟的過程中，你可能會想說，為什麼一定會有某一個分類當中保証有2個以上呢？
這邊就是應用到鴿籠原理，也就是為什麼我們一定要找n+1個數字的原因，這個+1就是保証鴿子一定比籠子多，那麼我們才可以用鴿籠原理來証明有某個分類保証會最少會分到兩個。

請自行拿幾個小數字5~9好了，跟著這個步驟來驗証一下，你自己會更清楚這個過程在做什麼。