當前位置:百科全書館>生活百科>家庭生活>

鴿巢原理

家庭生活 閲讀(2.48W)

鴿巢原理

鴿巢原理一般指抽屜原理,是組合數學中一個重要的原理。如果每個抽屜代表一個集合,每一個蘋果代表一個元素,假如有n+1個元素放到n個集合中,其中必定有一個集合裏至少有兩個元素。

把(mn-1)個物體放入n個抽屜中,其中必有一個抽屜中至多有(m-1)個物體(例如:將3×5-1=14個物體放入5個抽屜中,則必定有一個抽屜中的物體數少於等於3-1=2)。

運用抽屜原理的核心是分析清楚問題中,哪個是物件,哪個是抽屜。例如:屬相是有12個,那麼任意37個人中,至少有一個屬相是不少於4個人。這時將屬相看成12個抽屜,則一個抽屜中有37/12,即3餘1,餘數不考慮,而向上考慮取整數,所以這裏是3+1=4個人,但這裏需要注意的是,前面的餘數1和這裏加上的1是不一樣的。

因此,在問題中,較多的一方就是物件,較少的一方就是抽屜,比如上述問題中的屬相12個,就是對應抽屜,37個人就是對應物件,因為37相對12多。