抽屜問(wèn)題（數(shù)學(xué)術(shù)語(yǔ)）

抽屜問(wèn)題（數(shù)學(xué)術(shù)語(yǔ)）

抽屜問(wèn)題 （數(shù)學(xué)術(shù)語(yǔ)） 次瀏覽 | 2022.09.14 14:54:50 更新 來(lái)源 ：互聯(lián)網(wǎng) 精選百科 本文由作者推薦 抽屜問(wèn)題數(shù)學(xué)術(shù)語(yǔ)

桌上有十個(gè)蘋果，要把這十個(gè)蘋果放到九個(gè)抽屜里，無(wú)論怎樣放，我們會(huì)發(fā)現(xiàn)至少會(huì)有一個(gè)抽屜里面放不少于兩個(gè)蘋果。這一現(xiàn)象就是我們所說(shuō)的“抽屜原理”。抽屜原理的一般含義為：“如果每個(gè)抽屜代表一個(gè)集合，每一個(gè)蘋果就可以代表一個(gè)元素，假如有n+1個(gè)元素放到n個(gè)集合中去，其中必定有一個(gè)集合里至少有兩個(gè)元素。”抽屜原理有時(shí)也被稱為鴿巢原理。它是組合數(shù)學(xué)中一個(gè)重要的原理。

中文名

抽屜問(wèn)題

又叫

狄利克雷原則

包含

按任意確定的方式分成n個(gè)集合

問(wèn)題

如何構(gòu)造抽屜

原理第一抽屜原理

原理1：把多于n個(gè)的物體放到n個(gè)抽屜里，則至少有一個(gè)抽屜里的東西不少于兩件。 證明（反證法）：如果每個(gè)抽屜至多只能放進(jìn)一個(gè)物體，那么物體的總數(shù)至多是n×1，而不是題設(shè)的n+k(k≥1)，故不可能。

原理2：把多于mn(m乘n)+1（n不為0）個(gè)的物體放到n個(gè)抽屜里，則至少有一個(gè)抽屜里有不少于（m+1）的物體。 證明（反證法）：若每個(gè)抽屜至多放進(jìn)m個(gè)物體,那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體,與題設(shè)不符，故不可能。

原理3：把無(wú)數(shù)還多件物體放入n個(gè)抽屜，則至少有一個(gè)抽屜里有無(wú)數(shù)個(gè)物體。 原理1、2、3都是第一抽屜原理的表述。

第二抽屜原理

把（mn－1）個(gè)物體放入n個(gè)抽屜中，其中必有一個(gè)抽屜中至多有（m—1）個(gè)物體(例如，將3×5-1=14個(gè)物體放入5個(gè)抽屜中，則必定有一個(gè)抽屜中的物體數(shù)少于等于3-1=2)。

常見(jiàn)運(yùn)用構(gòu)造抽屜的方法

運(yùn)用抽屜原理的核心是分析清楚問(wèn)題中，哪個(gè)是物件，哪個(gè)是抽屜。例如，屬相是有12個(gè)，那么任意37個(gè)人中，至少有一個(gè)屬相是不少于4個(gè)人。這時(shí)將屬相看成12個(gè)抽屜，則一個(gè)抽屜中有37/12，即3余1，余數(shù)不考慮，而向上考慮取整數(shù)，所以這里是3+1=4個(gè)人，但這里需要注意的是，前面的余數(shù)1和這里加上的1是不一樣的。

因此，在問(wèn)題中，較多的一方就是物件，較少的一方就是抽屜，比如上述問(wèn)題中的屬相12個(gè)，就是對(duì)應(yīng)抽屜，37個(gè)人就是對(duì)應(yīng)物件，因?yàn)?7相對(duì)12多。

最差原則

最差原則，即考慮所有可能情況中，最不利于某件事情發(fā)生的情況。 例如，有300人到招聘會(huì)求職，其中軟件設(shè)計(jì)有100人，市場(chǎng)營(yíng)銷有80人，財(cái)務(wù)管理有70人，人力資源管理有50人。那么至少有多少人找到工作才能保證一定有70人找的工作專業(yè)相同呢？

此時(shí)我們考慮的最差情況為：軟件設(shè)計(jì)、市場(chǎng)營(yíng)銷和財(cái)務(wù)管理各錄取69人，人力資源管理的50人全部錄取，則此時(shí)再錄取1人就能保證有70人找到的工作專業(yè)相同。因此至少需要69*3+50+1=258人。

根據(jù)第一抽屜原理之原理2推導(dǎo)：mn+1個(gè)人的時(shí)候必有m+1個(gè)人找到的工作專業(yè)相同，所以是要求出mn+1的人數(shù)，已知n=3，m+1=70。考慮到人力資源專業(yè)只有50人，得出mn+1=(69*3+50)+1=258人。

一個(gè)抽屜里有20件襯衫，其中4件是藍(lán)的，7件是灰的，9件是紅的，則應(yīng)從中隨意取出多少件才能保證有5件是同顏色的？

根據(jù)鴿巢原理，n個(gè)鴿巢，kn+1只鴿子，則至少有一個(gè)鴿巢中有k+1只鴿子。若根據(jù)鴿巢原理的推論直接求解，此時(shí)k=4，n=3，則應(yīng)抽取3X4+1=13件才能保證有5件同色。其實(shí)不然，問(wèn)題的模型和鴿巢原理不盡相同。在解決該問(wèn)題時(shí)，應(yīng)該考慮最差的情況，連續(xù)抽取過(guò)程中抽取出4件藍(lán)色的襯衣，即4件藍(lán)色，取走后，問(wèn)題變成有灰色和紅色構(gòu)成相同顏色的情況，這時(shí)，n=2，k+1=5,k=4.故應(yīng)取4+4X2+1=13件。

問(wèn)題分析：該情況下鴿巢原理的推論不再適用，由于藍(lán)色的襯衫只有4件，而題目中要求有5件是同色的，導(dǎo)致4件藍(lán)色襯衫都被抽取出這一最差情況的存在，所以應(yīng)該先考慮最差情況，然后在此基礎(chǔ)上再運(yùn)用鴿巢原理。

證明

（反證法）：若每個(gè)抽屜都有不少于m個(gè)物體，則總共至少有mn個(gè)物體，與題設(shè)矛盾，故不可能。

趣聞

抽屜問(wèn)題

已知n+1個(gè)互不相同的正整數(shù)，它們?nèi)夹∮诨虻扔?n，證明當(dāng)中一定有兩個(gè)數(shù)是互質(zhì)的。 匈牙利大數(shù)學(xué)家厄杜斯(PaulErdous,1913-1996)向當(dāng)年年僅11歲的波薩(LouisPósa)提出這個(gè)問(wèn)題，而小波薩思考了不足半分鐘便能給出正確的答案。

波薩是這樣考慮問(wèn)題：取n個(gè)盒子，在第一個(gè)盒子我們放1和2，在第二個(gè)盒子我們放3和4，第三個(gè)盒子是放5和6，依此類推直到第n個(gè)盒子放2n-1和2n這兩個(gè)數(shù)。

如果我們?cè)趎個(gè)盒子里隨意抽出n+1個(gè)數(shù)。我們馬上看到一定有一個(gè)盒子是被抽空的。因此在這n+1個(gè)數(shù)中必有兩個(gè)數(shù)是連續(xù)數(shù)，很明顯的連續(xù)數(shù)是互質(zhì)的。因此這問(wèn)題就解決了！這就是利用了鴿巢原理的核心思想。

參考資料