鴿巢原理是非常著名的原理，生活正用的也很多。

文章目錄

• • 1 簡(jiǎn)單鴿巢原理的應(yīng)用
  • 2 定理（一般性鴿巢原理）
  • • 2.1 應(yīng)用
  • 3 總結(jié)

1 簡(jiǎn)單鴿巢原理的應(yīng)用

定理（鴿巢原理）

• 若有 n 個(gè)鴿巢， n+1 個(gè)鴿子，則至少有一個(gè)巢內(nèi)有至少兩個(gè)鴿子。

例1

假設(shè)在一個(gè)盒子里面有10雙黑色襪子、 12雙藍(lán)色襪子和8雙紅色襪子。那么拿出4只襪子一定可以保證有同色的兩只。

• 每種顏色作為抽屜
• 拿出的襪子數(shù)目作為蘋果

例2

在1到10中選取6個(gè)數(shù)，則其中必定有兩個(gè)數(shù)的和是11。

例3

一次酒會(huì)上有 n 名來(lái)賓，其中一些來(lái)賓相互握手致意，已知沒有人和自己握手、兩人之間至多只握一次手。證明：一定有兩名來(lái)賓的握手次數(shù)相同。

• 將來(lái)賓作為“蘋果”，握手的次數(shù)作為“抽屜”。
• 每名來(lái)賓的握手次數(shù)最多為 n?1 ， 最少為 0 。
  • 但是不可能既有來(lái)賓握手次數(shù)為 n?1 又有來(lái)賓握手次數(shù)為 0 ；
  • 假如有來(lái)賓握手次數(shù)為 n?1 ， 則說明他與其他任何一名來(lái)賓都握過手，那么不可能有來(lái)賓沒有與其它人握過手；
• 反過來(lái)，假如有來(lái)賓握手次數(shù)為 0 ， 則說明他與其他任何一名來(lái)賓都沒有握過手，那么不可能有來(lái)賓與其它人都握過手。
• 因此抽屜的個(gè)數(shù)最多為 n?1，蘋果的個(gè)數(shù)為 n，必定有兩個(gè)蘋果在同一個(gè)抽屜中，也即必定有兩名來(lái)賓的握手次數(shù)相同

例4

任意12個(gè)整數(shù)中一定存在兩個(gè)整數(shù)，其差是11的倍數(shù)。

• 任何一個(gè)整數(shù)模11的余數(shù)都只有11種：0, 1, 2, …, 10；于是任意的12個(gè)整數(shù)中必定存在兩個(gè)整數(shù)模11的余數(shù)相同，它們的差就是11的倍數(shù)。

2 定理（一般性鴿巢原理）

• 定理：

設(shè) m1, m2, … , mn 都是正整數(shù)， 并有m₁+m₂+…+m_n+n+ 1 只鴿子住進(jìn) n 個(gè)鴿巢，則至少對(duì)某個(gè) i 有： 第 i 個(gè)巢中至少有 mi 個(gè)鴿子， i=1, 2, …, n。

推論：

m 只鴿子住進(jìn) n 個(gè)巢， 且 m-1=q*n+r，其中 q 和 r 是整數(shù)， 且 0≤r<n 。 則至少有一個(gè)巢里有 q+1 只鴿子。

2.1 應(yīng)用

例5

• 如果小張?jiān)?5天內(nèi)作了170道習(xí)題，那么他一定有某一天做了至少12道習(xí)題。

170-1 = 169 = 11*15+4

3 總結(jié)

• 學(xué)好數(shù)學(xué)

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【离散数学中的数据结构与算法】九 鸽巢原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。