VERSION ACTUAL :

Inicio de sesión

Raulito el Friki

Raulito El Friki

COMENTARIOS

EN LINEA

Hay actualmente 1 usuario conectado.

  • Misfits_Herrera

NUEVOS

  • Misfits_Herrera
  • Juan Cruz Alonso
  • Josefv67
  • jesusSci
  • legomamey

Se encuentra usted aquí

Gaussianos

Suscribirse a canal de noticias Gaussianos
Porque todo tiende a infinito...
Actualizado: hace 10 horas 18 mins

La conjetura de Steinberg es…¡falsa!

Dom, 06/26/2016 - 14:25

La teoría de grafos es una de las ramas de las matemáticas que más movimiento está teniendo en los últimos años, en lo que se refiere a investigación y a aplicaciones a problemas “reales”.

Dentro de la teoría de grafos, los problemas relacionados con coloración de grafos tienen gran interés dentro de los especialistas de esta rama.

Y dentro de los problemas de coloración de grafos, la conjetura de Steinberg ha sido uno de los problemas abiertos que más han interesado a los estudiosos en la materia.

Bien, pues (parece ser que) tenemos resultado para este problema: la conjetura de Steinberg es falsa. En lo que sigue, vamos a dar una idea sobre qué es eso de la coloración de grafos y hablaremos de esta interesante conjetura.

Aunque en Gaussianos ya hemos hablado en otra ocasiones sobre grafos, no está mal recordar algo sobre ellos. Un grafo es un conjunto V (distinto del vacío) de puntos, llamados vértices, y un conjunto de líneas A, llamadas aristas, cada una de las cuales une dos de sus vértices. Si dos vértices están unidos con al menos una arista, se dice que dichos vértices están conectados.

Un grafo plano es un grafo que puede dibujarse en un plano con la condición de que dos aristas cualesquiera no se cortan en ningún punto que no sea un vértice. En la siguiente imagen podéis ver un grafo plano y uno que no lo es (de hecho es el famoso grafo de Kuratowski K_{3,3}):

plano-noplano

Un ciclo en un grafo es una sucesión de vértices v_1, \ldots ,v_n, v_1 en la que cada vértice de la lista está conectado con el siguiente y donde no hay vértices repetidos (excepto el primero y el último). Vamos, lo que todos esperaríamos que fuera un ciclo. La longitud de un ciclo es el número de vértices distintos (equivalentemente, el número de aristas) que contiene. Un ciclo de longitud n se suele denominar n-ciclo. Aquí tenéis dos ciclos, uno de longitud 3 (el verde) y otro de longitud 5 (el rojo):

ciclos

Una coloración de un grafo es una asignación de etiquetas (colores) a los vértices de dicho grafo de manera que dos vértices conectados tengan distinto color. Si el número de etiquetas es pequeño, suelen usarse colores para etiquetar los vértices. Si este número es grande, suelen usarse números enteros positivos: 1,2, \ldots , m. Si en la coloración se usan k colores, se dice que tenemos una k-coloración. Aquí tenéis como ejemplo una 3-coloración del grafo anterior:

3coloracion

The Three Color Problem

Ya tenemos todo lo necesario para introducir el tema principal de esta entrada. La cuestión central de toda esta historia es el coloreado de mapas. El resultado más conocido en relación con esto, como muchos ya sabréis, es el famosísimo teorema de los cuatro colores, demostrado por Kenneth Appel y Wolfgang Haken en 1976.

La primera noticia que se tiene sobre la coloración de mapas con tres colores es un paper de Arthur Cayley de 1879. Ese mismo año, Alfred Kempe también lo trata en su trabajo sobre el teorema de los cuatro colores (que, por cierto, contenía una demostración incorrecta de este resultado); y, más adelante, Percy Heawood también habla de él en sendos trabajos que datan de 1890 y 1898, respectivamente.

Pero es en 1958 cuando el Three Color Problem pasa a tener entidad de problema propio gracias a Herbert Grötzsch, siendo Oystein Ore en 1967 quien lo elevó a los altares. Recomiendo el paper The state of the Three Color Problem [Annals of Discrete Mathematics, 55, 21 1-248 (1993)], de Richard Steinberg, a quienes estén interesados en más datos relacionados con la historia de este problema.

El Three Color Problem pregunta, básicamente, lo siguiente:

¿Bajo qué condiciones pueden ser coloreadas las regiones de un mapa plano con tres colores de manera que no haya dos regiones con frontera común que tengan asignado el mismo color?

Como cada región de un mapa puede interpretarse como un vértice y la frontera común de dos regiones puede asociarse con una arista, un problema de coloreado de mapas puede interpretarse como un problema de coloreado de grafos.

Y por ahí va la cosa, por coloreado de grafos. En 1976, el propio Richard Steinberg establece la conjetura que actualmente lleva su nombre:

Conjetura de Steinberg:

Todo grafo plano que no contenga ni 4-ciclos ni 5-ciclos es 3-coloreable.

Es decir, si un grafo no tiene ciclos de longitud 4 ni ciclos de longitud 5, entonces pueden colorearse sus vértices con 3 colores de manera que no haya vértices conectados que compartan color.

Hasta hace poco, había habido acercamientos a dicha conjetura. Posiblemente, el más interesante surgió a partir de una sugerencia del gran Paul Erdős. Erdős sugirió buscar si existía una constante k que cumpliera que todo grafo sin ciclos de longitud 4,5, \ldots , k era 3-coloreable. Borodin, Glebov, Raspaud y Salavatipour, mejorando resultados anteriores, demostraron en Planar graphs without cycles of length from 4 to 7 are 3-colorable [J. Combin. Theory Ser. B 93 (2005), 303–331] que k \le 7.

Y más o menos en este punto es en el que estábamos…hasta hace bien poquito (en julio de 2006, se publicaba una supuesta demostración de la veracidad de la conjetura de Steinberg que no fue aceptada como correcta). En abril de este año 2016, Vincent Cohen-Addad, Michael Hebdige, Daniel Král, Zhentao Li y Esteban Salgado ha demostrado que la conjetura de Steinberg es falsa. En su trabajo Steinberg’s Conjecture is False, construyen un contraejemplo para dicha conjetura. Es decir, construyen un grafo plano que no contiene ni 4-ciclos ni 5-ciclos y que no es 3-coloreable. Para ello, comienzan construyendo un grafo G_1 (arriba a la izquierda en la imagen) con ciertas propiedades; a partir de él construyen un segundo grafo G_2 (arriba a la derecha); y para finalizar construyen un grafo G (abajo) a partir de este último que cumple que no tiene ni 4-ciclos ni 5-ciclos y que además no es 3-coloreable:

En el paper que acabo de enlazar podéis ver la demostración de este hecho.

Bien, la conjetura de Steinberg es falsa, problema resuelto. Pero el Three Color Problem sigue abierto, todavía no sabemos si ese k cuya búsqueda sugirió Erdős es 7 ó 6. Estaremos atentos a futuras novedades.

Fuentes y enlaces relacionados:

Esta entrada participa en la Edición 7.5 del Carnaval de Matemáticas, cuyo anfitrión es el blog Series Divergentes.

Explicando un “Casi-Pi” relacionado con un seno y muchos cincos

Mar, 05/24/2016 - 05:30

Un “Casi-Pi” podría definirse como una aproximación de Pi que, posiblemente, uno no esperaría encontrarse. Vamos, una operación que involucra ciertos números y que, de manera más o menos sorprendente, da como resultado una interesante aproximación de nuestro amado número Pi.

Tomo prestado este nombre de este post del blog de Claudio Meller (por cierto, blog muy interesante que os recomiendo visitar). Y aprovecho que he visto dicha entrada para enseñaros un “Casi-Pi” bastante curioso:

sen \left ( \cfrac{1}{55555555} \right )=3.14159268 \ldots \cdot 10^{-10} \approx \pi \cdot 10^{-10}

Este valor, multiplicando por 10^{10}, nos da una aproximación de \pi con 7 decimales exactos. Lo que decía, bastante curioso, ¿verdad?

Pues la cosa se torna en totalmente intrigante cuando comprobamos que aumentando el número de cincos mejoramos la aproximación. Por ejemplo, para 12 cincos obtenemos lo siguiente:

sen \left ( \cfrac{1}{555555555555} \right )=3.141592653592 \ldots \cdot 10^{-14}

El resultado, después de multiplicar por 10^{14}, nos ofrece una aproximación de \pi con 10 decimales exactos. Y, por poner otro ejemplo, con 20 cincos se obtiene

sen \left ( \cfrac{1}{55555555555555555555} \right )=3.141592653589793238494 \ldots \cdot 10^{-22}

que nos da, después de multiplicar por 10^{22}, una aproximación de \pi con 19 decimales correctos.

Tatuaje de PiY podéis seguir aumentando el número de cincos. Cuantos más pongáis, mejor sería la aproximación que obtendréis (después de multiplicar por cierta potencia de 10).

¿Qué está pasando? ¿Qué tipo de brujería es ésta? Tranquilos, no hay ninguna razón oculta en este tema. ¿Casualidad? Como diría aquél, no lo creo. Y, de hecho, no lo es. Todo esto tiene una explicación y, al contrario que cualquier mago que se precie, os voy a desvelar el (sencillo) “truco” que hay escondido aquí.

Para empezar, recordemos que, para valores de x cercanos a cero, se tiene que sen(x) \approx x (hecho que también ha dado para el insulto matemático definitivo)…pero, y esto es muy importante, dicha aproximación se tiene si x está medido en radianes. Si tomamos x medido en grados sexagesimales (los grados de toda la vida), la equivalencia queda así:

sen(x)\approx \cfrac{\pi}{180} \; x

Explicado esto, vamos a meternos en el tema. Teniendo en cuenta que

\cfrac{1}{180}=0.00555 \overline{5}

podemos relacionar el 180 con un número formado solo por cincos. Por poner algunos ejemplos:

  • \cfrac{1}{180} \approx 5555 \cdot 10^{-6}
  • \cfrac{1}{180} \approx 555555 \cdot 10^{-8}
  • \cfrac{1}{180} \approx 55555555 \cdot 10^{-10}

En general, para k cincos se tiene que

\cfrac{1}{180} \approx 555 \ldots (k) \ldots 555 \cdot 10^{-k-2}

Particularizando para k=8, tendríamos que:

\cfrac{1}{55555555} \approx 180 \cdot 10^{-10}

Si sustituimos en la expresión anterior del seno en grados, obtenemos el “Casi-Pi” que comentábamos al principio:

sen \left ( \cfrac{1}{55555555} \right ) \approx \cfrac{\pi}{180} \cdot \cfrac{1}{55555555} \approx \cfrac{\pi}{180} \cdot 180 \cdot 10^{-10} =\pi \cdot 10^{-10}

Por lo que:

10^{10} \cdot sen \left ( \cfrac{1}{55555555} \right ) \approx \pi

Y, como decíamos antes, al aumentar el número de cincos obtenemos cada vez mejores aproximaciones.

Después de explicar todo esto, después de mostrar el “truco”, parece que la cosa no es para tanto. Pero lo que seguro no podréis negar es que la “casualidad” nos proporciona un, cuando menos, curioso resultado, ¿verdad?

Por cierto, ¿qué pensáis sobre la posibilidad de encontrar un “Casi-Pi” ciertamente sorprendente que realmente pueda considerarse una casualidad? ¿Conocéis alguno? Para abrir boca os dejo uno al que, al menos yo, no le encuentro “explicación” (vamos, que parece ser totalmente “casual”):

(Ln(6))^{{{{(Ln(5))}^{(Ln(4))}}^{(Ln(3))}}^{(Ln(2))}}=3.141577 \ldots

Esta entrada participa en la Edición 7.4 del Carnaval de Matemáticas, que, en esta ocasión, organiza Marta Macho desde el blog ZTFNews.

Ha fallecido Javier Cilleruelo, DEP

Dom, 05/15/2016 - 13:05

Hace unas horas me he enterado del triste fallecimiento, hoy mismo, del matemático español Javier Cilleruelo. El primero en avisarme ha sido Diego Soler, a través de la página de Facebook del blog. Después, durante el día, han sido varios amigos, compañeros, exalumnos y familiares de Javier los que me han comunicado y confirmado la noticia.

Javier Cilleruelo

El fallecimiento de Javier es una gran pérdida, tanto a nivel profesional como a nivel personal. En lo que se refiere a su profesión, era uno de los matemáticos españoles de mayor importancia y reconocimiento dentro de su área, la teoría de números. Era profesor titular de la Universidad Autónoma de Madrid (UAM), miembro del Instituto de Ciencias Matemáticas (ICMAT) y director del Colegio Mayor Juan Luis Vives de la UAM (es de la página de Facebook de este colegio mayor de donde he tomado la imagen que acompaña a esta entrada).

En los últimos años, Javier, en colaboración con otros matemáticos, resolvió algunos problemas de su área que, hasta ese momento, permanecían abiertos. Concretamente, los que han llegado a mi conocimiento son el problema de los conjuntos generalizados de Sidon, que resolvió junto a Imre Ruzsa y Carlos Vinuesa, y el problema de cómo expresar números enteros como suma de números capicúas, resuelto por Javier junto a Florian Luca.

Por otra parte, Javier ha sido uno de los grandes colaboradores que ha tenido Gaussianos desde siempre. Cuando me enteré de la resolución del problema los conjuntos generalizados de Sidon, me puse en contacto con él y, muy gentilmente, accedió a colaborar con el blog. De dicha colaboración salió la entrada Javier Cilleruelo nos habla sobre el problema de los conjuntos generalizados de Sidon. Pero la cosa no quedó ahí. A propósito de la visita de Endre Szemerédi a Madrid, Javier me ayudó a presentaros el teorema de Szemerédi en la entrada Endre Szemerédi, una leyenda viva de las matemáticas. Ambas colaboraciones se produjeron en el año 2011.

Ya en 2014, Harald Helfgott (exacto, el matemático peruano que demostró la conjetura débil de Goldbach), visitaba España para dar un coloquio en el ICMAT. En aquellas fechas, Javier colaboraba con Gaussianos presentando dicho coloquio y dando unas líneas generales sobre el problema en la entrada “La conjetura débil de Goldbach”, coloquio de Harald Helfgott en el ICMAT. Y, por último, hace bien poco (en febrero de este año 2016) Javier nos sorprendía demostrando, junto a Florian Luca, que todo entero positivo puede expresarse como suma de tres números capicuás. Fue él mismo quien me informó sobre este hallazgo y, como no podía ser de otra forma, quien me sugirió publicar un artículo sobre ello en este blog. Y así lo hicimos en Todo entero positivo es suma de tres capicúas (por javier Cilleruelo).

Además, compartimos colaboración con El País y la RSME por el centenario de ésta última en 2011. En aquel año, se celebró dicho centenario con la publicación de 40 problemas en dicho medio de comunicación. Javier se encargó de proponer el problema número 3 y yo el problema número 39. Más adelante, esta colaboración entre El País y la RSME se ha repetido en fechas señaladas, y Javier siguió apareciendo en estas colaboraciones. En concreto, propuso el Desafío Extraordinario de Navidad 2013 y el cuarto Desafío de verano de 2014. Los amantes de los problemas matemáticos seguro que disfrutaréis intentando resolver todos ellos.

Por otra lado, a nivel personal se nos va una magnífica persona, alguien a quien todos apreciaban y que, al menos según mi experiencia, se tenía bien ganado ese cariño. Para mí, Javier ha sido, y es, alguien muy especial. Siempre tuvo una magnífica disposición a colaborar conmigo y a ayudarme en lo que yo pudiera necesitar, y eso, bajo mi punto de vista, es de admirar. Y viendo las reacciones que me han llegado de algunos de sus compañeros, amigos y conocidos, veo que no soy el único que le tenía un cariño y aprecio especial. Se nos va un gran matemático y, sobre todo, una maravillosa persona. Javier, te echaremos de menos. Descansa en paz.

No, los experimentos aleatorios independientes no tienen memoria

Lun, 04/18/2016 - 06:30

“Cuanto más llevas sin ganar, más probable es que ganes el siguiente”. Esta afirmación, que podría parecer cierta, en realidad no tiene mucho sentido en términos de probabilidad. En los próximos párrafos analizaremos el porqué.

Antes de comenzar, quiero dejar claras las condiciones del tema que vamos a comentar. Lo que sigue se refiere a experimentos aleatorios independientes (es decir, su resultado en un momento dado no influye en el resultado del mismo experimento en otro momento, como puede pasar al lanzar un dado o una moneda) con un número finito de resultados en el que conocemos la probabilidad de cada uno de ellos.

Vamos al tema. Esta entrada me vino a la mente después de ver un tuit del famoso tuitero deportivo @2010MisterChip. Otro tuitero, @ScottiePeppino, le comentaba lo siguiente a raíz de una apuesta que el primero había realizado:

@2010MisterChip hombre, siendo un hombre de estadísticas como eres, apostar por el equipo que lleva sin ganar en ese estadio 30 partidos…

— Scottie Peppino (@ScottiePeppino) 11 de abril de 2016

A lo que MisterChip contestaba lo siguiente

Cuanto más llevas sin ganar, más probable es que ganes el siguiente. Estadística pura y dura 😉 https://t.co/ylyJpoVa6g

— MisterChip (Alexis) (@2010MisterChip) 11 de abril de 2016

Si accedéis al mismo podéis ver mi respuesta

@2010MisterChip Esto…Hablando de azar (si citas "estadística" supongo que te refieres a eso), lo que has dicho no es para nada correcto

— gaussianos (@gaussianos) 11 de abril de 2016

y algunas más de otros tuiteros. Todos intentábamos hacerle ver que había caído en una famosa falacia estadística, pero, hasta el día de hoy, la única respuesta que he visto de MisterChip es la siguiente (si hay alguna más decídmelo):

Cambia "jugador" por "mal jugador" y estaremos de acuerdo. https://t.co/03oXVSLo9H

— MisterChip (Alexis) (@2010MisterChip) 11 de abril de 2016

Si analizamos el tema de manera probabilística (entiendo que ésa era la intención de MisterChip al hablar de “estadística”), el asunto es como sigue: estamos ante un experimento aleatorio con dos posibles resultados (victoria de equipo de casa o victoria del equipo visitante, no consideramos el empate) en el que tenemos la probabilidad de cada uno de ellos (se podría hablar de cómo se determinan dichas probabilidades, pero eso es otro tema). Además, dichos resultados son independientes.

Si realizamos el experimento, podemos obtener cualquiera de los dos resultados. Imaginemos que gana el equipo de casa. Si volvemos a realizar el experimento, la pregunta es la siguiente: ¿ha aumentado la probabilidad de que gane el equipo visitante? La respuesta es NO. Para hacer un análisis probabilístico correcto, en este caso tenemos que considerar que el resultado obtenido en un enfrentamiento no influye en lo que pasará en el enfrentamiento siguiente (los resultados son independientes).

La creencia de que muchos resultados “hacia un lado” aumentan la probabilidad de que en la siguiente ocasión la cosa irá “hacia el otro lado” o, más en general, que los resultados obtenidos influyen en los siguientes (vamos, que el juego “tiene memoria”) se denomina falacia del jugador. Uno de los ejemplos más conocidos de esta falacia es el caso que se dio el 18 de agosto de 1913 en una de las ruletas del casino de Monte Carlo. En aquella ocasión, la bolita cayó la friolera de ¡¡26 veces seguidas!! en el negro. Lo que ocurrió es que, a medida que iban saliendo “negros”, los jugadores iban apostando cada vez más al “rojo”, porque entendían que con tantas apariciones del negro era mucho más probable que en la siguiente tirada saliera rojo. Y no, esto no es así: la probabilidad de rojo no aumentaba en este caso. Tomando la ruleta como un juego de probabilidades, y dando un 0.5 al rojo y un 0.5 al negro (esto no exacto, pero para el caso en el que estamos nos vale), esas probabilidades se mantienen en cada tirada independientemente de lo que saliera en tiradas anteriores (la ruleta “no tiene memoria”). ¿Qué ocurrió? Pues no es difícil imaginarlo: el casino ganó muchísimo dinero en ese rato.

¿Por qué entonces pensamos de esta errónea manera (y, si somos jugadores, tan perjudicial para nuestro bolsillo)? Pues porque tendemos a pensar que si los resultados anteriores se desvían sustancialmente de lo que marcan las probabilidades, dicha desviación se corregirá pronto para dejarlo todo “como debe ser” (en este caso, mismo número de rojos que de negros). Eso es, a todas luces, falso. Y de este error por nuestra parte se aprovechan a veces los organizadores de este tipo de juegos, dándonos, por ejemplo, los números calientes y los números fríos (intentando así influir en nuestra percepción sobre las probabilidades de cada número en la siguiente tirada). De hecho, en juegos tipo la ruleta, en una situación como ésta de tantos “negros” seguidos podría ser más razonable pensar que dicha ruleta está “trucada” (premeditadamente o no, eso no es importante) para que salgan más “negros” que “rojos”, por lo que quizás tendría más sentido volver a apostar al “negro” en la tirada siguiente (esta forma de razonar se conoce como principio de Hume).

Y un último detalle. Es también interesante distinguir entre “número de veces que se ha producido cada resultado” y “probabilidad de cada resultado”. Que las probabilidades sean iguales no significa, ni mucho menos, que conforme aumentamos el número de realizaciones del experimento las veces en las que sale cada resultado tiendan a igualarse. Voy a poner un ejemplo para intentar explicar qué quiero decir:

Imaginemos que tiramos una moneda 100 veces y salen 40 caras y 60 cruces. En este caso, llevaríamos un 40% de caras y un 60% de cruces. Imaginemos que seguimos tirando la monda y llegamos a 1000 tiradas, obteniendo 460 caras y 540 cruces. Las probabilidades se van acercando, 0.46 para “cara” y 0.54 para “cruz”, pero la distancia entre el número de veces de cada una es mayor (antes era 20 y ahora es 80).

Recordad: la probabilidades en estos casos se calculan dividiendo casos favorables entre casos posibles. Por ello, aunque las probabilidades se vayan igualando, la diferencia de las veces que sale cada uno de los resultados puede ser cada vez mayor.

Se ha escrito mucho sobre la falacia del jugador, y en internet podéis encontrar gran cantidad de artículos sobre el tema. Os dejo éste del maestro Adrián Paenza: La falacia del jugador.

Sobre la manera de determinar las probabilidades de cada uno de los resultados quería hacer un comentario. ¿Tiene sentido tomar los resultados anteriores entre ambos equipos para determinar dicha probabilidad? Si la respuesta es afirmativa, el hecho de que un equipo haya perdido los últimos enfrentamientos directos debería entonces, bajo mi punto de vista, hacer que la probabilidad de victoria del “perdedor habitual” baje respecto a estimaciones anteriores, pero nunca que suba. Y si no lo veis, ahí va un ejemplo:

Imaginemos que el Granada ha perdido 20 veces seguidas en el Bernabéu, y que “su” probabilidad de victoria era de 0.1. ¿Significa eso que si vuelven a jugar ahora en el Bernabéu tienen una probabilidad mayor de ganar?

Pues yo creo que no. A ver qué pensáis vosotros.

Y sobre el hecho de que los resultados anteriores puedan influir en la mente de los jugadores del equipo “perdedor habitual”, cabrían las dos posibilidades. Podría ser de manera positiva (más ganas de romper la mala racha) o de manera negativa (como llevan muchos años perdiendo no se ven con capacidad de ganar). Pero eso significaría que introducimos efectos externos en el análisis (podrían añadirse más: la buena o mala temporada que está haciendo cada uno, la moral que se tiene en esa época, si se juegan algo importante en ese momento o no…), efectos que no tienen que ver con la probabilidad. Por ello no cabría hablar de estadística en este caso.

Este artículo participa en la Edición 7.3 del Carnaval de Matemáticas, que en esta ocasión organiza Pimedios.es.

La sucesión de Golomb y una aparición “dorada”

Mar, 03/29/2016 - 06:00

El mundo de las matemáticas es apasionante por muchas razones, y una de las principales (bajo mi punto de vista) es la aparición de objetos matemáticos conocidos en los lugares más insospechados. Eso es lo que ocurre en la conocida como sucesión de Golomb, de la cual vamos a hablar en esta entrada.

La sucesión de Golomb (que también se conoce como sucesión de Silverman), es una sucesión no decreciente de enteros positivos en la que cada término a_n indica el número de veces que aparece el número n en dicha sucesión. Comienza con a_1=1, y el resto de valores a_k corresponden al entero positivo que haga que se satisfaga la condición anterior.

Su nombre se debe a Solomon Golomb, un matemático, ingeniero y profesor estadounidense nacido en 1932.

Solomon Golomb

Además de dar nombre a esta sucesión, Golomb inventó el juego Cheskers, una variante ajedrecística de las damas, en 1948, y describió los poliominós y los pentóminos en 1953. Más información en Solomon W. Golomb en la Wikipedia en inglés.

Vamos a ir construyendo la sucesión de Golomb paso a paso. Como a_1=1, tenemos que el 1 aparece una única vez en la sucesión. Por tanto, a_2 no puede ser 1, por lo que debe ser a_2=2. Eso indica que el 2 aparece dos veces en la sucesión, por lo que es obligatorio que a_3=2. Ya tenemos nuestras dos apariciones del 2, pero a_3=2 indica que el 3 también debe aparecer dos veces, por lo que es necesario que a_4=3 y a_5=3. Ahora, a_4=3 nos dice que el 4 debe aparecer 3 veces, por lo que los tres siguientes valores deben ser 4; y a_5=3 indica que el 5 también aparece 3 veces, lo que nos lleva a que los siguientes 3 valores deben ser igual a 5…y así sucesivamente.

Los primeros valores de la sucesión de Golomb (A001462 en la OEIS) son los siguientes:

\begin{matrix} 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, \\ 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, \\ 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, \\ 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, \\ 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, \\ 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, \\ 17, 17, 18, 18, 18, 18, 18, 18, 18, 19 \end{matrix}

Como veis, no es demasiado complicado describir los elementos de esta sucesión, pero no nos vendría mal una relación de recurrencia que nos ayude, ¿verdad? Pues la hay. Se debe a Colin Mallows, y es la siguiente:

\begin{matrix} a(1)=1 \\ \\ a(n+1)=1+a(n+1-a(a(n))) \end{matrix}

Interesante, ¿verdad? Pues queda lo mejor: tenemos una maravillosa expresión asintótica para a_n. Se ha demostrado que, cuando n \to \infty:

a_n \xrightarrow{n \to \infty} \phi^{2-\phi} \cdot n^{\phi-1}

siendo \phi=\frac{1+\sqrt{5}}{2} el número áureo, el número de oro. ¿No es magnífico?

Podéis ver demostraciones de este resultado aquí. En la siguiente imagen os dejo una de ellas:

Por cierto, sobre esta demostración un apunte. En la misma se calcula que

a=\left (\phi-1 \right )^{\frac{-1}{\phi+1}}

Pero después “parece” que se da otro valor (en la solución final). Bien, podéis comprobar vosotros mismo que ambos valores son iguales, es decir:

a=\left (\phi-1 \right )^{\frac{-1}{\phi+1}}=\phi^{2-\phi}

Si queréis más datos sobre cómo de buena es esta aproximación asintótica, podéis echar un vistazo a The error term in Golomb’s sequence, de Ilan Vardi. También presenta un método eficiente para calcular valores grandes de la sucesión de Golomb.

Como decía al principio, es magnífico ver cómo números tan bellos como \phi aparecen de manera inesperada en un sitio como éste, la sucesión de Golomb, al cual parecía no estar invitado. Cosas así siempre me recuerdan a la curiosa, y también inesperada, aparición de \pi en el conjunto de Mandelbrot, de la que hablé en Pi y el conjunto de Mandelbrot. ¿Conocéis más casos parecidos a estos?

Tuve conocimiento de esta sucesión a través del vídeo Six sequences, de Numberphile, del cual también saqué información para escribir La sorprendente constante de Khinchin en octubre de 2014.

Foto de Golomb tomada de aquí.

Encontrada la mejor manera de apilar naranjas 8-dimensionales

Sáb, 03/26/2016 - 11:54

¿Tienes un montón de pelotitas esféricas 8-dimensionales en el garaje y no sabes cuál es la mejor manera de colocarlas? Bien, pues tu problema (parece que ya) está resuelto: ya se sabe cuál es la forma más eficiente de disponer esferas 8-dimensionales.

En el trabajo The sphere packing problem in dimensión 8 (publicado hace apenas un par de semanas), la matemática Maryna S. Viazovska (de la Berlin Mathematical School y de la Humboldt University, también de Berlín) demuestra lo siguiente:

No hay ningún empaquetamiento de esferas unidad en dimensión 8 que tenga densidad mayor que la que da la red E_8

Maryna Viazkovska

Vamos a explicar un poco de qué va todo este tema.

El sphere packing problem (o problema de empaquetamiento de esferas) consiste en encontrar la manera más eficiente de colocar esferas unidad (de radio 1), entendiendo por más eficiente a la disposición que deje una menor cantidad de espacio vacío entre ellas (es decir, la más densa). Este problema, que puede estudiarse en cualquier dimensión, ha interesado a la comunidad matemática desde hace un buen puñado de años.

Para n=1, nuestro espacio \mathbb{R} es una recta y nuestras esferas unidad son intervalos de amplitud (diámetro) 2. En este caso podemos rellenar la recta completa con intervalos sin dejar huecos, por lo que, si llamamos \Delta_n a la densidad de la colocación más eficiente en \mathbb{R}^n, se tiene claramente que \Delta_1=1

En el caso n=2, tenemos que \mathbb{R}^2 es un plano y la esfera unidad es un círculo de radio 1. Aquí se sabe que la disposición más densa es una como la siguiente:

Joseph Louis Lagrange, en 1773, fue el primero en probar que esta disposición era la disposición regular más densa en dos dimensiones. Axel Thue, a principios del siglo XX, probó que también era la más densa aun considerando también disposiciones irregulares, pero dicha demostración se consideró incompleta. Sobre 1940, László Fejes Toth dio una demostración que, ahora sí, se considera correcta.

Por cierto, la densidad de esta disposición, llamada empaquetamiento hexagonal, es:

\Delta_2=\cfrac{\pi}{\sqrt{12}} \approx 0.90690

Es decir, con este empaquetamiento cubrimos algo más del 90% del plano.

Para n=3, tenemos que \mathbb{R}^3 es el espacio tridimensional que todos conocemos y la esfera unidad es un esfera maciza tridimensional de radio 1. En este caso, la disposición más densa es la denominada empaquetamiento compacto, que podríamos definir como la colocación más habitual de naranjas que podemos encontrar en una frutería:

Este problema es conocido como la conjetura de Kepler, y fue planteada por Johannes Kepler en 1611. La densidad de esta disposición es:

\Delta_3=\cfrac{\pi}{\sqrt{18}} \approx 0.74048

Esto es, dicha colocación ocupa algo menos del 75% del espacio tridimensional.

En 1831, Gauss demostró que ésta es la mayor densidad siempre que la disposición de esferas sea regular (es decir, siempre que la colocación de las mismas siga un patrón), pero todavía quedaba por ver si también superaba a las disposiciones irregulares. En 1998, Thomas Hales concluyó la demostración, no sin polémica por el uso del ordenador. Os recomiendo que leáis La conjetura de Kepler para más detalles de esta historia.

Y hasta ahora no se había encontrado la disposición más densa para ninguna otra dimensión. Para n=8 se sabía que la red E_8 era la disposición periódica más densa, pero no sabíamos si había alguna no periódica que fuera más densa que ella. Maryna Viazkovska se ha encargado de demostrar que no es así. La densidad de dicha disposición es:

\Delta_8=\cfrac{\pi^4}{384} \approx 0.25367

Es decir, en \mathbb{R}^8 sólo podemos aspirar a rellenar algo más del 25% del espacio con esferas unidad.

Ah, por cierto. Seguro que os preguntáis qué es la red E_8, ¿verdad? Pues es el subgrupo discreto de \mathbb{R}^8 que puede definirse mediante el conjunto de puntos, \Gamma_8, siguiente:

\Gamma_8=\{(x_1, \ldots , x_8) \in \mathbb{Z}^8 \cup (\mathbb{Z} + \cfrac{1}{2})^8 \Bigg / \displaystyle{\sum_{i=1}^8 x_i \equiv 0 \; (\mbox{mod } 2)} \}

Tenéis más información en E_8 lattice (en la Wikipedia en inglés) y en los enlaces que encontraréis un poco más abajo.

Y como suele pasar en muchas ocasiones en matemáticas, un problema resuelto puede ayudar a resolver otros. En este caso, el trabajo de Viazkovska ha servido para que también se concluya la demostración para n=24. La propia Maryna junto con Henry Cohn, Abhinav Kumar, Stephen D. Miller y Danylo Radchenko prueban en The sphere packing problem in dimension 24 que la red Leech es la más densa dentro de \mathbb{R}^{24}, siendo su densidad la siguiente:

\Delta_{24}=\cfrac{\pi^{12}}{12!} \approx 0.00192

Y un apunte final. Por si alguien se lo pregunta, el sphere packing problem tiene aplicaciones prácticas, por ejemplo en los códigos de corrección de errores. Podéis consultar Communication and ball packing para más información.

Fuentes y enlaces relacionados:

Algunos enlaces de Gaussianos relacionados con estoys y otros empaquetamientos:

Esta entrada participa en la Edición 7.2 del Carnaval de Matemáticas, que en esta ocasión organiza el blog La aventura de la ciencia.

Andrew Wiles, premio Abel 2016

Mar, 03/15/2016 - 08:26

El matemático británico Andrew Wiles, de la Universidad de Oxford, ha sido galardonado con el Premio Abel 2016 por la Norwegian Academy of Science and Letters “por su impresionante demostración del último teorema de Fermat mediante la conjetura de modularidad de curvas elípticas semiestables, iniciando una nueva era en la teoría de números”. Wiles añade este premio al Premio Fermat (1995), al Premio Wolf en Matemáticas (1995/6), a la Royal Medal de la Royal Society (1996), a la IM Silver Plaque (1998) y al Premio Shaw (2005), entre otros.

Andrew Wiles

Andrew Wiles junto al enunciado del UTF.

La vida de Andrew Wiles ha estado unida desde siempre al último teorema de Fermat. Él mismo cuenta que cuando tenía 10 años encontró un libro en el que se hablaba del último teorema de Fermat, y que quedó intrigado al ver un problema que él podía entender pero que llevaba más de 300 años sin resolverse. Según él, desde ese mismo instante pensó que algún día tendría que encontrar la solución.

Y lo consiguió, aunque le costó dos intentos (en primera instancia, su demostración contenía un error que le costó un año solucionar) y varios años de trabajo dedicados exclusivamente a este problema. Pero lo dicho, lo consiguió. La resolución del UTF le reportó fama mundial, y no solamente dentro de la comunidad matemática. Wiles es uno de los pocos matemáticos (quizás el único) que ha tenido repercusión en medios de comunicación generalistas por la demostración de un teorema matemático (hay otro muy reciente, Grisha Perelman, pero fue noticia más por su carácter que por sus logros matemáticos).

Con este premio Abel, Wiles consigue por fin uno de los máximos galardones que puede recibir un matemático. El otro, la Medialla Fields, no la pudo conseguir, ya que cuando resolvió el error de su demostración ya sobrepasaba los 40 años (edad máxima requerida para recibir dicho premio). Mi más sincera enhorabuena.

Fuentes y enlaces relacionados:

Imagen de Wiles tomada de aquí.

El primer producto infinito con Pi como protagonista

Lun, 03/14/2016 - 05:00

Hoy es 14 de marzo y, como todos los años, en esta fecha se celebra mundialmente el día de Pi por ser 3-14 la notación que se utiliza para este día en ciertas zonas de nuestro planeta. Además, añadiendo las dos últimas cifras de este año 2016, en esta ocasión tenemos la típica aproximación a cuatro decimales que todos aprendimos en su momento de este interesantísimo número irracional: 3.1416.

Mucho hemos hablado en Gaussianos sobre Pi (en la categoría Pi podéis ver la gran cantidad de artículos en los que aparece), y todos los años hemos celebrado este bonito día 14 de marzo (al final de esta entrada tenéis los enlaces a los artículos publicados en este blog el día de Pi). Y, para no poder las buenas costumbres, este año vamos a volver a hacerlo.

En esta ocasión vamos a celebrar el día de Pi destacando el primer producto infinito conocido con Pi como protagonista. Se trata de la conocida como fórmula de Viète, publicada por François Viète en 1593 como parte de su obra Variorum de rebus mathematicis responsorum, liber VIII. Dicha fórmula es la siguiente:

\cfrac2\pi=  \sqrt{\cfrac12} \cdot\sqrt{\cfrac12 +\cfrac12\sqrt{\cfrac12}}\cdot\sqrt{\cfrac12 +\cfrac12 \sqrt{\cfrac12 + \cfrac12\sqrt{\cfrac12}}}\cdot\sqrt{\cfrac12+\cfrac12\sqrt{\cfrac12 +\cfrac12 \sqrt{\cfrac12 + \cfrac12\sqrt{\cfrac12}}}}\cdots

Al parecer, no solamente se trata del primer producto infinito en el que aparece el número Pi, sino del primer desarrollo infinito que involucra a dicho número. Viendo que hasta ese momento sólo se disponía de aproximaciones para Pi, el descubrimiento de esta expresión puede considerarse como un hito histórico, así como un gran avance de las matemáticas en su conjunto.

La idea que usó Viète fue partir de un círculo de radio 1 (cuya área es exactamente \pi) e inscribir en él polígonos de 2^n lados, para n \geq 2, comparando después las áreas de los polígonos de 2^k y 2^{k+1} lados. Pero hay una manera relativamente sencilla de deducir la fórmula de Viète utilizando identidades trigonométricas:

Si inscribimos un polígono regular de 2^n lados en un círculo de radio 1, es sencillo ver, triangulando dicho polígono, que el área del mismo, a_n, se puede expresar así:

a_n=2^n \; sen \left ( \cfrac{\pi}{2^n} \right ) \; cos \left ( \cfrac{\pi}{2^n} \right )

Usando la fórmula de seno de ángulo doble, sen(2 \alpha)=2sen(\alpha)cos(\alpha), llegamos a que:

a_2=a_3 \; cos \left ( \cfrac{\pi}{2^2} \right )=a_4 \; cos \left ( \cfrac{\pi}{2^2} \right ) cos \left ( \cfrac{\pi}{2^3} \right )=a_5 \; cos \left ( \cfrac{\pi}{2^2} \right ) cos \left ( \cfrac{\pi}{2^3} \right ) cos \left ( \cfrac{\pi}{2^4} \right )=\ldots

Como a_n tiende a \pi cuando n \to \infty (el área del círculo), se tiene que:

a_2=\pi \; cos \left ( \cfrac{\pi}{2^2} \right ) cos \left ( \cfrac{\pi}{2^3} \right ) cos \left ( \cfrac{\pi}{2^4} \right ) cos \left ( \cfrac{\pi}{2^5} \right ) \ldots

Ahora, a_2 es el área del cuadrado inscrito en el círculo anterior, cuyo valor es 2, por lo que de la expresión anterior obtenemos lo siguiente:

\cfrac{2}{\pi}=cos \left ( \cfrac{\pi}{2^2} \right ) \; cos \left ( \cfrac{\pi}{2^3} \right ) \; cos \left ( \cfrac{\pi}{2^4} \right ) \; cos \left ( \cfrac{\pi}{2^5} \right ) \ldots

Usando ahora la fórmula para el seno del ángulo mitad, cos \left ( \frac{\alpha}{2} \right )=\sqrt{\frac{1+cos(\alpha)}{2}}=\sqrt{\frac{1}{2}+\frac{1}{2} cos (\alpha)}, y que cos(\frac{\pi}{2^2})=\sqrt{\frac{1}{2}} llegamos a la expresión de la fórmula de Viète.

Un último apunte interesante sobre esta fórmula de Viète. En 1655, John Wallis encontraba el siguiente desarrollo infinito para 2 \over \pi:

\cfrac{2}{\pi}=\cfrac{1 \cdot 3}{2 \cdot 2} \cdot \cfrac{3 \cdot 5}{4 \cdot 4} \cdot \cfrac{5 \cdot 7}{6 \cdot 6} \cdot \cfrac{7 \cdot 9}{8 \cdot 8} \ldots

En principio, ambas fórmulas no parecen tener mucha relación, pero hace pocos años se demostró que no es así. En 1999, Thomas J. Osler publicaba en American Mathematical Monthly una fórmula que incluye como casos particulares tanto a la fórmula de Viète como a la fórmula de Wallis. Podéis ver el artículo en The union of Vieta’s and Wallis’ products for Pi (pdf). También podéis ver comentarios sobre la misma en Historia de las fórmulas y algoritmos para \pi (pdf), de Jesús Guillera, artículo en el que también encontraréis muchas más información sobre el tema.

Y para terminar os dejo enlaces a los artículos publicados en Gaussianos celebrando el día de Pi en años anteriores: