杯子里的互質數

匈牙利著名數學家保羅·埃杜斯教授，聽說有一個叫路易·波沙的少年，聰明過人，擅長解數學題．埃杜斯教授心想，這是一個難得的人才，我要親自考驗考驗他．

埃杜斯教授到了波沙的家中，見到了12歲的波沙．教授給他提了個問題：“從1，2，3直到100中任意取出51個數，那么至少有兩個數是互質的．你能說出其中的道理嗎？”（兩個正整數互質，指的是它們沒有大于1的公約數，比如4和9）

波沙稍微想了一下，把父母和教授面前的杯子都移到自己的面前.他指著這些杯子說：“這幾只杯子就算50個吧．我把1和2這兩個數放進第1個杯子，把3和4兩個數放進第2個杯子……這樣兩個兩個地往杯子里放，最后把99和100兩個數放進第50個杯子里．我這樣放可以吧？”

教授點點頭說：“可以，當然可以這樣放了．”

波沙又說：“因為我要從1到100中挑出51個數，所以至少有一只杯子里的兩個數會全部被我挑走，對吧？而這同一只杯子里的兩個數是緊挨著的、連續的，兩個連續的正整數必然互質．”

埃杜斯教授笑著說：“你的杯子能喝酒、喝咖啡，還能做題，你這可是多用杯呀！”教授幾句幽默話，把大家都逗笑了．

埃杜斯教授追問：“為什么相鄰的正整數一定互質呢？”

波沙說：“假設a、b為兩個相鄰的正整數而又不互質（且b>a），那么a和b必存在著大于1的公約數c.于是a=mc，b=nc，m≠n，從而b-a=（n-m）c.所以c一定是b-a的約數．因為b-a=1，故b-a存在大于1的約數是不可能的！因此，兩個相鄰的正整數必然互質．”

埃杜斯教授夸獎小波沙：“答得很好！”

……

小波沙在解答埃杜斯教授的問題時，使用了兩個數學原理：抽屜原理和反證法．

什么是“抽屜原理”呢？

如果將n+1件物體放進n個抽屜里，那么至少有一個抽屜里放著2件或2件以上的物體．

這就是抽屜原理.這個抽屜原理是顯而易見的，也幾乎是不言自明的．

抽屜原理也叫做“鴿籠原理”或“鞋盒原理”，是數學中經常使用的原理．請看下面的問題：

在一所有400名學生的小學里，會有兩個小學生的生日相同嗎？

1月1日到12月31日可以看做365（或366）個抽屜，而要把400個人的生日往這365（或366）個抽屜里“放”，那么至少有兩個人的生日是在同一個抽屜里，也就是說至少有兩個人的生日相同．

當然，這個問題比較簡單，直接一說就明白了．如果問題稍微復雜一點，在使用抽屜原理時，就要講究一些方法了．請看下面的問題：

現有9個人，每個人都有一支紅藍雙色圓珠筆．每個人用雙色圓珠筆寫下“愛科學”三個字，每個字必須用同一種顏色寫，各個字的顏色是隨意的.試說明其中至少有兩個人寫字顏色是完全相同的（即所寫的每個字的顏色都一樣）．

如果用0代表紅色字，用1代表藍色字，那么用紅藍兩種顏色寫“愛科學”三個字，會出現如下8種可能情況：

0，0，0，即紅，紅，紅；1，1，0，即藍，藍，紅；

1，0，0，即藍，紅，紅；1，0，1，即藍，紅，藍；

0，1，0，即紅，藍，紅；0，1，1，即紅，藍，藍；

0，0，1，即紅，紅，藍；1，1，1，即藍，藍，藍．

這8種可能可以看做是8個抽屜.現在有9個人寫字，可以看成是要在8個抽屜中裝進9件物體．由抽屜原理可知，至少有兩個人所寫的字的顏色完全相同．