鴿籠原理

鴿籠原理

鴿籠原理 (抽屜原理) “如果有五個鴿子籠,養鴿人養了6隻鴿子,那么當鴿子飛回籠中後,至少有一個籠子中裝有2隻或2隻以上鴿子。”這個簡單的事實就是著名的鴿籠原理,在我們國家更多地稱為抽屜原理。由鴿籠原理知A、B、C 三數中各數位上都有一個數字是正確的(即與M和N的相應數字相同)。這個賽程的公平性如何呢,不妨只看看各隊每兩場比賽中間得到的休整時間是否均等. 表的右半部分是各隊每兩場比賽間相隔的場次數,顯然這個賽程對A,E有利,對D則不公平.

更一般的敘述

有n+1件或n+1件以上的物品要放到n個抽屜中,那么至少有一個抽屜里有兩個或兩個以上物品。

英文:pigeonhole principle

套用

套用廣泛

鴿籠原理鴿籠原理

抽屜原理雖然簡單,但套用卻很廣泛。它可以解答很多有趣的

問題,其中有些問題還具有相當的難度。

下面我們來研究有關的一些問題。

問題1

某校國中部有30個班,每班平均52人。已知這些學生的90%都是在1978~1980年這三年出生的,問他們中有同年同月同日出生的嗎?

解:全校共有學生52×30=1560人,1978~1980年間出生的有1560×90%=1404人。

而這三年有365×3+1=1096天。

由鴿籠原理知道,至少有兩個同學是同年同月同日出生的。

問題2

一個書架有五層,從下至上依次稱第1,第2,…,第5層.今把15冊圖書分別放在書架的各層上,有些層可以不放,證明:無論怎樣放法,書架每層上的圖書冊數以及相鄰兩層內圖書冊數之和,所有這些數中至少有兩個是相等的.

解:我們先把這個實際問題抽象成數學問題.用xi表示第i層放書的冊數(i=1,2,…,5).

若有某個xi=0,則相鄰的一層放書冊數等於它與第i層放書冊數之和,結論成立.

下面考慮xi≥1(i=1,2,3,4,5)的情況:

⑴若x1,x2,…,x5中已有兩數相等,結論成立.

⑵若x1,x2,…,x5兩兩不等,再由它們和為15,所以它們分別取1,2,3,4,5.我們容易驗證,在x1+x2,x2+x3,x3+x4,x4+x5這四個數中不可能同時包含6,7,8,9這四個數(請讀者驗證).這四個數與x1,x2,…,x5總共九個數,但只能有8種取值,因此其中必有兩數相等。

問題3

某個信封上兩個郵政編碼M和N均由0,1,2,3,5,6這六個不同數字組成,現有4個郵政編碼如下:

A:320651,B:105263,C:612305,D:316250.已知編碼A,B,C各恰有兩個數字的位置與M和N相同,D恰有三個數字的位置與M和N相同,試求M和N.

解:

-------------------------------------------------------------

A:320651 恰有兩個數字的位置與M和N相同

B:105263 恰有兩個數字的位置與M和N相同

C:612305 恰有兩個數字的位置與M和N相同

D:316250 恰有三個數字的位置與M和N相同

-------------------------------------------------------------

首先仔細觀察A、B、C。它們雖然均由0、1、2、3、5、6這六個數碼組成,但同一數位上的數字都互不相同。

由鴿籠原理知A、B、C 三數中各數位上都有一個數字是正確的(即與M和N的相應數字相同)。

再把D的各數位上的數與A、B、C 比較,發現D中第3位的6和第6位的0在A、B、C 的第3和第6位上沒有出現,

因此這兩個數碼肯定不正確。由已知D有三個數字正確。因此D中的3、1、2、5四個數字中只有一個不對。

得到結果為:31X25XX=未知數

-------------------------------------------------------------

以下數字必須符合31X25X的數字對應位置。必須滿足D:316250恰有三個數字的位置與M和N相同。

下面逐個討論驗證:

若3不對,取得以下結果:

X1X25X613250 610253

X1X25X013256 016253

若1不對,取得以下結果:

3XX25X301256 306251

3XX25X361250 360251

若2不對,取得以下結果:

31XX5X312056 316052

31XX5X310652 312650

若5不對,取得以下結果:

31X2XX310265 315260

31X2XX316205 315206

-------------------------------------------------------------

回頭校正所有結果,必須滿足A、B、C 當中有且僅有兩個數字的位置與M和N相同

613250X 不符合A,排除

610253

013256X 不符合A,排除

016253X 第3位為6,排除

301256x 不符合C,排除

306251X 第3位為6,排除

361250X 第6位為0,排除

360251X

312056X 不符合B,排除

316052X 第3位為6,排除

310652X 不符合A,排除

312650X 第6位為0,排除

310265

315260X 第6位為0,排除

316205X 第3位為6,排除

315206X 不符合A,排除

-------------------------------------------------------------

最後檢驗所有條件,可知 610253 與 310265 是滿足這些條件的兩個數。

問題4

在前100個自然數中任取51個數,求證:一定存在兩個數,其中一個是另一個的整數倍.

解:我們用鴿籠原理來考慮.把這100個自然數分成50組,使得每組中的數(如果至少含兩個數)是倍數關係,怎樣分組呢 我們記

A1={1,1×21,1×22,1×23,…,1×26},

A2={3,3×21,3×22,…,3×25},

A3={5,5×21,5×22,5×23,5×24},

………………………

A25={49,49×2},A26=,A27=,

………………

A50=.

這50組數中包含了從1到100這100個自然數.根據鴿籠原理從中任取51個數,至少必有兩個數在同一組中,這兩個數中的一個必為另一個的整數倍。

另解:(個人覺得)這個問題有更容易理解的解法

將這51個數,全部轉換為 2^r * b (2的r次方乘以b)

比如這51個數為3、5、7、8、22......

2--> 2^1* 1

5-->2^0* 5

7-->2^0* 7

8-->2^3* 1

22-->2^1*11

......

提取出的51個b都滿足

⑴ 必然是奇數

⑵ 必然小於100

而小於100的奇數只有50個,由鴿籠原理

==> 必然存在2個b相等,則這2個b對應的數必然滿足,其中一個是另一個的倍數

問題5

17個科學家中每個人與其餘16個人通信,他們通信所討論的僅有三個問題,而任兩個科學家之間通信討論的是同一個問題.證明:至少有三個科學家通信時討論的是同一個問題.

解:不妨設A是某科學家,他與其餘16位討論僅三個問題,由鴿籠原理知,他至少與其中的6位討論同一問題.設這6位科學家為B,C,D

若這6位中有兩位之間也討論甲問題,則結論成立.否則他們6位只討論乙,丙兩問題.這樣又由鴿籠原理知B至少與另三位討論同一問題,不妨設這三位是C,D,E,且討論的是乙問題。

若C,D,E中有兩人也討論乙問題,則結論也就成立了。否則,他們間只討論丙問題,這樣結論也成立。

問題6(2002年數學建模d題)

你所在的年級有5個班,每班一支球隊在同一塊場地上進行單循環賽,共要進行10場比賽. 如何安排賽程使對各隊來說都儘量公平呢. 下面是隨便安排的一個賽程: 記5支球隊為A,B,C,D,E,在下表左半部分的右上三角的10個空格中,隨手填上1,2,¼10,就得到一個賽程,即第1場A對B,第2場B對C,¼;,第10場C對E. 為方便起見將這些數字沿對角線對稱地填入左下三角.

這個賽程的公平性如何呢,不妨只看看各隊每兩場比賽中間得到的休整時間是否均等. 表的右半部分是各隊每兩場比賽間相隔的場次數,顯然這個賽程對A,E有利,對D則不公平.


A B C D E 每兩場比賽間相隔場次數
A X 1 9 3 6 1,2,2
B 1 X 2 5 8 0,2,2
C 9 2 X 7 10 4,1,0
D 3 5 7 X 4 0,0,1
E 6 8 10 4 X 1,1,1

相關詞條

相關搜尋

熱門詞條

聯絡我們