Кіріспе
6 адамнан тұратын кез келген топта, кем дегенде 3 адам бір-бірімен таныс емес немесе кем дегенде 3 адам таныс болады. Пауль Эрдос, Альфред Реньи және Вера Т. Состың достық теоремасы, әр екі төбесінің дәл бір көршісі болатын графтарды сипаттайды. Достар мен бейтаныстар туралы теорема – математиканың Рамзи теориясы саласындағы математикалық теорема.
The theorem on friends and strangers is a mathematical theorem in an area of mathematics called Ramsey theory.
Айтылым
Бір партияда алты адам болса дейік. Олардың кез келген екеуін қарастырайық. Егер олар бірінші рет кездесіп жатса, онда оларды өзара бейтаныс деп атаймыз; әйтпесе, бұрын таныс болған жағдайда, оларды өзара таныс деп атаймыз. Теорема мынадай: алты адамнан тұратын кез келген топта кем дегенде үшеуі (екеу-екенімен) өзара бейтаныс немесе өзара таныс болады.
In any party of six people, at least three of them are (pairwise) mutual strangers or mutual acquaintances.
Графтық теориялық орнатуға көшіру
Теореманы дәлелдеу үшін үш қадамдық логикадан басқа ештеңе қажет емес. Мәселені графтар теориясының тілінде түйіндеу ыңғайлы. Графтың 6 төбесі болсын және әрбір (әр түрлі) төбе жұбы қабырғамен қосылсын. Мұндай граф толық граф деп аталады (өйткені одан артық қабырғалар болуы мүмкін емес). n төбесі бар толық граф белгілі бір символмен белгіленеді. Енді K₆-ны қарастырайық. Оның барлығы 15 қабырғасы бар. 6 төбе біздің топтағы 6 адамды білдірсін. Қабырғалар қызыл немесе көк түспен боялады, бұл қабырғамен байланысқан төбелердегі екі адамның бір-бірімен таныс еместігіне немесе өзара таныстығына байланысты. Теорема былай деп тұжырымдайды:
Now take a It has 15 edges in all. Let the 6 vertices stand for the 6 people in our party. Let the edges be coloured red or blue depending on whether the two people represented by the vertices connected by the edge are mutual strangers or mutual acquaintances, respectively. The theorem now asserts:
Қызыл және көк түстермен K₆ графының 15 қабырғасын қалай боясаңыз да, қызыл үшбұрыштан – яғни үш қабырғасы да қызыл үшбұрыштан, үш жұп өзара таныс емес адамды білдіретін – немесе көк үшбұрыштан, үш жұп өзара таныс адамды білдіретін, қашқанға болмайды. Басқаша айтқанда, қандай түс қолдансаңыз да, әрқашан кем дегенде бір монохроматикалық үшбұрыш (яғни барлық қабырғалары бір түсті үшбұрыш) болады.
Дәлел
Кез келген төбе таңдаңыз; оны P деп атаңыз. P-ден бес қабырға шығады. Олардың әрқайсысы қызыл немесе көк түспен боялған. Көгершін ұясы принципі бойынша, олардың кем дегенде үшеуі бір түсті болуы керек; егер бір түстің, мысалы қызылдың, үшеуі болмаса, онда кем дегенде үшеуі көк болуы керек. А, В, С осы үш қабырғаның екінші ұштары болсын, барлығы бір түспен, көк болсын. Егер AB, BC, CA-ның кез келгені көк болса, онда бұл қабырға P-ден оның ұштарына дейінгі екі қабырғамен бірге көк үшбұрыш құрайды. Егер AB, BC, CA-ның ешқайсысы көк болмаса, онда барлық үш қабырға қызыл болады және бізде қызыл үшбұрыш, атап айтқанда ABC үшбұрышы болады.
Рамзидің газеті
Бұл аргументтің толыққанды қарапайымдылығы, өте қызықты нәтижеге күшті әсер ететіндіктен, теореманы тартымды етеді. 1930 жылы «Формалды логиканың бір мәселесі» деген мақаласында Фрэнк П. Рамзи өте жалпы теореманы (қазір Рамзи теоремасы деп белгілі) дәлелдеді, ал осы теорема соның қарапайым мысалы болып табылады. Рамзидің бұл теоремасы комбинаторикадағы Рамзи теориясы деп аталатын саланың негізін қалайды.
Теореманың шекаралары
Теореманың қорытындысы, егер алты адамнан тұратын топты алтыдан кем адамнан тұратын топқа алмастырсақ, орындалмайды. Мұны көрсету үшін, біз K5-ті қызыл және көк түстермен бояймыз, онда барлық қабырғалары бір түсті үшбұрыш болмайды. K5-ті жұлдызды (пентаграмманы) айналдыра орналасқан бесбұрыш түрінде саладық. Бесбұрыштың қабырғаларын қызыл, ал жұлдыздың қабырғаларын көк түспен бояймыз. Осылайша, 6 – теореманың қорытындысын тұжырымдай алатын ең кіші сан. Рамзи теориясында бұл факт былай жазылады: