用剩余類造“抽屜”解證一類存在性競賽題

任意整數(shù)除以m(m是大于1的正整數(shù))所得余數(shù)只有m種情形，即余數(shù)為0，1，…，m-1，把被m除所得余數(shù)相同者歸為一類，稱為以m為模的一個剩余類.如：整數(shù)按除以2余1還是0，分為奇數(shù)和偶數(shù).又如，整數(shù)除以3，余數(shù)只能是0，1，2這3種情況，我們可把所有整數(shù)按除以3后的余數(shù)分3類，即3k型數(shù)，3k+1型數(shù)，3k+2型數(shù)(k是整數(shù)).在數(shù)論中有一類存在性問題常可借助某正整數(shù)的剩余類構(gòu)造“抽屜”給予解決，本文略舉數(shù)例作剖析，旨在探索題型規(guī)律，總結(jié)解題方法.

1.直接以題中的已知數(shù)為模，獲得作為“抽屜”的剩余類

例1 從1到100的100個整數(shù)中，最多可以取出多少個數(shù)，使得這些數(shù)中沒有兩個數(shù)的差是5的倍數(shù)?

解：任何一個整數(shù)除以5的余數(shù)只能是：0，1，2，3，4，從這5類中各取一個數(shù)，這些數(shù)中沒有兩個數(shù)的差是5的倍數(shù).故從1到100的100個整數(shù)中最多可以取出5個數(shù)，使得其中沒有兩個數(shù)的差是5的倍數(shù).

例2 求證：在任何5個整數(shù)中，總可以找到這樣的3個數(shù)，它們的和是3的倍數(shù).

分析：將模3的3個剩余類看作3個“抽屜”，分別放置形如3k，3k+1，3k+2(k是整數(shù))的數(shù).

證明：將所給的5個整數(shù)按照除以3的余數(shù)分為三類.

(1)如果每一類都不是空集，那么在每類中分別取一個數(shù)，它們被3除的余數(shù)分別為0，1，2，顯然這三個數(shù)的和是3的倍數(shù)；

(2)如果這三類中有空集，那么在兩個不空的類中必有某一類含有三個數(shù)，即必有三個數(shù)被3除的余數(shù)相同，這三個數(shù)的和是3的倍數(shù).

因此，無論5個整數(shù)在模3的3個剩余類中如何分布，總能找到其和為3的倍數(shù)的三個數(shù).

例3 任給7個不同的整數(shù)，證明其中必有兩個數(shù)，其和或差是10的倍數(shù).

分析：首先考慮什么樣的兩個整數(shù)的和或差可被10整除.設(shè)兩個整數(shù)a，b，若a≡b(mod10)，則10|(a-b);若a≡r(mod10)，而b=10-r(mod10)，則10|(a+b)，只有這兩種情況.但是如果按整數(shù)除以10的余數(shù)造抽屜，就有十個抽屜，對于已知條件中給定的7個數(shù)無法應(yīng)用抽屜原理，所以要考慮如何造6個抽屜.根據(jù)上面考慮的兩個整數(shù)被10除的兩種情況，可把余數(shù)之和等于10的并成1類，這樣分為：余數(shù)為0的數(shù)，余數(shù)為1或9的數(shù)，余數(shù)為2或8的數(shù)，余數(shù)為3或7的數(shù)，余數(shù)為4或6的數(shù)，余數(shù)為5的數(shù)，共6類，恰好構(gòu)成6個抽屜.

證明：按照除以10的余數(shù)構(gòu)造上述6個抽屜，這樣任給的7個整數(shù)按照除以10的余數(shù)r，放入6個抽屜中，必有1個抽屜中至少有兩個數(shù)，這兩數(shù)的和或差必是10的倍數(shù).

點評：例1、例2、例3的共同點在于不僅作為模的那個整數(shù)顯而易見，而且作為要放入“抽屜”的數(shù)也已經(jīng)明確地給出了.下面的三個例子中，作為模的那個整數(shù)同樣不難看出，但要把怎樣的數(shù)作為物品放入“抽屜”則需要作一番思考.

例4 證明：從任意的7個整數(shù)a1，a2，…，a7中必可選出若干個數(shù)，它們的和(包括只有一個數(shù)的情形)被7整除.

分析：由于對模7的同一剩余類中的兩數(shù)而言，其差必定能被7整除，因此本題的關(guān)鍵在于設(shè)法將從任意的7個整數(shù)a1，a2，…，a7中選出“若干個數(shù)之和”的問題轉(zhuǎn)化為“某兩個‘新數(shù)’之差”的問題，然后再用抽屜原理解決.

證明：我們考慮下面的7個整數(shù)：a1，a1+a2，a1+a2+a3，…，a1+a2+…+a7，如果其中有一個數(shù)是7的倍數(shù)，則結(jié)論成立；否則，以上7個整數(shù)中必有兩個屬于模7的同一剩余類(余數(shù)為1到6的六個剩余類中的某一個)，這兩數(shù)之差能被7整除，并且它可表示成已知的7個整數(shù)a1，a2，…，a7中若干個數(shù)之和的形式.

注：本題中的正整數(shù)7可換成任意的正整數(shù)m，證明方法則完全相同.

例5 設(shè)m是任意大于1的正整數(shù)，證明：必有一個正整數(shù)a是m的倍數(shù)，并且它的十進制表示中，數(shù)碼均為0或1.

分析：毫無疑問，應(yīng)以正整數(shù)m的m個剩余類作為“抽屜”.而要使落入某一剩余類的兩數(shù)之差數(shù)碼均為0或1，只要選擇各位數(shù)碼都是1的數(shù)即可.

證明：取數(shù)1，11，111，1111，….把這無窮多個數(shù)按模m的余數(shù)分類.

由于模m的剩余類個數(shù)有限，所以1，11，111，1111，…中必有兩個屬于模m的同一剩余類，于是它們的差(記為a)能被m整除，而且顯然a的十進制表示中，數(shù)碼只有0或1.

例6 設(shè)n為大于1的正奇數(shù)，證明：2-1，22-1，…，2n-1-1中必有一個數(shù)是n的倍數(shù).

分析：由于2的正整數(shù)指數(shù)冪只有2這個質(zhì)因數(shù)，因此，1，2，22，…，2n-1都與大于1的正奇數(shù)n互質(zhì)，當然也就不能被n整除，故考慮將，1，2，22，…，2n-1放入模n的n-1個剩余類(除去余數(shù)為0的那個)所構(gòu)成的“抽屜”中.

證明：在1，2，22，…，2n-1中沒有一個數(shù)是n的倍數(shù)，故它們除以n所得的余數(shù)只能是1，2，…，n-1，所以這n個數(shù)中必有兩個數(shù)對模n同余，即有2i≡2j(modn)，其中i，j都是整數(shù)，且0≤i

又n為正奇數(shù)，∴(2i，n)=1，從而2i=2j(modn)，即n|(2j-i-1)，這里0≤j-i≤n-1，命題獲證.

2.綜合其它相關(guān)知識尋找合適的模，獲得作為“抽屜”的剩余類

對于以下兩個存在性問題的處理，我們不能看出也要采用剩余類作為“抽屜”，但究竟以什么數(shù)作為模并不能一下子從所給題目中看出來，這時就需要我們綜合其他相關(guān)知識進行分析以確定合適的整數(shù)作為模，進而利用該模的剩余類制造出“抽屜”.

例7 給出12個彼此不同的兩位數(shù)，證明：由它們中一定可選出兩個數(shù)，它們的差是兩個相同數(shù)字組成的兩位數(shù).

分析：證這道題要考慮到以下3點：①對于兩位數(shù)而言，數(shù)碼相同等價于能被11整除；②遇到若干個數(shù)是任意的，若排個序則在討論時表述起來比較方便；③用12個數(shù)中最大的數(shù)依次地分別減去其余11個數(shù)可得到11個差.若差中有相同數(shù)碼組成的兩位數(shù)，問題得證；若差中沒有符合條件的兩位數(shù)，這時這11個(差)數(shù)各自除以11，所得余數(shù)只可能在1，2，3，…，10中，故必有兩個差數(shù)的余數(shù)相同.

證明：設(shè)12個兩位數(shù)從小到大排列為：10

(1)若上面11個差中有某個差bi能被11整除，即11|(a12-ai)，那么a12-ai是由兩個相同數(shù)碼組成的兩位數(shù)；

(2)若這11個差均不能被11整除，則按不能被11整除的余數(shù)造10個抽屜，余數(shù)相同者歸入同一抽屜，根據(jù)抽屜原理，11個差數(shù)中一定存在兩數(shù)bm，bn對于模11同余，即：bm-bn≡0(mod11)，即(a12-am)-(a12-an)=0(mod11)，即an-am≡0(mod11)，即11|(an-am)，即差an-am是由相同數(shù)碼組成的兩位數(shù).

綜合(1)和(2)，問題得證.

例8 求證：在任意17個不同的正整數(shù)中，必定存在幾個這樣的正整數(shù)，只用減號、乘號與括號，就可以將它們組成一個得數(shù)是21879的倍數(shù)的算式.

分析：由于21879=9×11×13×17，而9、11、13、17兩兩互質(zhì)，所以只要能找到四對(個)數(shù)，使它們的差(它們)分別是17、13、11、9的倍數(shù)，題目就得到證明.

證明：(1)將正整數(shù)按照除以17的余數(shù)0，1，…，16分為17類.可見：在任意17個不同的正整數(shù)中，至少有一個是17的倍數(shù)，或者有兩個數(shù)的差是17的倍數(shù)，設(shè)為(a1-a2).(2)同理，在剩下的16個或者15個數(shù)中，至少有一個是13的倍數(shù)，或者有兩個數(shù)的差是13的倍數(shù)；……；以下類推.

因此，在任意17個不同的正整數(shù)中，必定存在若干個正整數(shù)，只用減號、乘號與括號，就可以將它們組成一個得數(shù)是21879的倍數(shù)的算式.