2014-07-09

拉姆齊數

拉拇齊理論是一個數學裡面的有趣的主題。我們已經知道拉拇齊數 R(3,3)=6, R(4,4)=18, 但之後更大的 R(n,n) 都還不知道。
數學家保羅·艾狄胥曾以一個譬喻來描述尋找拉姆齊數的難度:「想像有一群科技遠比我們進步的外星人軍隊在地球降落,他們要我們提供R(5,5)的值,否則便會毀滅地球。遇到這種狀況,我們應該集中全世界所有的超級電腦和數學家,去除歧見,齊心合作去找這個數值。但假如他們要的不是 R(5,5) 而是 R(6,6) 的話,我們應該要想辦法消滅這群外星人。」

拉拇齊數是什麼呢?假設有六個人聚會,他們彼此之間當然有時會握手。一個有趣的事實是,任一時刻,我們可以挑出三個人,他們要嘛彼此都曾握過手,要嘛彼此都未曾握過手。
顯然,如果聚會的人數超過六人時,一定也可以找到那樣的三個人(先隨便挑六個人出來,不要管其他人)。但如果只有五個人聚會,那就有可能找不出那樣的三個人。
上面的事實,我們稱之為拉拇齊數 R(3,3)=6。 同樣的道理,如果是 18 人聚會,就一定能找到四個人,要嘛彼此都曾握過手,要嘛彼此都未曾握過手(17 個人就未必如此)。這個事實可以表達為 R(4,4)=18。
那需要多少人才能保證一定能找出五個人,彼此都握過手或彼此都未曾握過手? 目前只知道這個數在 43 到 49 之間。
張貼留言