Grahamovo číslo

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Grahamovo číslo, pojmenované po Ronaldu Grahamovi, je velké číslo, které je horní hranicí řešení určitého problému v Ramseyově větě.

Číslo získalo velkou popularitu, když ho Martin Gardner popsal v sekci "Mathematical Games" magazínu Scientific American v listopadu 1977, popisující, "V nepublikovaném důkazu Graham nedávno ustanovil ... hranici tak rozsáhlou, že drží rekord za největší číslo, které bylo kdy použito v matematickém důkazu. " Guinnessova kniha rekordů z roku 1980 zopakovala Gardenerovo prohlášení, což přidalo na popularitě tohoto čísla.[1]

Grahamovo číslo je nepředstavitelně větší než ostatní známá velká čísla jako Googol, googolplex, a dokonce větší než Skewesovo číslo a Moserovo číslo. Ve skutečnosti je pozorovatelný vesmír příliš malý, aby obsahoval běžnou digitální reprezentaci Grahamova čísla, za předpokladu, že každé číslo okupuje alespoň jednu planckovu délku krychlovou. Dokonce umocňování ve formě je nepoužitelné pro tento záměr. Pro definici Grahamova čísla je nutno použít rekurzivní Knuthův zápis.

Posledních 10 číslic Grahamova čísla je ... 2464195387.

Specifická celá čísla považovaná za daleko větší než Grahamové číslo se od té doby objevila v množství seriózních matematických důkazech (např. ve spojitosti s Friedmanovými různými konečnými formami Kruskalova algoritmu).

Souvislost s Ramseyovo teorií[editovat | editovat zdroj]

Příklad 2-barevné 3rozměrné kostky obsahující jeden jednobarevný 4-vrcholový komplanární soubor podgrafu. Tento podgraf je zobrazen pod kostkou. Tato kostka by ale neobsahovala žádný podgraf, pokud by například spodní hrana v tomto podgrafu byla vyměněna za modrou hranu - což by prokázalo, že N*> 3.

Grahamovo číslo je spojeno s tímto problémem v Ramseyově větě: vezměte v úvahu n-dimenzionální nadkrychli a spojte každý pár vrcholů, abyste získali kompletní graf 2n vrcholů. Pak vybarvěte každou z hran tohoto grafu buď modře, nebo červeně. Jaká je nejmenší hodnota n, pro kterou každé takové vybarvení obsahuje alespoň 1 jednobarevný kompletní podgraf 4 koplanárních vrcholů?

V roce 1971 Graham a Rothschild dokázali, že tento problém má řešení, N *, a dali mu ohraničení 6 ≤ N * ≤ N, kde N je definováno výlučně jako velmi velké číslo. Spodní hranice 6 byla později zdokonalena na 11 Geoffem Exooomem v roce 2003 a na 13 Jerome Barkleyomem v roce 2008. Tedy, nejznámější hranice pro N * jsou 13 ≤ N * ≤ N.

Grahamovo číslo, G, je mnohem větší než N. Tato horní hranice byla nakonec publikována a pojmenována Martinem Gardnerem v Scientific American v listopadu 1977.

Vysvětlení velikosti Grahamova čísla[editovat | editovat zdroj]

Pro definici Grahamova čísla je nutno použít Knuthův zápis. Nejprve definujeme g1 jako 3 ↑↑↑↑ 3 = 3↑43. Dále definujeme

gn=3↑g(n-1)3

Tedy:

g2 = 3 ↑g(1)3 = 3↑3↑↑↑↑33

g3 = 3 ↑g(2)3

...

g64 = 3 ↑g(63) 3 = Grahamovo číslo

Již g1 je větší než jakékoliv číslo rozumně zapsatelné ve formě mocninové věže . Vzhledem k tomu, že gn se v iteraci gn+1 používá jako počet šipek, roste funkce gx nepředstavitelně rychle.

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Grahamovo číslo na slovenské Wikipedii.

  1. From 1,000,000 to Graham's Number. Wait But Why [online]. 2014-11-20 [cit. 2017-02-24]. Dostupné online.