Perfect Villain

nagyon nagyon nagy szamok

pblue:

#fb ronald graham matematikus egyik munkajaban (1971ben) akkora szamot hasznalt, amelyrol martin gardner azt mondta hogy a legnagyobb szam valaha, amit komolyan veheto matematikai bizonyitasban hasznaltak barmire. ez amugy guinness rekord is.

graham munkaja egyebkent a kovetkezo problemarol szolt:

vegyunk egy n dimenzios kockat, es minden csucsot kossunk ossze mindegyikkel (ez 2 az n-ediken elt eredmenyez), majd szinezzuk ki az eleket pirossal vagy kekkel. melyik az a legkisebb ilyen n szam, amelyiknel tetszoleges szinezes mellett biztosan lesz olyan 4 csucsot tartalmazo sik metszet, amelyen a negy csucsot osszekoto elek mind egyszinuek?

a problema maga most egyaltalan nem fontos, hanem az, hogy bar a kerdesre a valaszt nem tudjuk, de grahamnek sikerult megadnia egy bizonyithato also es felso hatart is a megoldasra. az also hatar 6 (ez 2008ban 13ra pontosult). a felso hatar leirasahoz sajnos a mindennapokban hasznalt aritmetikai muveletek, mint osszeadas, szorzas, hatvanyozas, nem elegendok, ezert ujakkal kell megismerkedni.

de elobb azert a hatvanyokrol: az a nagyon nagy szam, amirol a google is kapta a nevet, a googol, 10 a 100adikon, azaz egy 1es es 100 darab nulla utana. hogy a szaz darab 0at erzekeltessem: a magyar allamadossag forintban, ami egy kibaszott nagy szam, kb 24 billio, lefele kerekitve 20 billio, egy 2es es 13 nulla utana. az ilyen irrealisan nagynak tuno szamok mint trillio, kvadrillio stb. is csak az 1 utani 18-24 nullas mezonyben mozognak. az 1 utani 100 darab nulla akkora szamot eredmenyez, ami nagyobb mint az osszes hidrogenatom szama a megfigyelheto univerzumban.

de a googolra ratesz egy lapattal a googolplex nevu szam, ami 10 a googol-adikon, azaz tiz a tiz a szazadikon (10^10¹⁰⁰). az 1 utan tobb nulla van mint ahany hidrogenatom osszesen a vilagegyetemben.

na de visszaterve az aritmetikai muveletekre. a szorzas ugye nem mas, mint hogy hanyszor adunk ossze egy szamot onmagaval. peldaul 3 * 4 = 3 + 3 + 3 + 3. ugyanilyen logika szerint mukodik a hatvanyozas is: 3⁴ = 3 * 3 * 3 * 3, azaz a 3 negyszer osszeszorozva. a hatvanyozasra hasznalhatunk egy masfajta jelolest is, ami az ugynevezett knuth-nyilazas: 3⁴ = 3 ↑ 4 (innen jon a ^ jeloles a hatvanyozasra a szamitogepeken). de ez a logika tovabbviheto a hatvanyozason tulra is. vezessuk be a 3 ↑↑ 4 jelolest, ami jelentse azt, hogy egy szamot hanyszor emelunk a sajat hatvanyara (ezt a muveletet amugy tetracionak hivjak): 3 ↑↑ 4 = 3 ↑ 3 ↑ 3 ↑ 3 = 3^{3^3³} = 3^{7 625 597 484 987} (3 a 7 billiodikon). tovabbmenve, hasznalhatjuk a 3 ↑↑↑ 4 jelolest is, ami egyenlo 3 ↑↑ 3 ↑↑ 3 ↑↑ 3, de ezt mar nem bontanam ki tovabb. ha maradunk a hatvanyozas hagyomanyos jelolesenel, akkor itt mar nem egy 3asokbol allo hatvanytoronyrol beszelunk, mint az elobbi tetracional, hanem 3asokbol allo tornyokbol allo toronyrol. a nyilak szamat tetszolegesen novelhetjuk, mindegyik uj nyil azt fogja jelenteni, hogy hanyszor alkalmazzuk az egyel kevesebb nyillal jelolt muveletet. az lathato, hogy ahogy no a nyilak szama, ugy eleg drasztikusan no az eredmeny is, de mar ket nyillal is es nagyon alacsony szamokkal egesz hamar le lehet hagyni a googol-t. peldaul 2 ↑↑ 5 = 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 = 2⁶⁵⁵³⁶ = 10¹⁹⁷²⁹ (nagyjabol!). a knuth-nyilazast vegul altalanosithatjuk ugy, hogy a ↑^m b, ahol m a nyilak szama.

egy fuggveny, mondjuk f(x) = 2 * x, alkalmazasa azt jelenti ugye, amikor x helyebe valami szamot helyettesitunk, peldaul ez esetben f(3) = 6 stb. egy fuggveny iteralt alkalmazasa pedig azt jelenti, amikor a fuggvenyt tobbszor alkalmazom sajat magara: peldaul f²(x) = f(f(x)), f³(x) = f(f(f(x))), es igy tovabb. maradva az elobbi fuggvenyunknel, f³(3) = f(f(f(3))) = 2 * (2 * (2 * 3)) = 24. de ne maradjunk ennel a fuggvenynel, hanem vezessuk be az f(x) = 3 ↑^x 3 fuggvenyt. peldaul f(8) = 3 ↑↑↑↑↑↑↑↑ 3.

a graham szam (G) meghatarozasahoz pedig hasznaljuk az uj fuggvenyunket: G = f⁶⁴(4).

ez a gyakorlatban azt jelenti, hogy a graham szamot 64 lepesben tudjuk kiszamitani. elso lepesben vesszuk 3 ↑↑↑↑ 3, ami onmagaban egy kiirhatatlanul nagy szam (lattuk az elobb, hogy mar 3 ↑↑↑ 4 is vagy 3 a 7 billiodikon, itt meg egyel tobb nyil van). ez a kiirhatatlanul nagy szam azt fogja megadni, hogy a kovetkezo lepesben a ket harmas kozott hany nyil lesz. annak az eredmenye pedig megadja hogy a kovetkezo lepesben hany nyil lesz a harmasok kozt. es igy tovabb, mindez 64szer. valojaban mar az elso lepesben, 3 ↑↑↑↑ 3 eredmenyekepp, is akkora szamot kapunk, hogy nincs az univerzumban eleg hely ahhoz se hogy kiirjuk, figyelembe veve hogy nem irhatunk tetszolegesen kicsi szamjegyeket, mert a lehetseges legkisebb meret, a planck-hossz ebben behatarol minket

jelenleg ez az ismert legnagyobb ertelmes szam - az utolso tiz szamjegye 2464195387. (amugy az eredeti problemara a valasz valoszinuleg kozelebb all a 13hoz, mint G-hez.)

tök jó ez a poszt és csak a 7²sorban vesztettem el a fonalat!!!