古詩詞大全網 - 字典詞典 - 抽屜原理是什麽

抽屜原理是什麽

抽屜原理是“如果每個抽屜代表壹個集合,每壹個蘋果就可以代表壹個元素,假如有n+1個元素放到n個集合中去,其中必定有壹個集合裏至少有兩個元素。” 抽屜原理有時也被稱為鴿巢原理。它是組合數學中壹個重要的原理。

壹、第壹抽屜原理:

1、原理1:?

把多於n個的物體放到n個抽屜裏,則至少有壹個抽屜裏的東西不少於兩件。證明(反證法):如果每個抽屜至多只能放進壹個物體,那麽物體的總數至多是n×1,而不是題設的n+k(k≥1),故不可能。

2、原理2:

把多於mn(m乘n)+1(n不為0)個的物體放到n個抽屜裏,則至少有壹個抽屜裏有不少於(m+1)的物體。證明(反證法):若每個抽屜至多放進m個物體,那麽n個抽屜至多放進mn個物體,與題設不符,故不可能。

二、第二抽屜原理:

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

三、表現形式:

1、設把n+1個元素劃分至n個集合中(A1,A2,…,An),用a1,a2,…,an分別表示這n個集合對應包含的元素個數,則:至少存在某個集合Ai,其包含元素個數值ai大於或等於2。證明:(反證法)假設結論不成立,即對每壹個ai都有ai<2,則因為ai是整數,應有ai≤1。

2、設把nm+1個元素劃分至n個集合中(A1,A2,…,An),用a1,a2,…,an表示這n個集合對應包含的元素個數,則:至少存在某個集合Ai,其包含元素個數值ai大於或等於m+1。證明:(反證法)假設結論不成立,即對每壹個ai都有ai<m+1,則因為ai是整數。

抽屜原理的表述及運用:

壹、表述:

在上面的第壹個結論中,由於壹年最多有366天,因此在367人中至少有2人出生在同月同日。這相當於把367個東西放入 366個抽屜,至少有2個東西在同壹抽屜裏。在第二個結論中,不妨想象將5雙手套分別編號,即號碼為1,2,...,5的手套各有兩只,同號的兩只是壹雙。

任取6只手套,它們的編號至多有5種,因此其中至少有兩只的號碼相同。這相當於把6個東西放入5個抽屜,至少有2個東西在同壹抽屜裏。

二、運用:

運用抽屜原理的核心是分析清楚問題中,哪個是物件,哪個是抽屜。例如,屬相是有12個,那麽任意37個人中,至少有壹個屬相是不少於4個人。這時將屬相看成12個抽屜,則壹個抽屜中有 37/12,即3余1,余數不考慮,而向上考慮取整數,所以這裏是3+1=4個人。

但這裏需要註意的是,前面的余數1和這裏加上的1是不壹樣的,因此,在問題中,較多的壹方就是物件,較少的壹方就是抽屜,比如上述問題中的屬相12個,就是對應抽屜,37個人就是對應物件,因為37相對12多。