El número de Graham

En una antigua entrada de este blog hablábamos de ¿Cuál es el número más grande que puedes imaginar? En él se mencionaron el gogol, el número de Safford y el número de Leviatán, entre otros, pero se nos quedó en el tintero un número mucho más grande que todos ellos y que, además, no es una invención, sino que es empleado en varias demostraciones matemáticas.

El número de Graham, que recibe su nombre del matemático Ronald Graham, es una cota superior de la solución de un determinado problema en la teoría de Ramsey, concretamente el siguiente:

Considérese un hipercubo n-dimensional, y conéctese cada par de vértices para obtener un grafo completo con 2^n vértices. Posteriormente, coloréese cada una de las aristas de negro o de rojo. ¿Cuál es el menor valor de n para el cual toda manera de colorear las aristas necesariamente da lugar a un subgrafo completo de un solo color con 4 vértices que forman un plano?

Graham y Rothschild [1971] demostraron que este problema tiene una solución, N*, y dieron como acotación de la misma 6 ≤ N*N, siendo N un número determinado, definido explícitamente y muy grande. Sin embargo, Graham revisó esta cota superior al alza, la cual fue publicada (y apodada número de Graham) por Martin Gardner en la revista Scientific American de noviembre de 1977 de la siguiente manera:

En una demostración no publicada, Graham ha establecido recientemente … una cota tan vasta que tiene el registro de ser el mayor número jamás usado en una demostración matemática seria.

Ahora bien, ¿cuál es el número de Graham?

Primero debemos definir la notación flecha de Knuth, donde el símbolo (\uparrow\uparrow) indica una «torre» de exponenciaciones (\uparrow). Por ejemplo,

3 \uparrow\uparrow X \ = \ 3 \uparrow (3 \uparrow (3 \uparrow \dots (3 \uparrow 3) \dots )) \ = \ 3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}.

Si añadimos una flecha más, entonces el significado será el siguiente:

3 \uparrow \uparrow \uparrow 3 \ = \ 3 \uparrow \uparrow (3 \uparrow \uparrow 3).

Y con cuatro flechas sería g1, que vendría definido por:

  g_1  = 3 \uparrow \uparrow \uparrow \uparrow 3  = 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3)  = 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots ))

un número extraordinariamente grande, sin duda.

Pues bien el número de Graham, G, es mucho mayor aún y equivale a:

  \left.   \begin{matrix}    G &=&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots\cdots \uparrow}3 \\     & &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\      & &\underbrace{\qquad\;\; \vdots \qquad\;\;} \\      & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\     & &3\uparrow \uparrow \uparrow \uparrow3  \end{matrix}  \right \} \text{64 filas}

donde el número de flechas en cada fila, empezando por la fila superior, viene especificado por el valor de la fila inmediatamente inferior, es decir,

G = g_{64},\text{ donde }g_1=3\uparrow\uparrow\uparrow\uparrow 3,\  g_n = 3\uparrow^{g_{n-1}}3,

donde el superíndice en una flecha superior indica cuántas flechas hay. En otras palabras, G se calcula a través de 64 pasos: el primer paso consiste en calcular g1 con cuatro flechas entre los treses; el segundo paso consiste en calcular g2 con g1 flechas entre los treses, el tercer paso consiste en calcular g3 con g2 flechas entre los treses, y así sucesivamente hasta calcular finalmente G = g64, que tiene g63 flechas entre los treses.

Es evidente que no podemos alcanzar a percibir las dimensiones de dicho número, sin embargo podemos conocer algunos detalles del mismo. Por ejemplo, ¿en qué cifra termina el número de Graham? No es difícil demostrar que cualquier torre de treses suficientemente grande termina en 7 (¿te atreves?). ¿Podemos conocer más cifras? Pues sí. Una de las propiedades de las torres de treses del tipo 3 \uparrow\uparrown es que todas las torres de este tipo de altura mayor que d presentan la misma sucesión de d cifras situadas en los últimos lugares. Este es un caso especial de una propiedad más general: las d últimas cifras de todas las torres de este tipo de altura mayor que d+2 son independientes del “3” situado en la parte superior de la torre, es decir, el 3 situado arriba del todo se puede cambiar por cualquier otro entero no negativo sin afectar las d últimas cifras. La siguiente tabla ilustra, para unos pocos valores de d, cómo ocurre esto:

Número de valores posibles de 3\uparrow3\uparrow…3\uparrowx  mod 10d
Nºcifras (d) 3\uparrowx 3\uparrow3\uparrowx 3\uparrow3\uparrow3\uparrowx 3\uparrow3\uparrow3\uparrow3\uparrowx 3\uparrow3\uparrow3\uparrow3\uparrow3\uparrowx
1 1,3,9,7 3,7 7 7 7
2 1,3,…87 3,27,83,87 27,87 87 87
3 1,3,…387 3,27,…387 27,987,227,387 987,387 387

Con este resultado, las cien últimas cifras del número de Graham (o de cualquier torre con más de cien treses) son:

…9404248265018193851562535
   7963996189939679054966380
   0322234872396701848518643
   9059104575627262464195387

SI TE HA GUSTADO, COMPÁRTELO:

Add to FacebookAdd to DiggAdd to Del.icio.usAdd to StumbleuponAdd to RedditAdd to BlinklistAdd to TwitterAdd to TechnoratiAdd to Yahoo BuzzAdd to Newsvine

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s