六人集會(huì)和抽屜原理問(wèn)題

　　“任意367個(gè)人中，必有生日相同的人。”

　　“從任意5雙手套中任取6只，其中至少有2只恰為一雙手套。”

　　“從數(shù)1，2，...，10中任取6個(gè)數(shù)，其中至少有2個(gè)數(shù)為奇偶性不同。”

　　......

　　大家都會(huì)認(rèn)為上面所述結(jié)論是正確的。這些結(jié)論是依據(jù)什么原理得出的呢？這個(gè)原理叫做抽屜原理。它的內(nèi)容可以用形象的語(yǔ)言表述為：

　　“把m個(gè)東西任意分放進(jìn)n個(gè)空抽屜里（m>n），那么一定有一個(gè)抽屜中放進(jìn)了至少2個(gè)東西。”

　　在上面的第一個(gè)結(jié)論中，由于一年最多有366天，因此在367人中至少有2人出生在同月同日。這相當(dāng)于把367個(gè)東西放入366個(gè)抽屜，至少有2個(gè)東西在同一抽屜里。在第二個(gè)結(jié)論中，不妨想象將5雙手套分別編號(hào)，即號(hào)碼為1，2，...，5的手套各有兩只，同號(hào)的兩只是一雙。任取6只手套，它們的編號(hào)至多有5種，因此其中至少有兩只的號(hào)碼相同。這相當(dāng)于把6個(gè)東西放入5個(gè)抽屜，至少有2個(gè)東西在同一抽屜里。

　　抽屜原理的一種更一般的表述為：

　　“把多于kn個(gè)東西任意分放進(jìn)n個(gè)空抽屜（k是正整數(shù)），那么一定有一個(gè)抽屜中放進(jìn)了至少k+1個(gè)東西。”

　　利用上述原理容易證明：“任意7個(gè)整數(shù)中，至少有3個(gè)數(shù)的兩兩之差是3的倍數(shù)。”因?yàn)槿我徽麛?shù)除以3時(shí)余數(shù)只有0、1、2三種可能，所以7個(gè)整數(shù)中至少有3個(gè)數(shù)除以3所得余數(shù)相同，即它們兩兩之差是3的倍數(shù)。

　　如果問(wèn)題所討論的對(duì)象有無(wú)限多個(gè)，抽屜原理還有另一種表述：

　　“把無(wú)限多個(gè)東西任意分放進(jìn)n個(gè)空抽屜（n是自然數(shù)），那么一定有一個(gè)抽屜中放進(jìn)了無(wú)限多個(gè)東西。”

　　抽屜原理的內(nèi)容簡(jiǎn)明樸素，易于接受，它在數(shù)學(xué)問(wèn)題中有重要的作用。許多有關(guān)存在性的證明都可用它來(lái)解決。

　　1958年6/7月號(hào)的《美國(guó)數(shù)學(xué)月刊》上有這樣一道題目：

　　“證明在任意6個(gè)人的集會(huì)上，或者有3個(gè)人以前彼此相識(shí)，或者有三個(gè)人以前彼此不相識(shí)。”

　　這個(gè)問(wèn)題可以用如下方法簡(jiǎn)單明了地證出：

　　在平面上用6個(gè)點(diǎn)A、B、C、D、E、F分別代表參加集會(huì)的任意6個(gè)人。如果兩人以前彼此認(rèn)識(shí)，那么就在代表他們的兩點(diǎn)間連成一條紅線(xiàn)；否則連一條藍(lán)線(xiàn)。考慮A點(diǎn)與其余各點(diǎn)間的5條連線(xiàn)AB，AC，...，AF，它們的顏色不超過(guò)2種。根據(jù)抽屜原理可知其中至少有3條連線(xiàn)同色，不妨設(shè)AB，AC，AD同為紅色。如果BC，BD，CD3條連線(xiàn)中有一條（不妨設(shè)為BC）也為紅色，那么三角形ABC即一個(gè)紅色三角形，A、B、C代表的3個(gè)人以前彼此相識(shí)：如果BC、BD、CD3條連線(xiàn)全為藍(lán)色，那么三角形BCD即一個(gè)藍(lán)色三角形，B、C、D代表的3個(gè)人以前彼此不相識(shí)。不論哪種情形發(fā)生，都符合問(wèn)題的結(jié)論。

　　六人集會(huì)問(wèn)題是組合數(shù)學(xué)中著名的拉姆塞定理的一個(gè)最簡(jiǎn)單的特例，這個(gè)簡(jiǎn)單問(wèn)題的證明思想可用來(lái)得出另外一些深入的結(jié)論。這些結(jié)論構(gòu)成了組合數(shù)學(xué)中的重要內(nèi)容-----拉姆塞理論。從六人集會(huì)問(wèn)題的證明中，我們又一次看到了抽屜原理的應(yīng)用。
 

　　 歡迎使用手機(jī)、平板等移動(dòng)設(shè)備訪(fǎng)問(wèn)中考網(wǎng)，2024中考一路陪伴同行！>>點(diǎn)擊查看