Aktuální číslo:

2025/7

Téma měsíce:

Umění

Obálka čísla

3,9995

 |  2. 5. 2023
 |  Vesmír 102, 247, 2023/5

Narozeninový problém je dosti známá úloha z kombinatoriky. Ve dvacátých letech minulého století ji obecně matematicky formuloval F. P. Ramsay (1903–1930). Pro nás může být nastíněn takto: Jaký je nejmenší počet hostů R(k), které chceme pozvat na večírek, abychom zaručili, že se mezi nimi vyskytne skupina k hostů, kteří se již předtím znali, nebo skupina k hostů, z níž se předtím nikdo s nikým neznal (pro jistotu dodávám v rámci té skupiny). Pro případ k = 3 nejmenší počet hostů, který to zajistí, je šest. To si můžete ověřit i bez matematiky hrubou silou tak, že si všechny možnosti jednu po druhé vypíšete. Obecně dosud úlohu nikdo nevyřešil. Geniální Paul Erdös našel spolu s G. Szekeresem v r. 1935 alespoň omezení shora, že totiž počet hostů 4k zaručuje, že se mezi nimi vyskytne skupina k hostů, kteří se již předtím znali, nebo skupina k hostů, z níž se předtím nikdo s nikým neznal. To nebylo moc uspokojivé, protože toto číslo je pro větší hodnoty k příliš veliké. A tak se nedivme, že po více než 90 letech neúspěšných pokusů o snížení Erdösovy horní hranice, vzbudila velkou pozornost práce čtyř matematiků, v níž snížili omezení shora na R(k) = 3,9995k. Jejich práce je dostupná na arxiv.org/abs/2303.09521. Rozdíl nám může připadat směšně malý, ale pro velká k je významný. Nejde o společenskou kuriozitu – práce má význam pro grafy s prvky náhodnosti, které mají aplikace v reálných problémech.

P. Ball: Nature, 2023, DOI: 10.1038/d41586-023-00840-5

Ke stažení

OBORY A KLÍČOVÁ SLOVA: Matematika
RUBRIKA: Mozaika

O autorovi

Ivan Boháček

Mgr. Ivan Boháček (*1946) absolvoval Matematicko-fyzikální fakultu UK v Praze. Do roku 1977 se zabýval v Ústavu fyzikální chemie J. Heyrovského molekulovou spektroskopií, do roku 1985 detektory ionizujících částic v pevné fázi v Ústavu pro výzkum, výrobu a využití radioizotopů. Spolu s Z. Pincem a F. Běhounkem je autorem knihy o fyzice a fyzicích Newton by se divil (Albatros, Praha 1975), a se Z. Pincem pak napsali ještě knihu o chemii Elixíry života a smrti (Albatros, Praha 1976). Ve Vesmíru působí od r. 1985.
Boháček Ivan

Doporučujeme

Věstonická superstar

Věstonická superstar video

Soška tělnaté ženy z ústředního tábořiště lovců mamutů u dnešních Dolních Věstonic pod Pálavou je jistě nejznámějším archeologickým nálezem...
K čemu je umění?

K čemu je umění? uzamčeno

Petr Tureček  |  7. 7. 2025
Výstižná teorie lidské evoluce by měla nabídnout vysvětlení, proč trávíme tolik času zdánlivě zbytečnými činnostmi. Proč, jako například lvi,...
Paradoxní příběh paradoxu obezity

Paradoxní příběh paradoxu obezity uzamčeno

Petr Sucharda  |  7. 7. 2025
Obezita představuje jednu z nejzávažnějších civilizačních chorob, jejíž důsledky zasahují do téměř všech oblastí lidského zdraví. Její definice...