Jugando al Melate con algoritmos genéticos

Hoy, gracias a la ciencia, hemos podido resolver un número enorme de problemas que nos afectan. Hemos entendido por ejemplo, algunas características de los sismos y por ello hemos podido tomar acciones para protegernos. Y esto es sólo una muestra porque la ciencia en general ha trabajado en un sinfín de frentes y se han resuelto problemas que permiten que la vida sea más fácil de vivirla.

Hay problemas, sin embargo, que no aceptan una solución definitiva y que en el mejor de los casos sólo podemos hallar una solución aproximadamente buena. Este tipo de problemas en teoría de la computación se les llaman NP (nondeterministic polynomial time) y su importancia reside en que hay muchos problemas de búsqueda y optimización en donde no hay una solución final. Lo más que podemos tener son aproximaciones. Por ejemplo, el problema del agente viajero, el cual trata de responder a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿Cuál es la ruta más corta posible que el agente viajero puede usar para visitar cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? No existe solución completa y final a este problema y quien lo encuentre bien podría hacer mucho dinero, pues su solución podría permitir implementarla en las empresas de mensajería y así optimizar sus viajes.  

Otro problema NP es el de la mochila, el cual dice: Dado un conjunto de artículos, cada uno con un peso y un valor, determine qué artículos incluir en la colección para que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible. Este tipo de problemas suelen plantearse de muchas maneras, por ejemplo: imagine que tiene una mochila y encuentra una cueva con una serie de objetos de metales preciosos. El problema es que sólo puede llevarse lo que pueda entrar en su mochila. ¿Cómo hacer para llevarse el máximo valor posible (dadas las condiciones iniciales)? Es otro problema que no tiene una solución final y definitiva. La ciencia ha buscado incansablemente maneras de aproximarse al máximo en este particular problema.

Y el tema de la mochila es una mera analogía a muchos problemas de máximos y mínimos que encontramos en el mundo real. De hecho, pensando en esto, el problema de la mochila puede ser usado para intentar hallar los números del Melate a los cuales apostar para tener más chances de ganar. De hecho, en el artículo pasado hablamos de un software que escribí para hallar los números del Melate que aparecen con más frecuencia que otros. La razón para que no salgan con la misma probabilidad esos números es que el azar real, en la tómbola que se usa, hace que quizás –sólo quizás– las diferencias mínimas en el peso de las bolitas (décimas o centésimas de gramos), bien podría hacer que la probabilidad no fuese exactamente de cada número 1/56. Puede ser también que todo esto sea una construcción mental y que simplemente no hay suficientes concursos realizados para que se cumpla la ley de los grandes números, la cual es en realidad un teorema de la estadística que nos dice que el promedio de una muestra (pequeña), tomada al azar de un universo (de gran tamaño), tenderá a estar cerca de la media de dicho universo. 

Como sea, el problema de la mochila puede programarse como un algoritmo genético, un sistema ideado por el biólogo teórico John Holland en los años 70s del siglo pasado, en donde se realizan una serie de pasos en un programa a partir de la evolución biológica y su base genética. Estos algoritmos hacen evolucionar una población de individuos (simulando sus condiciones a través de “cromososmas y genes”), sometiéndola a acciones aleatorias, semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una selección. Se usa una función de “aptitud” (fitness) para establecer qué individuos son mejores que otros. Esto se hace ejecutando repetitivamente el algoritmo genético hasta que se llega a una buena solución o cuando se exceden los recursos de la máquina que está haciendo el proceso. De acuerdo con esto, se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles son los menos aptos, que son descartados.

Entonces, si tenemos el cálculo del porcentaje de veces que salen los números en el histórico del Melate, bien podemos pensar que este porcentaje habla del éxito de esos números para “sobrevivir”, para ser los más “aptos”. Si consideramos que tenemos que elegir 7 números (donde el último es el adicional), basándonos en el porcentaje en el que han salido en los anteriores 1777 concursos, bien podemos pensar que es el equivalente a elegir los objetos más valiosos hallados en una cueva para meterlos en nuestra mochila y llevarnos la mayor riqueza posible dadas las condiciones iniciales planteadas.

Hay en Internet muchos programas y aplicaciones que juegan con el algoritmo genético. Desde luego que dada las condiciones azarosas del concurso del Melate, diferentes programas pueden dar diferentes soluciones. Sin embargo, para ayudarles un poco a mis cuatro lectores, les pondré la lista de números (columna izquierda) y el porcentaje calculado del número de sorteos en el que ha salido cada número (columna derecha):

49 13.77379619

29 13.77379619

54 13.77379619

52 13.71780515

5 13.54983203

50 13.43784994

12 13.3818589

56 13.3818589

43 13.32586786

21 13.26987682

19 13.21388578

40 13.21388578

1 13.04591265

18 13.04591265

15 12.87793953

26 12.87793953

10 12.76595745

24 12.76595745

45 12.76595745

25 12.65397536

33 12.65397536

2 12.59798432

13 12.59798432

17 12.59798432

28 12.59798432

44 12.59798432

48 12.59798432

51 12.59798432

36 12.54199328

3 12.4300112

39 12.4300112

6 12.37402016

32 12.31802912

42 12.31802912

16 12.26203807

46 12.20604703

55 12.20604703

20 12.09406495

8 11.92609183

30 11.92609183

37 11.92609183

47 11.92609183

4 1.87010078

14 11.87010078

34 11.87010078

35 11.87010078

53 11.87010078

38 11.81410974

27 11.7581187

23 11.70212766

9 11.64613662

22 11.64613662

31 11.59014558

7 11.53415454

11     11.53415454

41 11.42217245

Ahora hay que hacer la tarea de buscar qué aplicaciones de algoritmos genéticos pueden hallar en Internet y poner los datos como el sistema que hayan encontrado les exija para que pueda procesarlos. Para darles una idea de los resultados que puede entregar el algoritmo genético, yo usé el programa de Gary Darby, Branch and Bound Algorithm, que aparece en su página www.DelhiForFun.org. Este fue el resultado que el sistema halló: 49, 29, 54, 52, 5, 50 y 12. Ojo, no sé cuál es el número adicional de todos estos y además, considerando los porcentajes, el 12 podría cambiarse por el 56, por ejemplo.

Cabe decir que de nuevo, este trabajo no garantiza que se hará el lector millonario de la noche a la mañana. Simplemente les dará una aproximación que quizás sea mejor que apostar azarosamente a los siete números (o quizás no). Mi sugerencia es que si consideran que todo esto tiene algún sentido y quieren probar suerte, háganlo sistemáticamente cada semana. Es muy, pero muy poco probable, que se ganen el Melate con una primera apuesta al sistema. Si me preguntan, yo apostaría esos mismos números semana a semana por varios meses. En cualquier caso me deslindo de cualquier responsabilidad mía sobre las acciones, apuestas y gastos que tomen los lectores de este artículo. Yo solamente intento usar las herramientas de la ciencia para poder jugar con más chances que si se hace azarosamente. ¡Qué conste!

Cuando el responsable de la pandemia no entiende matemáticas

En el artículo pasado de este blog comenté el tema (de nuevo), de la cantidad de muertos en México debido a la pandemia y las maromas que hacen López Gatell y camarilla para tratar de justificar lo injustificable. Y es que para ello el Dr. Alomía presentó una gráfica en donde se observan los decesos por millón. Cabe decir que medir de otra manera es, según López Gatell, un error metodológico, cuando en realidad, después de lo que voy a decir aquí, se verá que el responsable del manejo de la pandemia es un inepto que para colmo, no entiende de matemáticas.

El asunto es así: en la conferencia diaria vespertina, López Gatell mostró la gráfica de muertos por millón acumulados, por país hasta el 11 de octubre del 2020. El primer lugar lo tiene San Marino, un paisito con menos de 70 kms cuadrados de territorio y con unos 40 mil habitantes. Sus datos muestran 42 fallecimientos pero... ¿por qué López Gatell pone 1,238? Porque lo que hace es una regla de tres... Si 42 muertes corresponden a una población de 40 mil habitantes, entonces ¿cuántos muertos tendrán si tuviesen la población de un millón? Y por eso les da esa escandalosa cifra de 1,238 muertos. Y lo mismo hace con otros países, como Andorra, por ejemplo, que tiene menos de 60 muertos en una población que es de menos de 80 mil personas. Aquí el epidemiólogo indica que por millón de habitantes, el índice de muertos en Andorra es de 712 por millón.

Para ponerlo en perspectiva, toda la población de San Marino (unos 40 mil habitantes), es menos de la mitad de los muertos en México por covid-19. Toda la población de Andorra es menos que los muertos en México por este virus.

Lo que López Gatell usa para ilustrarnos sobre este índice de mortalidad es tramposo y tonto porque el hecho es que Andorra y San Marino tienen 57 y 42 muertos respectivamente. No tiene 1,238 muertos ni 708. Sus poblaciones son mucho menores al millón de habitantes y el índice de Gatell es una estupidez porque no refleja ninguna verdad objetivamente. Lo objetivo, lo real, son 42 y 57 muertos en estos dos países. Lo que piense Gatell sobre si es un error metodológico no hacer las comparaciones por millón es no entender que los modelos matemáticos buscan precisamente modelar el comportamiento de la pandemia y no el hacer numerología para justificar la cifra catastrófica (sic López Gatell), de personas fallecidas en México.

Yo entiendo que López Gatell hizo un doctorado en epidemiología y aparentemente, tuvo que llevar estadística para analizar los datos con los que trabajó para sacar su doctorado. Sin embargo, parece claro que no entiende de números. Por ello, mi recomendación es que deje su frase "sí y sólo sí" y no la use más, porque como él mismo ha dicho, se la robó a los matemáticos. ¿La razón? No entiende López Gatell entre realidad matemática y manipulación matemática. Su ineptitud está a nivel de su grado, es doctoral.

¿Qué números jugar en el Melate para ganar?

Los concursos de azar en general -si efectivamente no hay influencia externa- son un ejemplo perfecto de lo que es la probabilidad. El ser humano se ha preguntado muchas veces sobre qué tan probable es que ocurra un evento en particular, por ejemplo, el tirar una moneda al aire y ver si cae de un lado o el otro. Y se supone que en el mundo de los grandes números, cuando se hacen millones y millones de intentos, la probabilidad de que caiga una moneda de un lado o del otro es del 50%.

Pero esto es el mundo ideal. Hoy, hablando con un par de estudiantes de mi curso de Proceso Digital de Imágenes, discutíamos una idea para hacer más eficiente el algoritmo de búsqueda de la mejor imagen para colocarla en el fotomosaico que tienen que crear. Un alumno de China, Yuguo (yo le digo "Hugo"), junto con Diego, en donde este último halló una idea interesante usando árboles k-dimensionales (), hablábamos de qué enfoque había que usar para la tarea mencionada. A Yuguo se le ocurrió usar un método en donde no encuentra necesariamente la mejor imagen en el fotomosaico, sino un aproximado. Su comentario fue: si hay en un salón tres alumnos de más de 1.80 m. ¿por qué tengo que revisar a cada uno de ellos en su estatura? Digamos que eso -como piensa mi estudiante- es perder el tiempo. Entonces nos indicó a Diego y a mí que busca "el más probable", lo que significa -de acuerdo al algoritmo que parece seguir- tiene alguna manera de buscar en una zona del espacio de búsqueda, ignorando lo demás. Así, encuentra una imagen aceptablemente buena aunque como el mismo Yuguo dijo, "no es la imagen óptima". Le pedí pues que documentara su algoritmo para estudiarlo.

Pues bien, todo lo anterior fue el preámbulo para cuando Yuguo me comentó: "yo creo que la probabilidad está en la cabeza nada más". Y en parte tiene razón. La realidad es que la probabilidad de que caiga una moneda en un intento es exactamente igual a la que tendrá aunque se hayan tirado antes mil millones de veces la moneda. Vamos, no importa que haya salido el mismo lado de la moneda en mil millones de tiros (poco probable, muy poco), el siguiente intento tiene la misma probabilidad de salir "sol" o "águila" (cara o cruz, pues).

Y entonces hablamos de los concursos donde el azar existe. Comentamos el problema del Melate y les comenté que la cantidad de concursos llega a apenas a menos de 4000. Estos no son los grandes números en donde, si es un concurso totalmente azaroso, el porcentaje de que salga un número es 1/56. Así de simple. Pero resulta que hay muchos números que han salido con frecuencias diversas. Este es el resultado que me entrega el software:

Frecuencias/Números (de mayor a menor) con 7 números.

507 veces - 32
505 veces - 12
503 veces - 37
497 veces - 13
495 veces - 20
492 veces - 5
488 veces - 36
487 veces - 16,33
485 veces - 2,7
484 veces - 15,28
483 veces - 11,19,25
482 veces - 30
481 veces - 1,18
475 veces - 14,29
473 veces - 9
471 veces - 8
470 veces - 6
469 veces - 17
466 veces - 3,27
464 veces - 4,39
463 veces - 21,38
462 veces - 22,24
458 veces - 26
456 veces - 31,34
451 veces - 10
444 veces - 35
432 veces - 23
406 veces - 40
385 veces - 43
380 veces - 44
373 veces - 42
350 veces - 41
229 veces - 45
228 veces - 47
212 veces - 46
192 veces - 49
189 veces - 48
175 veces - 51
173 veces - 50
161 veces - 56
154 veces - 52
151 veces - 55
150 veces - 54
135 veces - 53

Si consideramos esta tabla, veremos que números como el 32, el 12, el 37, el 13, el 20 y el 5 han salido con mucho más frecuencia que el 53, 54, 55, 52, 51, 48, 10 entre otros.

¿Por qué ocurre esto? Hay dos posibles razones: la primera es que la ley de la probabilidad, en este caso 1/56, se aplica a los grandes números, a hacer estos sorteos millones y millones de veces y aún así, no sé qué signifique exactamente "los grandes números", es decir, en qué momento llego a esa cifra... La segunda es que efectivamente, como Yuguo me decía, la probabilidad es un constructo humano y es una observación que queremos suponer que en general es cierta, aunque esto ocurre en el mundo ideal y no en el mundo real, en el que vivimos y en donde la diferencia de pesos (aunque sean décimas de gramo) de las bolitas que se ponen en el sorteo, puede hacer la diferencia que muestre las razones por qué el 10 sale una tercera parte de lo que sale el 12, por ejemplo.

Entonces, si hay que establecer un criterio, si pensamos que en estos "grandes números", las probabilidades eventualmente se igualarán, podemos pensar que menos de 4000 concursos (desde 1984), no caen ni remotamente en esta ley de los grandes números y por ende, pensar que los números que no han salido ahora sí saldrán con más frecuencia, es simplemente creer que estamos en el mundo ideal de la probabilidad.

Así pues, ¿quiere ganar el Melate? Desde luego que tendrá que tener un golpe de suerte porque como indicamos al principio del artículo, si es al azar realmente cada número debería tener 1/56 de posibilidades de salir (aunque pensándolo bien, el primer número tiene 1/56 chances de salir, el segundo 1/55, el tercero 1/54, etcétera). Pero en términos generales, los concursos ocurren en el mundo real y aunque sí, los números por salir son "igualmente probables" (en el mundo ideal), en el real se notan preferencias debido a la "imperfección de la realidad". Consecuentemente, la mejor apuesta debe ser a los números más frecuentes.

Desde luego -y antes de que alguien venga a reclamarle que no ganó el Melate- esto es meramente una especulación que busca ser educada, es decir, basándose en hechos. Y vuelvo a elaborar: las pelotitas del concurso real pueden no tener estrictamente el mismo peso y una diferencia de décimas de gramo entre una y otra pudiese hacer que una esfera saliese más veces que las otras, aunque evidentemente, no puedo afirmar que esto ocurra por esta razón.

Reflexiones sobre el concurso de la catafixia de Chabelo

El problema planteado hace un par de artículos ha generado en facebook, particularmente, una interesante discusión. Después de un largo intercambio de bytes me quedo con la idea que todo el problema tiene que ver con el hecho de tomar a todo el concurso como uno solo o bien, dividirlo en dos, uno de tres puertas y después uno nuevo de dos puertas. Paul Erdös, que de matemáticas probablemente sabía más que todos mis lectores y yo juntos, sospechaba que la respuesta de 2/3 de la teoría de juegos estaba equivocada. Sin embargo, Erdös dejó por la paz este problema después de que alguien le mostró una simulación donde este 2/3 se cumplía estadísticamente.

Desde luego que una simulación no es una prueba de nada y sóo marca tendencias. Yo tengo sin embargo algunas cuestiones que los defensores del resultado que da la teoría de juegos no puede responder. Estos son mis razonamientos:

Concurso único: Chabelo me pide decidir sobre 3 posibles puertas donde hay un premio. Elijo la 1. Entonces una vez hecho esto, Chabelo me dice: "voy a abrir la 3, porque ahí no hay premio". Y me pregunta entonces: "¿quieres cambiar la puerta 1 por la 2?". El problema es saber si cambiar me da alguna ventaja. Los resultados mostrados en la teoría de juegos es que sí conviene, pues teniendo 1/3 de la puerta que abrió más el cambio de la puerta a la 2, me da 2/3. Si no cambio, sigo con mi elección inicial y no saco ventaja de que se quitó la puerta 3, por lo que sigo con mi 1/3 de chances de ganar..

Pero éste es el problema. Veamos el siguiente escenario. Chabelo me pide elegir una puerta, elijo la 1. Chabelo entonces me dice: "Vamos a otra parte del estudio". En la otra parte del estudio hay sólo dos puertas. El premio se mantiene en el mismo lugar que en primer concurso. No hay cambios, puede estar en la puerta 2 o 1 como originalmente estaba. Nada ha cambiado con respecto a la configuración inicial. Pero ojo, estamos en un nuevo estudio con sólo dos puertas. Chabelo entonces me dice: "en el concurso anterior decidiste la puerta 1 y ésa es la puerta que voy a decir que decidiste en este nuevo concurso. Te doy chance de que cambies por la puerta 2". ¿Debes cambiar? ¿No es un nuevo concurso en donde sólo hay dos puertas? La diferencia con el ejercicio original es que Chabelo no me dice que quita la puerta 3, sino que se va a otra parte del estudio, donde hay dos nuevas puertas (repito, los premios siguen en el lugar que originalmente estaban) y me pregunta si del concurso anterior, que elegí la puerta 1, me sostengo en esa decisión o cambio. Aquí es un concurso de 50% de probabilidades. Sólo son dos puertas. El otro concurso quedó atrás. Por eso no se "acarrea" o se "hereda "la probabilidad. Yo pregunto ¿dónde está el error en considerar que son dos concursos?

Por otra parte, imaginemos que hay dos concursantes, no 1. Y que el concursante A elige la puerta 1 y el concursante B elige la puerta 2. Chabelo quita la puerta tres y les pregunta a ambos concursantes: "¿quieren cambiar de puerta?". Asumamos que los dos concursantes conocen el resultado de teoría de juegos y ambos deciden cambiar simultáneamente. Entonces, de acuerdo a eso, cada uno de ellos tiene 2/3 de probabilidades de ganar. ¿Cómo puede ser eso? la suma de las probabilidades de los dos concursantes excede la probabilidad total. Explíquenme cómo puede pasar eso?

Pero pongo un escenario más: asumamos que no tengo tres puertas, sino un millón. El concursante elige la 1 y Chabelo me quita 999998 puertas que no tienen premio y me pregunta si quiero cambiar de puerta. ¿si cambio tengo 999999/1000000 de ganar? Finalmente, si hacemos una simulación de esto, en un millón de puertas, puede quedar el premio en la que quieran. Si quito 999998 puertas, quedan dos. Es un volado. Si cambio de puerta, con esa probabilidad estoy en plena certeza de que ganaré. Pero eso es ridículo, porque estoy jugando a que está en la puerta 1 o 2. 50%.

Pero va un planteamiento todavía más escabroso: Cuando Chabelo hace el concurso, él sabe que va a quitar una puerta. No importa la que elija el concursante, Chabelo quitará una puerta del mismo y a priori sabe eso. No tiene importancia qué puerta quita con tal de que quite una que desde luego, no contenga ningún premio. Si Chabelo sabe desde antes que una puerta será eliminada, ¿no estamos ante un concurso de dos puertas, con 50% de acertar correctamente? Y esto plantea algo interesante en sumo grado: para el concursante al elegir la primera vez tiene 1/3 de chances de acertar correctamente, pero Chabelo, que conoce el mecanismo de qué puerta va a quitar a priori, puede verlo como un concurso de dos puertas, porque para él, solamente hay dos puertas en juego. Entonces para Chabelo este es un concurso de 1/2 de probabilidad de acertar o fallar. Y entonces llegamos a la parte complicada ¿es acaso el cálculo de la probabilidad del concursante una maquinación del cerebro para explicarse sus posibilidades de ganar? ¿No será que la probabilidad es un inveto humano para trabajar con el intratable azar? ¿No es finalmente como la matemática, un invento humano? Porque ¿cómo podría ser diferente la probabilidad de Chabelo a la del concursante? ¿porque tiene el conocimiento que quitará una puerta? Esto me parece más asombroso que todo el problema planteado.

Así pues, quien tenga algo que decir explíqueme qué está mal en todos estos razonamientos. No me digan: "es que cambiaron las condiciones", porque no es cierto, siguen siendo las mismas. No me digan: "es que ya lo que dices no es un juego de teoría de juegos". eso no es argumento. Lo interesante en principio es darme la razón lógica atrás del acarreo del resultado anterior, del pensar que sigue siendo el mismo concurso. ¿Estamos?

Enigma lógico

En la página de Chessbase, se hace cada año un concurso de problemas. Debido a los motores de ajedrez, los retos a resolver son muchas veces mates ayudados o enigmas de lógica y no necesariamente de ajedrez. En el del año pasado, leo el siguiente:

Brain puzzle 1: Jack loves Mary; Mary loves Peter. Jack is married, Peter is single. In this group does a married person love an unmarried person? – This puzzle was given to us by Nick Carlin during a visit in 2012 to Bletchley Park. Nick is a computer chess expert and was involved in the Rybka program.
Traducción: Jack ama a María; María ama a Peter. Jack está casado, Peter es soltero. ¿En este grupo hay una persona casada que ame a una persona soltera? El problema lo puso Nick Carlin durante una visita en el 2012 a Bletchley Park. Nick es un experto en cómputo y estuvo involucrado en el programa Rybka.

Veamos la lógica del asunto:Hay dos hechos: Jack está casado y Peter está soltero. Si María es soltera, entonces sí, hay en ese grupo alguien casado que ama a alguien soltero. Si María es casada entonces de nuevo se cumple la condición de que alguien casado ama a alguien soltero. En otras palabras, no importa el estado civil de María, la condición siempre se cumple.

¿Alguien encuentra otro posible razonamiento?

Estereotipos de belleza, la ciencia y la cirugía estética

"La belleza está en los ojos que la mira", dice una frase popular y bien podríamos ir más allá con esta frase: "me gusta esa mujer porque es bonita o es bonita porque me gusta". El punto es que en parámetros de la belleza, en la estética, no pareciera posible ponerse de acuerdo. No obstante eso, los seres humanos hacemos concursos de belleza, en donde se evalúa la hermosura de las mujeres que en ellos participan. Tenemos Miss Universo, Miss Mundo (debiese ser "señorita Universo, señorita Mundo" ¿no?), etcétera y en general las ganadoras son mujeres bellas, pero en muchos sentidos con parámetros de belleza occidentalizados.

Las métricas usadas para medir la belleza femenina no son universales y cambian con los tiempos. Antes, las mujeres rollizas eran "más hermosas", pues estar gordito -se pensaba- era signo de salud. Hoy sabemos lo contrario y entonces se hace énfasis en mujeres delgadas, pero van más allá y las hay ultradelgadas, las cuales normalmente implican problemas de salud, como la anorexia o bulimia. Digamos que la belleza oscila entre los extremos y el justo medio no se encuentra jamás.

La cuestión es que se ha desatado una polémica en Corea, pues las participantes de "Miss Korea 2013", probablemente por retoques de cirugía estética, están convergiendo todas al mismo rostro. Vamos, las 20 participantes parecen ser una misma. En el blog del coreano JB Huang, se hace un interesante análisis al respecto. El autor del blohg tomó las 20 imágenes de las concursantes, normalizó los rostros y los alineó en un GIF animado, como puede verse aquí abajo:

El autor del estudio retomó lo aprendido en un curso de fotografía computacional y usando una serie de algoritmos, hizo un "morphing" del rostro promedio de las concursantes, lo que proceso finalmente en un video donde se muestra como los rostros de las concursantes cambian. Bueno, decimos que cambian pero parece ser casi la misma persona, el mismo rostro.

JB Huang no se quedó, sin embargo, con este solo resultado, sino que tomando eigenvectores y eigenvalores para los rostros de las concursantes  y usando el principio de análisis de componentes (PCA - por sus siglas en inglés), llegó a resultados muy interesantes, por ejemplo, que el promedio de eigenvalores de las fotos es 6. Con esto, se pudo analizar cómo los rostros se distribuyen en un eigenespacio y halló la similitud de las concursantes entre ellas.

Concursantes 1, 2 y 3, respectivamente

Con esta información, se intentó construir una matriz de afinidades la cual muestra qué tanto se parecen las concursantes entre sí (mientras más azul, más parecidas son). De esto se concluyó que las concursantes con rostros más diferentes a las demás fueron la 1, 2 y 6.

Así pues, aunque la ciencia descubre información que revela porqué las concursantes parecen ser muy parecidas, a ojo de buen cubero nos podemos dar cuenta de los parámetros que hoy en día se usan para valorar la belleza de las "misses".

Eficiencia en cómputo y resultados del reto Collatz

Actualmente tenemos programas que hacen un sinfín de tareas. Muchos de ellos -sino es que la mayoría- usan una interfaz gráfica para que los usuarios puedan tomar decisiones a través de botones, listas de opciones, etcétera. La interfaz gráfica se impuso por su facilidad de uso y el modo texto, o consola, fue desapareciendo poco a poco. Y aunque aún existe en los sistemas de cómputo, ya prácticamente todos los sistemas operativos utiliza una interfaz gráficaz, que se monta al arrancar el sistema y que ya está fusionado con la parte de interacción gráfica.

Pero ¿qué tanto influye la interfaz gráfica en el desempeño de un equipo de cómputo? ¿Cuántos recursos más requiere para correr un programa con relativa velocidad? Es una pregunta interesante y que a veces nos olvidamos de ello pues es claro que ahora las máquinas corren a unos 3 GHz y tienen 2, 4, 8 o más Gbytes de memoria. De hecho, cuando había computadoras de 8 bits y algunos intentos rudimentarios de interfaz gráfica (como el MousePaint de Apple //e), era claro que las limitaciones del hardware eran demasiadas.

Gracias a los avances en este rubro, parece que podemos tener una hermosa interfaz gráfica con el usuario y un desempeño fenomenal, pero aunque lo parezca, no es así. Hace unos días convoqué, vía este medio, a un reto de programación. Se trataba de hallar la secuencia más larga de números de Collatz. Hubo bastante aceptación de este "concurso" y he recibido una veintena de programas.

El reto en particular era hallar la secuencia más larga en un número del 1 al millón. Originalmente tomé mi código para calcular la secuencia de Collatz de un número y lo puse en forma de ciclo para que calculara todas las secuencias de 1 al millón. Como el programa trabajaba con una biblioteca para manejar números extremadamente grandes (más de 1000 cifras), el programa -al ejecutarse- tardaba más de diez minutos. Mi software desplegaba toda la secuencia para cada número y esto, evidentemente lo hacía muy lento.

Como en el reto sólo se pide hallar la secuencia más larga, no hay necesidad de desplegar cada cálculo que la máquina hace. Así, quitando el despliegue de esta información, el programa tardaba la mitad, es decir, unos 5 minutos. Aún así era lento. Vi programas de algunos de los participantes que tardaban menos de 15 segundos. ¿Cómo hacer para que mi programa corriera más rápido? Quité entonces la biblioteca de números grandes y usé el tipo predefinido LongInt. El programa, sin embargo, se atoraba en el número 999216. Vi la referencia y hallé que los LongInt aceptan números entre -2147483648 y 2147483647. Como algo estaba pasando, cambié las definiciones de los números a usar a LongWord, que aceptan valores entre 0 y 4294967295 y entonces mi programa corrió. Tardaba ahora alrededor de un minuto para hallar la secuencia pedida.

Pero ¿se podía ir más allá? La solución era hacer un programa que corriera sin necesidad del "overhead" que le mete la interfaz gráfica. Delphi permite crear aplicaciones que corran en modo consola/terminal. Se quita pues la sobrecarga que le impone la interfaz gráfica a todos los programas. Escribir código para aplicaciones sin interfaz gráfica es equivalente a escribir código en TurboPascal realmente. Con esto en mente, pasé mi programa más rápido a uno que no usara la interfaz gráfica. Así entonces, el programa no muestra los cálculos que hace. Sólo informa el resultado final. ¿Tiempo para hallar la secuencia más larga de Collatz? ¡Menos de 1 segundo! Sorprendente.

Desde luego que estos resultados pueden variar de acuerdo a la computadora que se esté usando, pero en esencia se mantiene la misma relación de velocidades. En conclusión, es claro que la interfaz gráfica hace muy lento, demasiado lento, el procesamiento de información. No pensaba que fuese tan grande esta sobrecarga, pero los números así lo indican. He aquí mi código en Delphi 7 (ejecutable disponible pidiéndomelo a mi correo morsa@la-morsa.com):

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  MaxNum    : LongInt; // núm máximo
  Contador  : Integer;
  Numero    : LongWord; //núm con la secuencia más larga
  Num1      : LongWord;
  NuevoLong : LongWord;
  NuevoCont : integer;

// Números de Collatz: Encontrar la máxima secuencia usando
// LongInt en lugar de la biblioteca de números grandes
// el programa se escribió en modo consola para evitarse el
// overhead que le mete la interfaz gráfica

procedure Calcula;
begin
  write('dame número máximo a calcular ');
  Readln(Num1); //leo el máximo número a calcular
  MaxNum := Num1;
  NuevoLong := 0;
  Contador := 0;
  NuevoCont := 0;
  repeat
    repeat
      if Num1 mod 2 = 0 then Num1 := Num1 div 2
                        else Num1 := (Num1 * 3) + 1;
      inc(Contador);
    until Num1 = 1;
    if Contador > NuevoCont then
    begin
      NuevoLong := MaxNum;
      NuevoCont := Contador;
    end;
    Contador := 0;
    dec(MaxNum);
    Num1 := MaxNum;
  Until MaxNum = 1;
  Writeln('Número: '+inttostr(NuevoLong)+ ' iteraciones: ' + inttostr(NuevoCont));
  readln;
end;

begin //main
  Calcula
end.

  Cabe señalar que hubo diferentes lenguajes en uso: Delphi, C++, C#, Ruby, Javascript, Java y Python. A pesar de ser interpretados algunos de estos lenguajes, su desempeño es estupendo, aunque me parece, no pueden competir con el compilador que genere código nativo y que además tiene, muchas veces, directivas para optimización. En este reto en particular, la velocidad para hallar la solución era el factor ganador. Sin embargo, en cualquier caso, es interesante ver el desempeño de varios de los lenguajes en boga. Una vez dicho esto, van los resultados del reto de la secuencia más larga en los números de Collatz, de 1 a un millón:  

• Juan Claudio Toledo 00.029 segundos (primer lugar)  
• Nayely Riverón Domínguez 00.047 segundos (segundo lugar) 
• José Raúl Escobedo Arreola 00.053 segundos 
• Darío Alvarez Aranda 00.164 segundos 
• Fabían Vargas Quijano (*) 00.200 segundos
• Carlos Torres Almonte 00.310 segundos 
• Kevin Reyes 00.320 segundos  
• Manuel López Michelone 00.420 segundos (fuera de concurso) 
• Luis Alfredo Juárez Blanco 00.640 segundos 
• Carlos Morales 00.699 segundos 
• Cyb3rxPuNk . 01.010 segundos 
• Eleazar Prieto 01.130 segundos 
• Ricardo Padilla Amezcua 02.324 segundos 
• Gerardo Robledo 03.300 segundos 
• Luis Rivera 05.638 segundos 
• Rafael Mendoza 06.540 segundos 
• Francisco Pérez 06.790 segundos 
• lugo tache 07.320 segundos 
• Eduardo Ruíz 07.490 segundos 
• David Garza 09.000 segundos 
• Ernesto Valderrama Blum 36.070 segundos 
• Roberto López Bedolla 36.350 segundos 
• Gabriel Romero 41.200 segundos 
• Rockodev 110.720 segundos 
• Juan Rafael Corrales más de 5 minutos 
• Cristian Castro Cienfuegos N/A (**)  

(*) Vargas Quijano incluyó en el envío de su programa, un estudio sobre una forma de optimizar el problema para que busque de manera más inteligente. Muy interesante enfoque, sin duda.

(**) Nunca pude correr su programa. Mi sistema decía que faltaba un archivo dll que busqué, descargué y puse en mi sistema, pero jamás lo reconoció o algo extraño pasó.

Juan Claudio Toledo, ganador del reto de Collatz

Me dice Juan Claudio Toledo, que está terminando su doctorado en la UNAM, (el ganador de este reto), en el correo en donde me mandó el programa, los siguiente:  

Me di cuenta que la respuesta al problema debe ser siempre > N/2. Es decir, el entero entre 1 y N con mayor ciclo debe estar en la segunda mitad del intervalo [1,N]. ¿Por qué? Acá lo demuestro, por reducción al absurdo.  

Sea x el entero entre 1 y N con mayor ciclo. Supongamos que x <= N/2. Puedo definir y = 2*x; como x <= N/2, tenemos que y <= N, por lo que y es también un candidato. Pero como y es par, la primera iteración del algoritmo empezando en y nos daría y/2 = x, y llegamos a x. De ahí la secuencia iría igual que si se empezara en x. Debido a esto, el ciclo de y es un paso más largo que el de x. Entonces x no es el entero de mayor ciclo, y se llega a una contradicción. Por lo tanto, x debe ser mayor que N/2.  

Modifiqué el programa para que buscara a partir de N/2+1, pero me salió un tiempo más grande. La razón: estoy usando un cache para recordar los valores ya calculados, pero en este caso nunca se calculan los ciclos de números menores que N/2. Y pues esos valores se usan bastante. Empezando desde cualquier número, la secuencia debe pasar *al menos* log_2(N/2)~18 veces por números en la primera mitad. De forma que al hacer este cambio, aunque calculo sólo la mitad de los casos, me cuesta más pues no aprovecho tanto el cache.

Así entonces, como podrán ver, esta conjetura de Collatz tiene mucha tela de donde cortar. Con respecto al reto me gustaría hacer algunas aclaraciones:

• Los tiempos los medí en mi computadora, con un procesador AMD de seis núcleos y sistema operativo Windows 7 de 64 bits. Puede haber máquinas en donde los concursantes probaron y sus programas corrieron más rápido que lo que mi máquina reporta. Los tiempos para el reto se miden desde mi máquina.
• El fallo es inapelable. Este es un concurso hecho de buena fe, tanto por quienes participan en él como yo, quien evalúa los resultados de la manera más legal y justa posible. Aún así y para que no quede duda: los resultados son inapelables y definitivos.
• Los premios tienen como objetivo motivar a quienes quieren concursar, pero desde luego, solamente es una motivación extra. Lo importante aquí es mostrarse como un programador que puede ser mejor que los demás en eficiencia, en maneras de resolver un problema de programación.
• Cuando quise probar algunos de los programas hubo errores. Por ejemplo, no hacían correctamente el cálculo. En su momento les indiqué a los concursantes con estas dificultades sobre los problemas de su software y les pedí que me mandaran las versiones corregidas. Quienes por alguna razón no me las mandaron, simplemente quedaron fuera del reto.
• Sobre los ganadores: El primer lugar, tiene derecho a elegir el premio: la taza con el logo de La_Morsa o la tarjeta SD de 4 GB. Me pondré en contacto por correo electrónico con los ganadores para darles su premio y que me den una foto para ponerlos en la galería virtual de honor. Felicidades. La verdad me satisface mucho ver que hay tanto empuje y tan buenos programadores en este país. Me tiene muy contento eso. Agradezco la entusiasta participación y prepárense para el siguiente reto.

Los programas ganadores (el código fuente), son los siguientes:

Programa de Juan Claudio Toledo:

/************************************************************\
* collatz.cpp                                                *
*                                                            *
* Autor: Juan C. Toledo                                      *
* Fecha: 13 de marzo de 2013                                 *
*                                                            *
* Encuentra el entero entre 1 y N con el ciclo mas largo,    *
* bajo el algoritmo de la conjetura de Collatz. Emplea       *
* memoization para optimizar la busqueda.                    *
*                                                            *
* Copyright 2013 Juan C. Toledo                              *
*                                                            *
* Este archivo es parte de collatz.                          *
*                                                            *
* collatz es software libre: usted puede redistribuirlo y/o  *
* modificarlo bajo los términos de la GNU General Public     *
* License, publicada por la Free Software Foundation, ya sea *
* la versión 3 de la licencia, o (a su opción) cualquier     *
* versión posterior.                                         *
*                                                            *
* collatz se distribuye con la esperanza de que sea útil,    *
* pero sin ninguna garantía; ni siquiera la garantía         *
* implícita de comerciabilidad o idoneidad para un propósito *
* PARTICULAR. Consulte la GNU General Public License para    *
* más detalles.                                              *
*                                                            *
* Usted debe haber recibido una copia de la GNU General      *
* Public License junto con Foobar.                           *
* Si no, véase http://www.gnu.org/licenses/                  *
\************************************************************/

#include < stdio .h >;

int main () {

  // ======================
  // Configuracion
  // fijar verbose a false para mejorar el tiempo de ejecucion
  
  const int N = 1000000;
  bool verbose = false; 

  // ======================

  int ciclos[N+1];
  int i, pasos, maxpasos, maxnum;
  long int x;

  // Calculamos para todos los enteros desde 1 hasta N
  maxpasos = 0;
  maxnum = 0;
  for (i=1; i<=N; i++) {

    // Bucle que simula el juego
    x = i;
    pasos = 0;
    while (x!=1){
      // Si x es menor a i, ya hemos calculado su ciclo
      if (xmaxpasos) {
      maxpasos = pasos;
      maxnum = i;
      if (verbose) printf(" Nuevo record!");
    }
    if (verbose) printf("\n"); 
  }

  printf("Ciclo mas largo (n<=%i): ",N);
  printf("%i con %i pasos\n",maxnum,maxpasos);
  
  return 0;
}

Nayely Riverón Domínguez, segundo lugar en el reto de Coillatz

El código de Nayely:

    
#include < stdio .h >;
    #include < stdlib .h >;
    #include < time .h >;

    int main(void){
         unsigned long tope=1000000, iteraciones=0, i=0, num=0, iteracion_mayor=0, numero_mayor=0;
         int *iteraciones_totales;
         
         printf("Ingrese tope: ");
         scanf("%lu",&tope);

         clock_t t_ini, t_fin;
         double secs;
         t_ini = clock();
         
         size_t tamanyo=tope;
         iteraciones_totales = (int *)malloc( tamanyo*sizeof(int) );
         
         for(i=1;i<=tope;i++){  
            iteraciones=0;            
            num=i;
            while (num > 1) {
                    if(numiteracion_mayor){
                     iteracion_mayor=iteraciones;
                     numero_mayor=i;
            }
            
         }
         
         printf("DEL 1 AL %lu\n\nNumero: %lu\nIteraciones: %lu\n\n",tope,numero_mayor,iteracion_mayor);
         
         t_fin = clock();
         secs = (double)(t_fin - t_ini) / CLOCKS_PER_SEC;
         printf("El tiempo de calculo fue: %.16g milisegundos\n", secs * 1000.0);

         
         getche();
         free(iteraciones_totales);    
         
         return 0;
    }

Otro reto con la conjetura de Collatz

La conjetura de Collatz es muy sencilla y cualquiera puede entenderla: elíjase un número entero positivo. Si es par, divídalo entre dos; si es impar, multiplíquelo por 3 y súmele uno. A ese resultado proceda de la misma manera. Así, si tomamos, por ejemplo, el número 10, tendremos que es par, entonces dividiremos entre 2, lo cual nos da 5. A ese resultado, multipliquemos por 3 y sumémosle 1. Tendremos como resultado 16. Como es par, entonces tendremos 8, siendo par este dividimos de nuevo entre dos y obtendremos 4. Hacemos de nuevo la división y hallamos 2. Dividamos de nuevo y obtendremos 1. Decimos entonces que 10 es un número maravilloso o de Collatz.

Llegar a probar que 10 es maravilloso lleva 6 pasos: 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1. El número 27, por ejemplo, requiere de 111 iteraciones antes de llegar a 1 y es el número de más iteraciones menor de 50. Cuando John Conway (el creador del juego de la vida) explica la conjetura pasa al pizarrón y dice: "veamos qué pasa si usamos un número al azar… digamos 27"…

Se me ha ocurrido un reto de programación, el cual es hacer un programa que nos diga cuál es la secuencia más larga para llegar a 1 -en la conjetura de Collatz, desde luego- que tienen los números del 1 a un millón. El resultado que el programa debe otorgar es cuál número, en el intervalo [1 .. 1,000,000] tiene la secuencia más larga. Cabe decir que hay dos premios fastuosos: una tarjeta SD de 4 GBytes y una taza con el logotipo de La_Morsa. El programa que llegue al número con la secuencia más larga en el menor tiempo posible, se llevará uno de esos premios (eso lo decide el ganador). El segundo lugar, es decir, el segundo mejor tiempo que llegue a la respuesta correcta, se llevará el premio sobrante. Cabe señalar que los programas que se remitan a mi cuenta de correo deben tener el código fuente y las instrucciones precisas para que los pueda probar. Habiendo tantos compiladores y diferentes sistemas, deben decirme qué hacer para compilar y correr el código a concurso (añadiendo una copia del ejecutable).

Así que a afilar sus armas. A programar y a optimizar. Veamos qué dicen nuestros programadores. Yo ya escribí mi propia versión para resolver este problema. A quien le interese el software, puede pedírmelo a morsa@la-morsa.com y a vuelta de correo tendrá el enlace para descargarlo.

Encuentran el número primo de Mersenne 48

En 1644 Mersenne conjeturó que los números de la forma 2ⁿ – 1 eran primos, donde n es un primo. W. W. R. Ball llamó a éstos Números de Mersenne y hasta la fecha los esfuerzos para demostrar esta conjetura han sido vanos De hecho, no se conoce cómo llegó Mersenne a este resultado, ni para cuáles condiciones se cumple Inclusive, hasta 1962 el primo más grande conocido era 2⁴⁴ – 1, el cual es, en sí, un número de Mersenne y consta de aproximadamente 3000 cifras.

Hay una larga historia de los primos de Mersenne, la cual comenzó en 1456 y que sigue hasta nuestros días. Se conocen 47 números primos de Mersenne (el último tiene como n = 43112609, y consta de 12,978,189 de cifras. Fue hallado en el 2008 gracias a los esfuerzos de Smith, Woltman y Kurowski usando GIMPS y PrimeNet, utilizando Prime95, una aplicación gratuita escrita por George Woltman, que es usada por GIMPS (Great Internet Mersenne Prime Search), como un proyecto distribuido dedicado exclusivamente a hallar nuevos primos de Mersenne. Prime95 se refiere al software de Windows y Mac OS X, pero hay una versión para Linux, MPrime, que funciona usando la consola, la línea de comandos. Es idéntica a Prime95, pero no tiene una interfaz gráfica como en sus contrapartes Mac y PC.

Los primeros números de Mersenne, de la forma 2ⁿ - 1 son 3, 7, 31, 127, y estos son fáciles de probar en su primalidad porque se pueden hacer las divisiones con los números anteriores al que estamos probando, pero para números muy grandes, el hacer este proceso podría llevar demasiado tiempo. Sin embargo, tenemos buenas noticias para los primos de Mersenne y es que hay una prueba rápida, llamada prueba de Lucas-Lehmer, con la que puede saberse si un número es primo o no. El primo de Mersenne 48 fue hallado por Curtis Cooper, un matemático de la Universidad de Missouri Central. Aquí hablamos de 2^57,885,161 - 1 y es un número de Mersenne que tiene 17,425,170 de dígitos.

El resultado se obtuvo usando los servidores distribuidos GIMPS. Este proyecto de cómputo distribuido se diseñó para "cazar" los primos de Mersenne y es responsable de descubrir los últimos 10 primos de Mersenne, habiéndose hallado en el 2008 el número 47. GIMPS corre en cerca de 1000 computadoras en diversas universidades y para hallar el primo 48 se necesitaron 39 días de cálculos.

Se verificó el resultado usando un servidor de 32 núcleos en seis días. El descubrimiento hace acreedor a Cooper a un premio de 3,000 dólares, dado por el propio proyecto GIMPS, pero no compite con el premio de la EFF (Electronic Frontier Foundation), que ofrece 150,000 dólares por el primer primo con al menos 100 millones de dígitos, y 250,000 dólares por descubrir el primer primo con al menos mil millones de dígitos. Es interesante hacer notar que desde el punto de vista de la programación, los números de Mersenne son muy simples.

Por ejemplo, en su forma binaria, los tres primeros son 11, 111, 11111, etcétera. En general, 2ⁿ-1 es simplemente un número binario con n unos. El hecho es que tenemos primos de Mersenne para n=31, 61 y 127 y frecuentemente son muy útiles cuando se necesita un primo rápidamente. Finalmente, ¿cuáles son todas las cifras del primo 48 de Mersenne?

En el sitio Programming Praxis se reta a los lectores (programadores) a que generen los 17 millones de dígitos. Un programa simple en C no puede hacer esto porque los tipos de los enteros tienen limitaciones evidentes. Pero tal vez usando una biblioteca de números muy grandes, como la Multiple Precision Library de GNU podría ser de gran ayuda.

Un vegetal fractal al alcance de todos

Hoy hallé en la sección de frutas y verduras algo fascinante: el romanescu. Jamás había visto semejante vegetal en los supermercados y es impresionante porque es en realidad una imagen tridimensional de un fractal. Este es uno de los ejemplos más llamativos de que la Naturaleza, sí, con N mayúscula, está seriamente involucrada con los fractales, descubiertos, o inventados (¿?) por Mandelbrot. El romanescu es una estructura cónica con protuberancias también cónicas más pequeñas que se forman a su vez de otras estructuras cónicas, y así sucesivamente. Esto se entiende con el término “autosimilaridad” .

El romanescu (Brassica oleracea), es un híbrido de brécol (Brassica oleracea var. italica) y coliflor (Brassica oleracea var. botrytis) de la familia de las brasicáceas. El brécol romanescu fue documentado inicialmente en Italia (como Broccolo romanesco) en el siglo XVI. Como todas las especies de esta familia, es rico en vitamina C, fibra soluble y carotenoides. Se suele consumir cocido o al vapor aunque también se suele utilizar como verdura cruda. Una de sus más llamativas características es que presenta geometría fractal en su estructura.

De acuerdo con la Wikipedia: Un fractal es un objeto geométrico cuya estructura básica, fragmentada o irregular, se repite a diferentes escalas. El término fue propuesto por el matemático Benoît Mandelbrot en 1975 y deriva del Latín fractus, que significa quebrado o fracturado. Muchas estructuras naturales son de tipo fractal. La propiedad matemática clave de un objeto genuinamente fractal es que su dimensión métrica fractal es un número no entero.

Como los fractales tienen unas matemáticas asociadas muy claras, existen muchos programas para generarlos con la computadora. Lo interesante es al final de cuentas entender que esto es un modelo que la naturaleza expresa en fenómenos cotidianos. Existen muchos programas para crear fractales, pero la mayoría trabaja con autómatas celulares undimensionales, conjuntos de Julia, etcétera. No he hallado, de hecho, un programa que haga fractales al estilo de la verdura Romanescu.

Sin embargo, hallé en esta página un interesante ejemplo utilizando las capacidades de scripting de Renderman, el programa de gráficas tridimensionales de Pixar, con el que se han generado muchas de las imágenes de películas como Toy Story, Cars, Monsters Inc., etcétera. El autor de la página eligió precisamente la verdura romanescu, la cual está compuesta de espirales colocadas en segmentos que son idénticos de toda la planta. El proceso continúa hasta el infinito como una forma fractal en 3D. “La belleza matemática y la simplicidad de esta verdura no deja de asombrarme”, escribe el autor de ese sitio web.

De acuerdo con Alexandar Rodic, el rendereo de cuatro generaciones de brócoli (porque el romanescu es un brócoli), es extremadamente lento por el inmenso número de conos (unos 1600 millones de conos cuadráticos). Las imágenes finales se renderizaron con After Effects.

Cuando vi el romanescu me la compré (24.90 pesos) sin pensarlo demasiado y más adelante Pilar Doporto tomó las magníficas fotos que ilustran este artículo. Si quieren ver en vivo este vegetal, vaya a su supermercado más cercano). Vale la pena el gasto simplemente por el valor estético visual de este fractal natural.

El juego de la vida de Conway

 

Hay un juego de computadora fascinante, llamado Juego de la Vida, el cual fue diseñado en 1970 por el matemático británico John Horton Conway, de la Universidad de Cambridge, Inglaterra. Se hizo muy popular desde que Martin Gardner, en su columna de octubre de ese año en la revista Scientific American hablara de las ideas de Conway. Y a partir de ese momento miles de programadores lo codificaron y jugaron con las ideas del británico en sus respectivos tiempos libres.

El juego de la vida ocurre en un tablero cuadriculado, en donde cada cuadro puede haber una célula o estar vacío. La idea es acomodar una serie de células en la malla cuadriculada y observando las vecindades de cada célula, cada cuadro pues -utilizando las reglas de Conway- ir calculando las nuevas configuraciones de células que aparecerán en la siguiente generación. Puede verse que el juego de la vida de Conway no es estrictamente un juego de video, pues el “jugador” no hace nada más que ver la evolución que en cada tiempo, en cada generación, aparece en la pantalla.

Cabe decir que las reglas que se definan para el juego de la vida deben ser tales que la conducta de la población resulte a un tiempo interesante e impredecible. Las reglas de evolución, dadas por el propio matemático, llamadas también reglas genéticas, son de una sencillez deliciosa y pensamos que Conway las fue descubriendo (¿inventando?) poco a poco.

Tomemos un plano cuadriculado entonces de dimensiones infinitas. Cada sitio, cuadro o casilla, tiene 8 casillas vecinas: cuatro ortogonalmente adyacentes (2 en vertical y 2 en horizontal). En cada sitio es posible poner un valor binario (hay célula o no hay en esa casilla). Las reglas son:

• Supervivencia: cada célula (digámosle ficha), que tenga dos o tres fichas vecinas sobrevive y pasa a la generación siguiente.
• Fallecimiento: cada ficha que tenga cuatro o más vecinas muere y es retirada del tablero, por sobrepoblación. Las fichas con una vecina o solas fallecen por aislamiento.
• Nacimientos: cada casilla vacía, adyacente a exactamente tres cifras vecinas -tres, ni más ni menos- es casilla generatriz. Es decir, en la siguiente generación habrá de colocarse una ficha en esa casilla.

Es importante hacer notar que todos los natalicios y fallecimientos ocurren simultáneamente, y constituyen en su conjunto una generación en particular, al paso del tiempo t, también llamado tic del reloj.

Con el mismísimo Conway, en su plática que dio en junio del 2010 en la Facultad de Ciencias de la UNAM.

En un principio el inventor de este singular “juego” conjeturó que ningún patrón inicial podría crecer ilimitadamente. Dicho en otras palabras, ninguna configuración compuesta por un número finito de fichas puede crecer hasta rebasar un límite superior finito, que limita el número de fichas que puede contener el campo del juego. Seguramente esta sea la cuestión más difícil y profunda que planteé el juego.

Conway ofreció un premio de 50 dólares a la primera persona capaz de probar o de refutar la conjetura antes de finalizar el año 1970. Una forma de refutarla sería dar con configuraciones que, generación tras generación, añadiesen más piezas al terreno de juego: un cañón (es decir, una configuración qaue repetidamente dispara objetos en movimiento), o bien el tren puf-puf (configuración que al paso del tiempo t avanza dejando tras de sí una estela de “humo”).

La conjetura de Conway se refutó en noviembre de 1970. Un grupo integrado en el proyecto de inteligencia artificial del MIT, comandado por William Gosper, halló un cañón lanza-deslizadores, el cual genera un deslizador cada 30 pulsos de reloj (o generaciones). La existencia de tal cañón suscita una interesante posibilidad de que el juego de Conway pueda simular una máquina de Turing, la cual es capaz de hacer, en principio, cualquier computación, cualquier cálculo. Si el juego permite esta alternativa, entonces la siguiente pregunta a resolver es si sería capaz de poderse crear un constructor universal. De lo cual se encontraría una máquina con capacidad de autorreproducción no trivial. Desafortunadamente, a la fecha, no ha podido construírse.

El carácter universal del juego de la vida significa que, en principio, es posible usar deslizadores para llevar a cabo cualquier cómputo que pueda efectuarse con la más potente de las computadoras digitales. Mediante la disposición de cañones lanza-deslizadores y otras formas de “vida”, es posible calcular π, e, la raíz cuadrada de 2, o de cualquier otro número, con cualquier número de cifras decimales.

 Hay muchísimos programas de código abierto y gratuito para jugar con el juego inventado por Conway. Vale la pena probar alguno de ellos e intentar configuraciones diferentes. Hay mucha información sobre el juego de la vida del matemático británico y podría asegurarles que es francamente apasionante. El único inconveniente es que esto comienza a hacerse obsesivo.

Algunas fuentes de interés:

Juego de la vida en HTML5
Juego de la vida de Conway
Juego de la vida con fuentes (Delphi)
LifeWiki
________

(*) En la foto inicial del artículo están, de izquierda a derecha: Erik Demaine, Martin Demaine, Bill Spight y John Conway

"Matemática... ¿estás ahí?" de Adrian Paenza

El sábado pasado, Guil Russek me prestó un libro de matemáticas recreativas, de divulgación de las matemáticas, llamado "Matemática... ¿estás ahí?" escrito por Adrián Arnoldo Paenza (Buenos Aires, Argentina, 9 de mayo de 1949), licenciado y doctor en ciencias matemáticas por la Facultad de Ciencias Exactas y Naturales de la Universidad de Buenos Aires y además, periodista deportivo.

Entre 1986 y 1997 fue profesor asociado del departamento de matemáticas de esa institución. Ganador del Premio Konex en la categoría Periodismo Deportivo Audiovisual en 1997, ejerce el periodismo en diversos medios, y es conductor del programa «Científicos Industria Argentina», galardonado con el Premio Martín Fierro en 2007 y 2011; «Alterados por pi» de Canal Encuentro, «Explora y Laboratorio de Ideas». Trabajó en las radios más importantes del país y en los cinco canales de aire de la Argentina. Fue redactor especial de varias revistas y colabora con tres diarios nacionales: Clarín, Página 12 y La Nación. Actualmente es columnista especial de Página 12. En 2007 recibió el Premio Konex de Platino a la Divulgación Científica.
Su obra literaria tiene mucho que ver con las matemáticas recreativas y de divulgación. He aquí un listado de las mismas:

• Propiedades de Corrientes Residuales en el Caso de Intersecciones No Completas, tesis doctoral de 1979.
• Matemática... ¿Estás ahí?, sobre números, personajes, problemas y curiosidades.
• Matemática... ¿Estás ahí? Episodio 2
• Matemática... ¿Estás ahí? Episodio 3.14, problemas, juegos y reflexiones sobre las matemáticas. Caen bajo su cordial charla el Nim, la teoría de juegos, la combinatoria, la Ley de Benford, los números primos y otras maravillas de los números, las figuras y el pensar.
• Matemática... ¿Estás ahí? Episodio 100, más historias sobre números, personajes, problemas, juegos, lógica y reflexiones sobre la matemática.
• Matemática... ¿Estás ahí? La vuelta al mundo en 34 problemas y 8 historias
• ¿Cómo, esto también es matemática?

El libro "Matemática... ¿estás ahí?" contiene los siguientes capítulos:

• Números
• Personajes
• Probabilidades y estimaciones
• Problemas
• Reflexiones y curiosidades
• Soluciones
• Apéndice

El estilo es muy ameno y fácil de digerir. El autor intenta no envolver en muchas ecuaciones y números cada apartado, por lo cual se puede seguir su razonamiento casi de forma automática. Tiene capítulos simpáticos, como por ejemplo: Cómo conseguir un contrato como consultor usando un poco de matemáticas o su reflexión en ¿Cuántas veces se puede doblar un papel? que termina finalmente mostrando el mismo problema de los granos de trigo en ajedrez (que son potencias de dos). Otros artículos, me parece, merecían más contenido, como el problema 3x + 1 que en mi opinión se queda corto. Hay mucho más que decir al respecto.

Como sea, es un libro divertido, que se puede leer a cualquier hora y nos asoma a un mundo fantástico, el cual en realidad está muy ligado al de la realidad cotidiana, en donde hay muchas más matemáticas de las que solemos ver.

Hallé que el libro completo está aquí, aunque no sé si el autor o la editorial hayan dado su permiso.

La inflación en el rating en ajedrez

En ajedrez existe una medida llamada "rating" o "Elo" (por el apellido a quien se le ocurrió inventar esto), el cual sirve para medir la fuerza ajedrecística de manera estadística. Arpad Elo, quien era físico/matemático y un fuerte aficionado (aunque de origen húngaro), vivió en Milwakee y ganó 8 veces el campeonato de su ciudad (allá por los años treintas del siglo pasado), estudio la idea de crear un sistema para clasificar numéricamente la fuerza en ajedrez. Luego de un interesante trabajo, la Federación Internacional de Ajedrez(FIDE, por sus siglas en francés), decidió incorporar ese sistema en 1970 y a partir de ese momento ya nada fue igual.

Gracias a este sistema, los torneos no solamente eran fuertes porque jugaban ajedrecistas famosos, sino porque tenían una clasificación que los hacía ver más fuertes. La idea fundamental de Elo es la siguiente: "Si dos jugadores tienen la misma puntuación, la probabilidad de que gane uno o el otro es de 50%". Elo entonces decidió calcular de acuerdo a una curva que casi es lineal, la probabilidad de que un jugador le gane a otro si el primero le lleva 10, 20, 30, ... , 100, 200, 300 puntos de diferencia. Esa tabla se llama precisamente "tabla de expectativas", porque indica, de acuerdo a la diferencia entre los ratings de los jugadores, quién tiene más probabilidades de vencer. Por ejemplo, si un jugador le lleva a otro unos 100 puntos de ventaja, entonces el jugador con la diferencia a su favor tiene que ganar 7 de cada 10 partidas aproximadamente.

Curiosamente con los años, el sistema de rating ha empezado a sufrir una serie de problemas, por decirlo de alguna manera. Por alguna razón no identificada aún, la medida ha tenido un efecto inflacionario. Por ejemplo, hace unos 15 años, tener más de 2650 puntos de rating lo calificaba al jugador como en la elite de jugadores. Hoy es un rating de un jugador fuerte, pero nada que hacer ante los 2700 puntos o más que ya unos 30 jugadores tienen en el mundo. Fischer, por ejemplo, llegó a tener 2780 puntos en 1972, cuando aún no había inflación en el rating. Hoy estaría entre los cinco o seis mejores del planeta. Así de fuerte era Bobby.

Otro jugador, Kasparov, que por 25 años se mantuvo en el primer lugar de la lista de rating, llegó a la estratosférica cifra de 2851 puntos. Nadie a la fecha ha llegado a ese nivel. Algunos dicen que el rating de Kasparov sufrió también del efecto inflacionario, pero la realidad es que con o sin ese efecto, Kasparov ha sido probablemente el mejor ajedrecista de todos los tiempos.

En mi opinión, la razón de la inflación del rating no es muy difícil de hallar. Por ejemplo, tenemos los resultados de los tres torneos en Wijk aan Zee 2012 (grupos A, B y C). Si sumamos el total de puntos de rating que ganaron y perdieron los jugadores (la cifra que está a la derecha de cada tabla), hallaremos que para el grupo A, B y C, el total de puntos ganados y perdidos es de 0, 0 y -1, respectivamente. El valor de -1 puedo achacarlo al redondeo (se desprecian a veces los decimales y el programa de Chessbase que hace estas tablas quita los decimales, redondeando a valores enteros). Así que probablemente si rechecamos esos resultados, con decimales incluídos, hallaremos que el total de puntos positivos y negativos, ganados y perdidos por los jugadores, suma cero.

(Dé click en cualquiera de las tablas para verlas en su tamaño original)

Esto significa que en este caso, en los tres torneos, el total de puntos de rating en juego se "reparte" entre los jugadores. Si ellos jugaran siempre entre sí los torneos, no habría inflación posible. Cuando un jugador no logra la puntuación esperada por la tabla de expectativas, entonces cede puntos de rating. En caso contrario, puedo ocurrir lo contrario y el jugador hacerse de puntos.

¿De dónde viene el problema de la inflación del rating? Sin duda de que los jugadores participan en torneos en donde juegan otros jugadores. Como no son los mismos ajedrecistas siempre, los mejores le quitan sus puntos Elo a los demás y cuando estos ganadores enfrentan a otros ajedrecistas -digamos de elite- ceden u obtienen puntos de acuerdo a sus fracasos o éxitos, respectivamente, y por ende,  se genera este efecto de inflación.

Por ejemplo, supongamos que tomamos toda la lista de rating de la FIDE, unos 130,000 jugadores actualmente. Si ése es el universo de ajedrecistas, entonces jugando entre ellos, unos con otros en diferentes torneos, no debería alterar el total de puntos ganados y perdidos en promedio, el cual arroja cero como la cifra correcta. Pero el punto es que mes a mes se incorporan nuevos jugadores a la lista de rating y entonces esos nuevos jugadores entran con una puntuación que se les asigna, y que no se dio quitándoles puntos a otros jugadores para así conservar el equilibrio de puntos ganados menos perdidos que nos dan cero o cercano al cero.

Por ejemplo, en los años ochentas, en los torneos FIDE que empezaron a jugarse en el mundo, un jugador no clasificado podía jugar ese tipo de torneos y se le asignaba una cifra temporal de rating de 2200 puntos. Ese número no era consecuencia de la fuerza de nadie. No, se le asignaba al jugador para que éste empezara el torneo con un valor. Una vez terminada la justa, se calculaba su rating y poco a poco, el ajedrecista se acomodaría al rating o fuerza ajedrecística que le correspondiera.

Cabe decir que hace unos años (quizás veinte), la FIDE decidión subir 100 puntos al rating femenil (a excepción de las hermanas Polgar, que ya jugaban como los mejores ajedrecistas del sexo opuesto). Si de pronto la FIDE "regala" a cada jugadora 100 puntos en cada rating, el efecto inflacionario tiene que verse reflejado en algún momento. Para mí es un asunto de sentido común. El conjunto total de ajedrecistas en el mundo, clasificados con rating, tiende a crecer y el efecto se notará -lentamente- como inflación en el rating.

¿Alguien encuentra algún fallo en este razonamiento?

Una pregunta a la que aún no tengo respuesta

Las pantallas gráficas ya vienen en todas las resoluciones habidas y por haber, 320x200 pixeles, 640x480, 1024x768 etc. y evidentemente en la medida que avanza el hardware y se tienen tarjetas gráficas más poderosas, más pequeños son los puntos en la pantalla y mejores son las imágenes que podemos desplegar.


En el curso que estoy dando, en la Facultad de Ciencias, sobre graficación por computadora, empezamos por las "primitivas", es decir, las funciones básicas que debe tener todo sistema gráfico. La primitiva más primitiva valga la expresión, más fundamental, es el pixel, el equivalente al punto en una gráfica en papel. En la computadora tenemos un limitado número de pixeles en la pantalla, que son cuadrados a todo esto, y que por su reducido tamaño ya el ojo humano no puede distinguir que se trata de un cuadrito minúsculo para cada pixel.

Otras primitivas son línea (sucesión de puntos, de pixeles, pues), círculos, elipses, rectángulos, moverse a un punto en la pantalla sin pintar, etc. Esto es lo primero que todo estudiante de este curso debe saber. Pero he aquí que pensando en las líneas, llegué a la conclusión que si consideramos que un punto en términos conceptuales no tiene siquiera tamaño, entonces una línea es una sucesión infinita de puntos. Si esto es cierto, mi pregunta es ¿por qué podemos dibujar en papel una línea, que supuestamente es una sucesión infinita de puntos y hacerlo en tiempo finito? 

Me huele que esto se parece al problema de Aquiles y la tortuga, pero no estoy seguro. ¿Alguna idea?

¿Por qué es difícil que los niños se interesen por la ciencia

El Dr. Michio Kaku es un físico teórcio, autor de libros de gran venta en los estados Unidos (bestsellers), y un divulgador de la ciencia. Él es el co-fundador de la teoría del campo de las cuerdas  (una rama de la teoría de cuerdas), y continúa la búsqueda de Einstein por unir las cuatro fuerzas fundamentales de la Naturaleza en una sola teoría unificada.

Me robo de la página de la física Úrsula Bernal Cataño (que estudió en la UNAM), el siguiente video que puso en su página de Facebook. Me queda claro que el argumento que presenta en el mismo el Dr. Michio Kaku es más que contundente:

¿Por fin cuántos vasos caben en un beetle?

He aquí las fotos que me mandó un buen internauta, con el siguiente texto, dirigido a Nescafé/Nestlé:


A quien corresponda.

Por medio de la presente, les solicitamos rectifiquen su error y repitan correctamente el llenado del beetle. Somos un grupo de inconformes que iremos hasta donde sea necesario incluyendo medios de comunicación para que se hagan bien las cosas.

Adjuntamos las pruebas que subiremos a diferentes medios y redes sociales, justificando que al coche le entran muchos más vasos que los que ustedes reportan. En las fotos, se lleno un choche beetle 2010, con vasos de 20oz marca convermex. con tapa plana.

Al coche le entraron mas de 1500 vasos y aun quedaba espacio como para otros 100. La tapa de los vasos de nescafe ocupan un poco de mas espacio pero no el espacio de 500 vasos como ustedes lo llenaron.

Asi mismo haremos llegar esta informacion toda recopilada, por paqueteria al director de nestle Juan Carlos Marroquin Cuesta.

Solo para que este enterado de lo sucedido.

ADDENDUM: (2/dic/2011 a las 2:12 pm)  Mi amigo Felipe Flores @FelipeFloresMX puso en twitter los siguientes mensajes:

El notario amablemente me comenta que dio fe le metieron determinado número de vasos, ese número no fue hasta llenar el Beetle. Me dice el notario que todavía le cabían más vasos al Beetle, pero detuvieron el llenado, en la fe notarial ahí se especifica.

Y agregó minutos más tarde: "dice [el Notario No. 17] que en la fe notarial que entregó ahí se específica el asunto de que no se llenó el beetle, dice que todavía quedaron más bolsas por meter. Indica que los vasos estaban en bolsas y que se tomaron fotografías".