Изчисляването на числата на Рамзи е толкова трудно, че един математик веднъж казва, че предпочита да се бори с нашествие на извънземни. Сега математиците са постигнали първия голям напредък от близо век насам.
През 1928 г. Франк Рамзи се бори с проблем в математическата логика. Струва му се, че за да го реши, трябва да покаже, че математическите системи, които изучава, винаги имат определен ред. На пръв поглед системите можели да бъдат колкото си искат хаотични, но Рамзи смятал, че дори и в най-непокорните, самият размер на системата би трябвало да принуди части от нея да проявяват някакъв ред.
Доказвайки, че интуицията му е вярна, той изобретява нов клон на математиката, който сега е известен като теория на Рамзи. Той прочита статията си пред Лондонското математическо общество, но умира на 26-годишна възраст, преди тя да бъде публикувана в неговия сборник.
Теорията на Рамзи все още намира приложение в областта на логиката. Но тя е и много привлекателна тема сама по себе си, тъй като основните ѝ идеи могат да бъдат разбрани много лесно и включват рисуване на цветни картинки. От друга страна, тя е и активна изследователска област, тъй като повдига някои впечатляващо трудни въпроси. Когато през 1998 г. беше обявен последният кръг от Фийлдсовите медали - Фийлдс е най-престижната награда в математиката, най-близкият еквивалент на Нобеловата награда - един от тях отиде при британския математик Тим Гауърс, отчасти за работата му в областта на теорията на Рамзи. В тази статия ще видим, че теорията на Рамзи има способността да задава дори много прости на вид въпроси, които досега са се изплъзвали на всички опити да им се отговори.
Ред от хаоса
Фундаменталният въпрос, който теорията на Рамзи задава, е: може ли винаги да се намери ред в хаоса? Ако е така, колко? Колко голямо парче от хаоса ни е необходимо, за да сме сигурни, че в него ще открием определено количество ред? Тук, когато говорим за "хаос" в тази статия, имаме предвид просто нещо разхвърляно или разбъркано - няма връзка с техническото значение на "хаос" в математиката, което е свързано с динамичните системи.
Това звучи като странен въпрос, ето един конкретен пример. Да предположим, че има стая с шест души в нея. Интересува ни дали хората в тази стая се познават или не. Нека наречем двама души приятели, ако се познават, и непознати, ако не се познават.
Търсим примери за подреденост и очевидно най-подреденият случай би бил, ако шестимата са или всички приятели, или всички непознати. За съжаление хората са избрани на случаен принцип, така че в стаята вероятно ще има смесица от приятели и непознати. Да предположим, че начертаем линии, свързващи всяка двойка хора в стаята, и ги оцветим в синьо, ако двамата са приятели, и в червено, ако са непознати. Тогава резултатът може да изглежда по следния начин:
 |
Тази картина - математиците я наричат граф - изглежда напълно хаотична. Със сигурност нямаме шестима приятели или шест непознати. Но все пак можем да попитаме: можем ли да намерим поне трима души в стаята, които са или приятели, или непознати? Казано по друг начин, можем ли да намерим син триъгълник (трима приятели) или червен триъгълник (трима непознати)?
В този случай отговорът е "да". Чарли, Евелин и Фред са непознати един за друг. Но какво ще стане, ако оригиналният граф е бил различен? Винаги ли щяхме да можем да намерим подреден набор от трима души, дадени от монохроматичен триъгълник (всички в един цвят, от гръцки monos, „единичен“, и chroma , „цвят“)?
Експериментирането с малко хартия и цветни моливи скоро ще ви убеди, че с шест души винаги има едноцветен триъгълник. Но как да докажем, че това е вярно? Един от начините би бил просто да изброим всички възможни оцветявания и да проверим всеки от тях. За съжаление има над 30 000 възможни оцветявания, така че това доказателство би било повече от досадно.
За щастие се оказва, че можем да го докажем много по-лесно. Първо избираме която и да е точка, от нея излизат пет линии - по една към всяка от останалите пет точки:
 |
При пет линии трябва да има поне три от един цвят - поне три червени линии или поне три сини линии. Да предположим, че има три червени линии (ако вместо тях имаше три сини линии, аргументът щеше да е абсолютно същият, но с разменени „червено“ и „синьо“). Така че имаме четири точки като тази:
 |
Какви са цветовете на останалите три линии? Е, ако дори един от тях е червен, тогава той прави червен триъгълник заедно с точка А (вляво). И ако не, трите заедно правят син триъгълник (вдясно):
 |
 |
Така или иначе имаме нашия монохроматичен триъгълник.
Достатъчни ли са 5 точки?
Доказахме, че при шест точки (или повече, разбира се), винаги трябва да има едноцветен триъгълник - с други думи, че при шест или повече души трябва да има трима приятели или трима непознати.
Това предполага въпроса „Колко души ни трябват, за да сме сигурни, че ще намерим или трима приятели, или трима непознати?“ Това е първият ни пример за число на Рамзи и се записва като R (3,3). Видяхме, че шестима души със сигурност са достатъчни. С други думи, R (3,3) не е по-голямо от 6. Но дали пет точки биха били достатъчни - с други думи, така ли е, че всяка група от петима души ще има или трима приятели, или трима непознати? Графът по-долу с пет точки показва, че отговорът е не, тъй като няма монохроматичен триъгълник:
 |
Това показва, че R(3,3) не може да бъде по-малко от 6. Ако вземем тези два резултата заедно, доказваме, че R(3,3)=6.
В търсене на повече ред
Сега, след като разбрахме какво е число на Рамзи, можем да се опитаме да намерим други примери. Например, R(5,5) ще ни каже колко души са необходими, за да сме сигурни, че ще намерим или петима общи приятели, или петима общи непознати. Разбира се, все още не знаем, че винаги има такъв отговор: може би нито едно количество хора няма да гарантира, да речем, 10 приятели или 10 непознати. (Всъщност по-нататък в тази статия ще докажем, че винаги има отговор, макар че обикновено не знаем какъв е той.)
За да се уверим, че сме разбрали дотук, да разгледаме следните два въпроса:
- Какво е R (2,5)?
- Ако знаем R (a, b), какво можем да кажем за R (b, a)?
Ето разсъжденията:
1. Числото на Рамзи R(2,5)
Това е числото, което ще отговори на въпроса: "Колко души са ни необходими, за да сме сигурни, че ще имаме или двама приятели, или петима непознати?"
Но, разбира се, ако в стаята има някакви двама души, които се познават, това ни дава нашите двама приятели. От друга страна, ако не са, тогава всички хора в стаята са взаимно непознати. Така че щом има петима души, трябва да има или двама приятели, или петима непознати.
Накратко, R(2,5)=5. Разбира се, същото разсъждение би работило и с друго число вместо 5, така че по-общо можем да кажем, че R(2,a)=a, за всяко число a.
2.Връзката между R(a,b) и R(b,a)
От математическа гледна точка няма нищо специално в думите "приятели" или "непознати" - или, погледнато по друг начин, в цветовете "синьо" и "червено". Когато имате граф със сини и червени линии, можете да ги размените, така че червените да станат сини и обратно.
Следователно, ако една група от хора е достатъчно голяма, за да съдържа или a общи приятели, или b общи непознати, трябва да е също толкова вярно, че тя съдържа или a непознати, или b приятели. С други думи, R(a,b)=R(b,a). Математикът би казал, че функцията R е симетрична.
Сега нека бъдем по-амбициозни: искаме да намерим четирима души, които са или всички приятели, или всички непознати. Искаме да намерим R(4,4). За момента обаче това е твърде трудно, затова ще се задоволим с нещо малко по-лесно, а именно намирането на R(3,4).
Намиране на R (3,4)
Колко точки са ни необходими, за да гарантираме, че можем да намерим или три точки, всички свързани със сини линии, или четири точки, всички свързани с червени линии - с други думи, едно от следните?
 |
 |
Първо, твърдим, че 10 точки със сигурност са достатъчни. Нека се опитаме да докажем това. Да предположим, че имаме 10 точки, съединени с червени и сини линии по обичайния начин. Изберете точка и забележете, че от нея излизат 9 линии.
 |
Трябва или да има поне 6 червени, или поне 4 сини (в противен случай няма да има общо 10) Така че сме в една от тези две възможности (начертани са само линиите, които ни интересуват ):
Случай (i) |
Случай (ii) |
Нека първо разгледаме случай (i). Какъв цвят са линиите в (i), различни от показаните сини? Ако дори един от тях е син, имаме син триъгълник, с други думи трима приятели (вляво); ако не, всички са червени и имаме четирима непознати (вдясно). И в двата случая сме готови:
 |
 |
Сега нека да разгледаме случай (ii). Там има 6 точки (освен А). И вече открихме, че R (3,3)=6, така че от тези 6 точки 3 трябва да образуват или син триъгълник, или червен триъгълник, което ни поставя в един от тези два случая:
 |
 |
В случая отляво имаме трима приятели, а в случая отдясно четирима непознати. Така че още веднъж сме готови.
Този аргумент е поставил граница на R (3,4): знаем, че съществува и не може да бъде повече от 10. Но все пак може да бъде по-малко от 10. Всъщност, чрез една вариация на аргумента по-горе, можем да покажем че 9 точки ще свършат работа.
Девет точки са достатъчни
За да покажем, че дори при само девет точки трябва да има или син триъгълник, или четири точки, свързани с червени линии, се нуждаем от леко подобрение на разсъжденията, които използвахме за 10 точки.
При 10 точки доказателството се основаваше на намирането на точка, свързана или с поне шест червени линии, или с поне четири сини. След като разполагахме с такава точка, можехме да сме сигурни, че ще намерим нашите трима приятели или четирима непознати. И всъщност, като преброихме линиите, които се срещат в дадена точка, видяхме, че всяка точка е подходяща.
Ако графът има само 9 точки, всеки от тях има само 8 съседи. Как може нашата теорема да се провали? Само ако всяка точка има точно пет червени линии и три сини. Това означава, че всяка точка трябва да изглежда по следния начин:
 |
Колко сини линии би имала този граф? Е, всяка линия има два края, а във всяка от 9-те точки се срещат по три сини линии. Така че общият брой на сините линии е (9×3)/2, което е 13,5. Това е невъзможно - разбира се, че в графа трябва да има цял брой сини линии.
Така че в крайна сметка трябва да има поне една точка, свързана или с четири сини линии, или с шест червени линии, и сега същият аргумент като преди показва, че трябва да има трима приятели (син триъгълник) или четирима непознати.
Осем точки не са достатъчни
От друга страна, 8 точки няма да са достатъчни, както показва следната диаграма. (Всички сини линии са показани; всички останали линии се приемат за червени.) Никакви 3 точки не образуват син триъгълник и никакви 4 точки не са свързани с червени линии.
 |
Сега знаем, че R (3,4)=9. Освен това, както видяхме по-рано, можем да разменим местата на "червено" и "синьо", така че същият аргумент показва, че R (4,3)=9.
Намиране на R (4,4)
Сега можем да използваме това знание, за да намерим R (4,4). Първо, твърдим, че 18 души са достатъчни, за да гарантираме или четирима приятели, или четирима непознати. Методът на доказване вече би трябвало да започне да изглежда познат. Да кажем, че имаме граф с 18 точки и линии между тях, оцветени в синьо или червено. Да вземем една точка. От нея излизат 17 ребра, така че поне 9 от тях трябва да са едноцветни - червени, да речем:
 |
Вече знаем, че R (4,3)=9, така че сред тези 9 точки трябва да има или четирима приятели - в който случай сме готови - или трима непознати. В последния случай, тъй като и трите са непознати за A , имаме четири непознати, включително A. Така че имаме или четирима приятели, или четирима непознати, което е точно това, което твърдехме.
Още веднъж открихме граница: R (4,4) със сигурност съществува и е най-много 18. Този път, за късмет, границата се оказва най-добрата възможна: 17 точки не са достатъчни, за да гарантират монохроматичен набор от четири точки. За да покажем това, трябва да намерим граф със 17 точки без такъв монохроматичен набор. Това е направено и може да go видите на отделна страница.
В резултат знаем, че R (4,4)=18.
По-големи числа на Рамзи
Последната стъпка показа, че можем да поставим граница на R (4,4), стига да имаме граници за R (3,4) и R (4,3). Те също се разделят на по-прости стъпки: можем да обвържем R (3,4), стига да можем да обвържем R (3,3) и R (2,4) и т.н. Mатематически казано R (a, b) съществува, стига да съществуват R (a-1, b) и R (a, b-1).
Също така вече видяхме, че R (a ,2) и R (2, a) винаги съществуват (те просто са равни на a). Така че, за да покажем, че например R (5,5) съществува, ще се разделим на поредица от стъпки, както е на диаграмата:
 |
Всеки случай се разделя на двата случая под него и ние вече направихме случаите в долния ред. Така че R (5,5) със сигурност съществува и по подобен начин за R (6,6) или всяко R (a,b). Това е теоремата на Рамзи и тя ни казва, че винаги можем да намерим подреденост, стига даденият графът да е достатъчно голям.
Важно е обаче да се запомние, че този метод не намира точните числа на Рамзи вместо нас, въпреки че ни позволява да намираме граници.
Никой не знае
И така, каква е истинската стойност на R (5,5)?
Отговорът е: никой не знае!
Всъщност много малко числа на Рамзи R (a, b) са известни (като a и b са по-големи от 2). Вече видяхме, че R (3,3)=6, R (4,3)=9 и R (4,4)=18. Освен това са известни само още три стойности: R (5,3)=14, R (6,3)=18 и R (7,3)=23. Най-многото, което можем да кажем за R (5,5) с настоящите ни познания е, че е някъде между 42 и 55.
Защо е толкова трудно да се получи точна стойност? Аргументи като тези, използвани в тази статия, ни позволяват да намерим горни граници на числата на Рамзи, които ни интересуват - например, видяхме доста лесно, че R (4,3) не може да бъде по-голямо от 10.
Но за да покажем, че то не може да бъде по-малко от 8, трябваше да построим изрично граф с 8 точки като контрапример. Проблемът е, че ние търсим примери за порядък, така че най-добрите контрапримери обикновено имат много безпорядък - те изглеждат случайни. Това затруднява или прави невъзможно намирането на "правило", което да дава добри контрапримери. Всяко нещо, конструирано по правило, вероятно ще има твърде много ред в него.
Освен това горните ни граници може да са твърде високи, но как ще го докажем? Може би като разгледаме всички възможности на компютър? Но един прост пример ще покаже, че това никога няма да се получи. Да кажем, че искаме да покажем, че R(5,5) е най-много 54 - с други думи, да покажем, че 54 точки винаги ще гарантират съществуването на 5 точки, всички свързани помежду си с линии с един цвят. Ще трябва да разгледаме всички възможни начини за оцветяване на линиите между 54 точки в червено или синьо.
Колко начина има? Първо трябва да знаем броя на линиите, който по добре познатата формула е
(54 × 53) / 2 = 1431.
Всяка линия може да бъде оцветена в червено или синьо, така че броят на възможните оцветявания е такъв
2 × 2 × 2 × ... × 2,
където броят на 2-ките, умножени заедно, е 1431 - в математически запис това е 2 1431 или над 10 400. Това число е много, много по-голямо от броя на частиците в познатата Вселена (около 10 80 ). Така че няма никакъв шанс дори и най-бързият възможен компютър да завърши такова търсене. Това е загадка, чийто отговор може би никога няма да узнаем.
Последни постижения
Пол Ердьош (Paul Erdős), който през 1935 г. установява, че горната граница за всяко число на Рамзи е 4 на степента на размера на кликата, веднъж казва, че намирането на точното число на Рамзи за клика от шест души е толкова трудно, че ако извънземните поискат да се опитаме да го изчислим или да бъдем унищожени, няма да имаме друг избор, освен да се опитаме да ги атакуваме първи. Оттогава насам поколения математици са се опитвали да подобрят значително границата на Ердьош, но без особен успех.
Сега Джулиън Сахасрабуде (Julian Sahasrabudhe) от Университета в Кеймбридж и неговите колеги показват, че горната граница за числата на Рамзи може да бъде намалена от 4 на степента на размера на кликата до 3.993 на степента на размера на кликата.
"Отстрани изглежда някак глупаво - като че ли, добре, математиците просто се опитват да подобрят някакво число и на кого му пука?", коментира Сахасрабуде. "Но това, което е интересно в тези количествени промени, като разликата между границата на Ердьош и предишните граници и нашата работа, е, че наистина има някакво количествено подобрение, което отразява задълбочаването на нашето разбиране за [математическите] структури."
Сахасрабуде и колегите му започват да работят по проблема за първи път през 2018 г. в Националния институт за чиста и приложна математика в Рио де Жанейро, Бразилия.
"Това е известен проблем и ние имахме някои идеи - и изглеждаше, че всъщност върви доста добре, което беше вълнуващо", разказва Сахасрабуде.
През първите няколко месеца екипът е начертал груб план за това как би могло да изглежда доказателството, обяснява Сахасрабуде, но бързо се е сблъскал с препятствие, което е включвало изчисляване на това как точките се струпват една до друга върху сфери от високи измерения.
След като години наред се опитват да решат този проблем и не успяват, Сахасрабуде и екипът му разбират, че могат да преформулират доказателството си, за да избегнат изцяло въпроса със сферите, след което нещата бързо напредват. "Вместо да прекосим планината, разбрахме, че всъщност можем някак да я заобиколим", разказва Сахасрабуде.
Окончателното доказателство, което е дълго повече от 50 страници и предстои да бъде официално проверено, използва елементи от оригиналното доказателство на Ердьош, което включва увеличаване на конкретни хора в произволно големи партита и определяне на вероятностите за връзките им с техните съседи, а също и идентифициране на съседни структури на клики, наречени "книги" (“books”), които са по-лесни за намиране, но гарантират, че клики съществуват.
"Поне през последните 50 години всеки изтъкнат математик в моята област се е опитвал доста усилено да подобри тези граници и не е успял", отбелязва Дейвид Конлон (David Conlon) от Калифорнийския технологичен институт. "Фактът, че сега те са подобрили този резултат, е много важен."
Сега, след като бариерата от 4 е преодоляна, други изследователи могат да използват и оптимизират методите на Сахасрабудхе и неговия екип, за да получат число, малко по-ниско от 3,993.
"Това е дяволски труден проблем", коментира Питър Камерън (Peter Cameron) от Университета "Сейнт Андрюс", Великобритания. "Малко подобрение като това представлява огромен пробив в техниките за решаването му."
Справка: Курсова работа по Числа на Ремзи, СУ „Св. Климент Охридски”
Източници:
Friends and strangers, Plus Magazine, University of Cambridge, Imre Leader
Авторът Имре Лидер е сътрудник на колежа Тринити в Кеймбридж и преподавател в катедрата по чиста математика и математическа статистика на университета в Кеймбридж.
Breakthrough in fiendishly hard puzzle has mathematicians partying, New Scientist
Коментари
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!
Няма коментари към тази новина !
Последни коментари