歐陽維誠

匈牙利是世界上開展中學生數(shù)學競賽最早的國家．匈牙利全國中學生數(shù)學競賽中有這樣一道試題：

證明：在任何６個人中，一定可以找到３個互相認識的人，或者３個互不認識的人．

這個問題乍看起來，似乎令人難以想像．若店中坐著６位客人，萍水相逢，全是他鄉(xiāng)之客，我們憑什么能夠判斷他們之中，必有３個人互相認識，或者３個人互不認識呢？這個問題用數(shù)學方法來證明卻出人意料地簡單．

為簡單直觀起見，我們用平面上的６個點Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ來代表６個人，如果兩人互相認識，就在代表他們的兩點之間連一條線；如果兩人互不認識，則不連線．這樣就會得到一個由一些點和線組成的圖．

現(xiàn)在從６個人中隨便挑出一個人，比方說是Ａ吧，其余５個人中，或者與Ａ認識，或者與Ａ不認識．不妨假定：與Ａ認識的人有３個（否則與Ａ不認識的人就至少有３個，把“與Ａ認識”換成“與Ａ不認識”即可），例如，Ｂ、Ｃ、Ｄ與Ａ認識，如圖１所示，ＡＢ、ＡＣ、ＡＤ之間就連有一條線．

再看Ｂ、Ｃ、Ｄ三人，如果他們彼此都不認識，那么我們就在６個人中找到了３個互不認識的人，本題的結論成立．如果Ｂ、Ｃ、Ｄ中至少有兩人互相認識，例如Ｂ與Ｃ互相認識，那么Ｂ與Ｃ之間就要連一條線，這時圖中出現(xiàn)了一個三角形ＡＢＣ，如圖２．這意味著Ａ、Ｂ、Ｃ之間互相認識，同樣證明了本題的結論．

像圖１和圖２那樣由一些點和線所組成的圖形在數(shù)學中稱為圖，專門研究圖的性質的一門數(shù)學分支稱為圖論．圖論是最近幾十年才發(fā)展起來的，它依靠自己獨特的思維方式解決了許多數(shù)學問題，特別是許多實際問題都可以歸結為圖論問題來研究．

世界上的萬事萬物都被某些關系聯(lián)系著，對于某一個特定的關系來說，有些事物之間具有這種關系，另一些事物之間則不具有這種關系．如果把一個圖中的點看作一些事物，點與點之間的連線看作某種關系，那么一個圖就可以抽象地代表許多事物之間的一種關系．如果我們把圖２中的點看作城市，線看作城市之間通航的關系，它就是一張城市的空中交通圖．如果把點看成國家，線看作互相建立了外交關系，那么圖２就表示這些國家的國際關系示意圖，等等．所以研究圖的性質可以解決許多問題．

現(xiàn)在我們再來研究一個與“故人”有關的趣味問題．

在一次大型的國際會議中，有１ ０００位來自不同國家的代表參加會議，每個代表都懂得多種語言．已經(jīng)知道，在這１ ０００名代表中的任意３人都可以進行交談，而不必要求另外的人幫助（但允許３人中有１人為其余２人充當翻譯）．現(xiàn)在，會務組想把這１ ０００位代表分配住進５００個房間里，每個房間兩人，使得每個房間里的兩個人都可以進行交談．

你認為可以辦得到嗎？如果你認為不能，請說明理由；如果你認為可能，請說出一種具體的分配方法．

分配是可能的．

因為在１ ０００名代表中任選３人，根據(jù)假設，其中至少有２人可以直接相互交談，把這兩人安排到第一號房間．

從剩下的９９８人中又任選３人，也至少有２人可以直接交談，把這兩人安排到第２號房間．

再從剩下的９９６人中任選３人，仍然至少有２人可以直接交談，把這２人分配到第３號房間．

如此繼續(xù)下去，每次減少２人，最后剩下４個人待分配．這時已不能再采用上述的辦法了，因為如果最后只剩下２人，這２人可能需要第３人翻譯才能交談．因此，在剩下４人時考慮另外的分配方法，才有調整的余地．

現(xiàn)在我們來安排最后４個人．

設Ａ、Ｂ、Ｃ、Ｄ表示最后待安排的４個人，若兩人能直接交談，則在兩點之間連一條線，若兩人不能直接交談，則兩點之間不連線．因為任何３個人都可以互相交談，所以任何三點中都至少有兩條連線，假定Ａ、Ｂ、Ｃ三點中至少有ＡＢ、ＢＣ兩條連線，如圖３．再考慮Ａ、Ｃ、Ｄ三點，這三點之間也應有兩條連線，不論是哪兩條線，不外乎下列三種情況之一：

（１）若ＡＤ、ＤＣ連線，如圖４，則可分配Ａ、Ｂ住一間，Ｃ、Ｄ住一間；

（２）若ＡＤ、ＡＣ連線，如圖５，則可分配Ａ、Ｄ住一間，Ｂ、Ｃ住一間；

（３）若ＡＣ、ＤＣ連線，圖６，則可分配Ａ、Ｂ住一間，Ｃ、Ｄ住一間．

無論出現(xiàn)哪一種情況，最后４人都可以安排他們住進兩個房間，使得每間房中的兩個人都能夠交談．