Graham-szám

A Wikipédiából, a szabad enciklopédiából

A Graham-szám, amely Ronald Graham amerikai matematikusról kapta nevét, arról nevezetes, hogy valószínűleg a legnagyobb olyan szám, ami matematikai bizonyításban valaha is előfordult. Jóval nagyobb annál, hogy a szokásosan használt tízes számrendszerben – akár még normálalak használatával is – le lehessen írni, így lejegyzéséhez, definiálásához külön jelölésrendszerre van szükség. Ennek ellenére elemi számelméleti módszerekkel tetszőlegesen sok számjegye kiszámítható (igaz, „hátulról”, a kisebbektől a nagyobb helyiértékek felé haladva). Graham számának utolsó 10 számjegye …2464195387.

A Graham-probléma[szerkesztés | forrásszöveg szerkesztése]

A Graham-szám a következő probléma megoldásakor merült fel, mely probléma egyébként a kombinatorikai, pontosabban diszkrét matematikai jellegű, Ramsey-elméletnek nevezett terület körébe tartozik:

Képzeljünk el egy n-dimenziós hiperkockát, és kössük össze minden csúcspárját, hogy egy 2^n csúcsú teljes gráfot kapjunk. Ezt követően színezzük ki e gráfnak minden élét csupán két színnel (például pirossal és kékkel). Mi n legkisebb olyan értéke (azaz legalább hány dimenziós kell legyen a hiperkocka), amelyiknél minden ilyen színezés szükségképpen tartalmaz egy olyan teljes részgráfot, mely egyszínű (tehát minden éle piros, vagy minden éle kék), és még 4, egy síkban fekvő csúcsa is van?

Habár a probléma megoldása még várat magára, de az bizonyított, hogy a Graham-szám olyan szám, melynél a fenti n érték biztosan kisebb kell hogy legyen, és ennél jobb felső becslést n-re még nem találtak.

Az 1989-es, Penrose Tiles to Trapdoor Ciphers című könyvében (ISBN 0-88385-521-6) Martin Gardner azt írta, hogy „A Ramsey-elmélet szakértőinek véleménye szerint a tényleges Ramsey-szám erre a problémára valószínűleg 6”, s ebből az következik, hogy a Graham-szám feltehetően a legrosszabb felső becslés, amit valaha is egy ismeretlen mennyiség értékének nagyságára tettek. 2003-ban az Indianai Állami Egyetem munkatársa, Geoff Exoo bizonyította, hogy a 6 rossz alsó becslés, ugyanis a keresett szám nagyobb, mint 11.[forrás?]

Úgy tartják, hogy a Graham-szám a legnagyobb olyan szám, amit a gyakorlatban valaha is alkalmaztak. Nagyobb a Moser-számnál is (ez szintén egy óriási szám).

A Graham-szám definíciója[szerkesztés | forrásszöveg szerkesztése]

Graham száma a 65. az alábbi sorozatban, ahol minden tag a következőhöz szükséges Knuth-nyilak száma:

4,\ 3\uparrow\uparrow\uparrow\uparrow3,\ 3\uparrow\cdots\uparrow3,\ 3\uparrow\cdots\uparrow3,\ \ldots

Ennek megfelelően határozzuk meg az f(n) = hyper(3,n+2,3) = 3→3→n függvényt, majd a függvényhatványok segítségével adódik G=f64(4).

Magát G-t, a Graham-számot nem lehet a Conway-féle láncoltnyíl-jelöléssel tömören kifejezni, de  3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2 , lásd a Graham-számra vonatkozó részeket a Conway-féle láncoltnyíl-művelet c. szócikkben.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]