當前位置:趣味科普網>經驗>

鴿巢問題的公式

經驗 閱讀(8.01K)

鴿巢問題的公式

把多於n+1個的物體放到n個抽屜裡,則至少有一個抽屜裡的東西不少於兩件。或把(mn-1)個物體放入n個抽屜中,其中必有一個抽屜中至多有(m—1)個物體(例如,將3×5-1=14個物體放入5個抽屜中,則必定有一個抽屜中的物體數少於等於3-1=2)。

例如13-6+1=8,一共有8個年齡段。

相當於把n個東西,放入8個抽屜,要求必須有1個抽屜有2個東西,求n的最小值。

根據抽屜原理(即鴿巢原理)n=9。

因為把8個抽屜各放一個後,再放入一個無論放哪個抽屜都會出現一個抽屜裡有2個東西。抽屜數(鴿巢的數量)有時是隱藏的,要注意仔細分析,尋找出來,這是解題關鍵。