Ramseyho problém: Poznáme výsledok matematického príkladu, ktorý vedci nedokázali rozlúsknuť takmer 100 rokov
Výskumníci z University of California, San Diego publikovali riešenie na jeden z najťažších Ramseyho problémov.
Výskumníci z University of California, San Diego objavili riešenie na matematický problém, s ktorým si vedci nevedeli dať rady takmer sto rokov.
Ide o takzvané Ramseyho problémy, ktoré sa formulujú veľmi jednoducho, no možných riešení je takmer nekonečné množstvo, čo z toho robí ťažko riešiteľný problém. Zo všetkých Ramseyho problémov však vynikal jeden, ktorý vedcom nedal spať takmer jedno storočie. Ide o príklad r(4,t), na ktorý konečne poznáme odpoveď.
V matematickom svete sa graf nazýva séria bodov a línií medzi týmito bodmi. Podľa Ramseyho teórie by malo platiť, že ak je graf dostatočne veľký, takmer určite v ňom nájdete nejaký poriadok. Pod poriadkom si môžeme predstaviť napríklad body, ktoré nie sú prepojené líniami alebo body, ktoré majú všetky možné línie medzi nimi. To sa zapisuje ako r(s,t), pričom písmeno s vyjadruje body s líniami a t predstavuje body bez línie.
Najznámejším príkladom je r(3,3). Ak by sme mali tento graf predstaviť na reálnom príklade, predstavte si párty, na ktorej je šesť ľudí. Teória hovorí, že nájdeme najmenej troch ľudí, ktorí sa navzájom poznajú alebo troch ľudí, ktorí sa navzájom nepoznajú. Riešenie príkladu r(3,3) je šesť.
“Je to prírodný fakt, absolútna pravda. Nezávisí na situácii alebo ľuďoch. Ak vezmete šiestich ľudí, nájdete troch ľudí, ktorí sa navzájom poznajú alebo troch ľudí, ktorí sa navzájom nepoznajú. Môžete nájsť viacerých, no je garantované, že to budú najmenej traja ľudia,” vysvetľuje Jacques Verstraete, jeden z autorov štúdie.
Odpoveď na takmer storočný problém
Vedci zistili riešenie na r(3,3) a potom chceli vedieť riešenia na r(4,4), r(5,5) a r(4,t). Pri poslednom príklade sa môže počet neprepojených bodov meniť. Zaujímavosťou je, že odpoveď na r(5,5) zatiaľ nepoznáme. Príklad r(4,4) má odpoveď 18.
Neprehliadnite
Prečo sa to nedá tak ľahko vyriešiť? Ak by vedci chceli nájsť odpoveď na r(5,5) a vedeli by, že odpoveď leží niekde medzi 40 a 50, povedzme 45, potom by museli zvážiť nepredstaviteľné množstvo grafov, až 10 na 234.
Čo sa týka príkladu r(4,t), ide o problém, ktorý nemal riešenie už viac ako 90 rokov. Na riešenie tohto prekvapivo náročného problému výskumníci čerpali aj z oblastí mimo kombinatoriky. Požičiavali si postupy z geometrie, pravdepodobnosti a algebry. Nakoniec sa ale dokázali dopracovať k odpovedi. Ako teda znie?
Povedzme že chcete usporiadať párty, na ktorej budú vždy štyria ľudia, ktorí sa poznajú a neurčité množstvo ľudí, ktorí sa medzi sebou nepoznajú. Na usporiadanie takejto párty potrebujete tretiu mocninu z ľudí, ktorí sa navzájom nepoznajú.
Odpoveď na príklad r(4,t) teda znie t³. Autori štúdie vysvetľujú, že nejde o presnú odpoveď, no tento výsledok je veľmi blízko k presnej odpovedi.
Komentáre