parser para fórmulas de lógica proposicional (o una somera introducción a pyparsing)

La semana pasada empecé a cursar, de oyente, dos materias en Exactas: Lógica y Computabilidad y Teoría de Lenguajes. En la primera, empezamos a estudiar algunos conceptos de cálculo proposicional. Al final de la clase, el profesor sugirió escribir un pequeño parser que reconozca fórmulas de lógica proposicional. Dado que venía con ganas de entender mejor pyparsing, me pareció que podía ser una buena forma de empezar.

Primero, la teoría. Dado el alfabeto $latex A$, $latex A^*$ es el conjunto de palabras que pueden formarse combinando sus elementos.
$latex A=\{ \to , \wedge , \vee , \neg , ( , ) , p , \prime \}$
Existe un tipo particular de palabras, a las que llamamos variables.
$latex Var=\{p , p\prime, p\prime\prime , \ldots \}$
Es un conjunto infinito y, dado que puede ser tedioso contar la cantidad de primas, las variables pueden ser referenciadas como $latex p_n$, donde n es la cantidad de primas. Así, parece razonable pensar que no todas las palabras son válidas a la hora de escribir una fórmula (que es como llamaremos a las palabras válidas).

Ejemplos de fórmulas:

  • $latex p_2$
  • $latex ( ( p_3 \wedge p_5 ) \to ( \neg p_2 \vee p_5 ) )$
  • $latex \neg \neg ( p\prime \vee p_{1232} )$

Ejemplos de no-fórmulas (palabras que no forman una fórmula):

  • $latex \neg\prime$
  • $latex ( p_2 )$
  • $latex p_3 \vee \wedge $

Si bien es más o menos intuitivo qué es una fórmula y qué no, es necesario definirlo en un sentido formal. Así $latex Form \subset A^* $ y es el conjunto de las palabras que cumplen:

  1. si $latex \alpha \in A^*$ y $latex \alpha \in Var$, entonces $latex \alpha \in Form$
  2. si $latex \alpha \in Form$, entonces $latex \neg \alpha \in Form$
  3. si $latex \alpha,\beta \in Form$, entonces $latex ( \alpha \circledast \beta)\in Form$. Donde $latex \circledast=\vee,\wedge,\to $

Nada más es una fórmula.

Ahora, a la práctica. Queremos escribir un parser que, dada una palabra, reconozca si es una fórmula. Y para esto vamos a jugar con el módulo pyparsing, para python.

Lo primero es definir el conjunto de variables.

>>> from pyparsing import Word
>>> variable=Word('Pp',"0123456789'")
>>> variable.parseString('p1')
(['p1'], {})
>>> variable.parseString("P'")
(["P'"], {})

Así, variable reconoce los posibles nombres de variables. Toda expresión que sea parseable por variable, es una formula. Para el punto ii. hay que definir una estructura recursiva. Utilizaremos el bang (!) para la negación.
from pyparsing import Forward
formula=Forward()
ii='!' + formula

Caso similar en el punto iii.. Para esto hay que definir los operadores, que son and (&), or (|) y then (<).

operador=Word('&|>',max=1)
iii='('+formula+operador+formula+')'

Por último, definimos una fórmula cómo una variable (i.) o una negación de una fórmula (ii.) o una operación entre fórmulas (iii.).

formula << ( variable | ii | iii )

Y esto es, básicamente, nuestro parser:

>>> formula.parseString("(p1 | p4)")
(['(', 'p1', '|', 'p4', ')'], {})

Lo dicho, con un poco más de contexto y en un único archivo, a continuación:

operating elements of a finite lattice is now easy(?)

In the context of my recent readings about Information Flow analysis, I wrote a little (tiny) Python module to operate elements of a finite lattice. Here is the code and usage tutorial. Comments are welcome. Patches to my broken English in the main page are very welcome.

/home/duijvestijn

I have a new guest in my apartment. Give a warm welcome to the Adrianus Johannes Wilhelmus Duijvestijn's spirit.

Thanks a lot to Bartu and Rezlaj, who carried out the necessary seance that make this possible.

The complete photo set is here. If you do not have the slightest idea of what I'm talking about, take a look to Wikipedia or my previous post (Spanish only).

(esta entrada también está disponible en Español)

/home/duijvestijn

Tengo un nuevo huésped en mi departamento. Denle una cálida bienvenida al espíritu de Adrianus Johannes Wilhelmus Duijvestijn.

Muchísimas gracias a Bartu y a Rezlaj, quienes llevaron a cabo la sesión de espiritismo necesaria para hacer esto posible.

Todas las fotos están disponibles aquí. Si no tienes la menor idea de a qué se refiere esto, échale un ojo a la Wikipedia (solo en inglés) o a mi entrada anterior.

(this post is available in English too)

disección perfecta de polígonos for dummies

Por razones que explicaré en una próxima entrada de este mismo blog, últimamente he estado divagando alrededor del concepto de la disección perfecta de polígonos. Y es este divague el que me gustaría compartir con ustedes en este (demasiado) extenso post.

Empezando por el principio, ¿qué es un polígono? En términos wikipediables:

un polígono es una figura geométrica formada por segmentos consecutivos no alineados, llamados lados.

Nos gusta que los segmentos no estén alineados, porque así forman ángulos, que es parte de la definición etimológica. Por otro lado, el hecho de que los segmentos sean consecutivos, garantiza que la figura quede cerrada. En particular, nos vamos a centrar en polígonos que sean:

  • planos. Es decir, bidimensionales, de lo que se pueden dibujar en un papel.
  • simples. Es decir, que sus lados no se corten entre sí.
  • convexos. Es decir, si al atravesarlo con cualquier recta lo corta en no más de dos puntos.
  • con hasta un máximo de 4 lados. Es decir, triángulos y cuadriláteros

En definitiva, vamos a referirnos a figuras sencillas donde algunas regularidades nos sean agradables, como el hecho de que los lados sean del mismo tamaño o que tenga algunos ángulos iguales.

Una vez acotado el universo de polígonos vayamos a la siguiente parte del asunto: la disección. Esta idea es bastante intuitiva. El objetivo es tomar un polígono y subdividirlo en otros. A estos otros los vamos a llamar elementos, dado que forman y son parte del polígono grande inicial. La cantidad de elementos es el orden de la disección. Un factor interesante que vamos a agregar a esta definición informal es que los elementos solo pueden variar en su proporción u orientación, por ejemplo que sean todos cuadrados o todos triángulos rectángulos, pero no mezclados.

Vamos a por un ejemplo inicial sencillo. Si tomamos un cuadrado, podemos dividirlo en cuatro triángulos isósceles rectángulos del mismo tamaño, como en la figura de la derecha . Así tenemos un polígono interesante (el cuadrado) que puede ser dividido en cuatro polígonos interesantes (los triángulos rectángulos isósceles). Sin un gran esfuerzo de imaginación, también podríamos dividir un cuadrado en 4 cuadrados (pero es una imagen que evitaremos, que me hace acordar a una empresa monopolizadora).

Así obtenemos disecciones de polígonos, que a primera vista, no parecen ninguna genialidad. Sin embargo, algunas ideas interesantes empiezan a surgir. Por ejemplo, dado que tanto el contenedor como los elementos son interesantes, la noción recursiva aflora. Otros conceptos llamativos, como el de teselado regular, temas de empaquetamiento o el problema de Mrs. Perkins's Quilt pueden desprenderse desde este punto.

Nosotros vamos a tomar otro camino al agregar el último ingrediente de esta receta: la disección perfecta, que pide que los elementos sean todos de distinto tamaño. Acá se pone más interesante y mucho menos obvio. Volvamos a nuestro ejemplo de dividir un cuadrado en triángulos rectángulos isósceles, pero esta vez hagamos una disección perfecta. A continuación, la propuesta de Arthur Stone:

El número es el largo del cateto de triángulo. Estamos entrando en un terreno donde ahora las cosas son difíciles de imaginar a primera vista. Uno podría empezar a preguntarse en cuántas formas distintas se pueden hacer estas disecciones, si es que hay mas de una. Y si hubiese, cómo se pueden construir. En un interesante y largo paper de 1999, Skinner II et. al. proponen una analogía con la primera ley de Kirchhoff (si, esa sobre los nodos de los circuitos eléctricos) para ayudar a la construcción de disecciones perfectas de cuadrados. Este método genera disecciones a triángulos rectángulos isósceles que cortan la diagonal principal de cuadrado que los contiene (lo que permite generar disecciones simples, explicadas más adelante). Como en el siguiente ejemplo extraído de la página 33 del paper:

La siguiente pregunta es si existen disecciones perfectas en otras formas interesantes. Por ejemplo, Brooks et. al. demostraron que no es posible dividir un triángulo equilátero en triángulos equiláteros de forma perfecta. En ese mismo trabajo de 1940 se señala que, a diferencia de la perfectibilidad, era posible hacer una disección de equiláteros en equiláteros que fuese simple.

Se dice que una disección es simple cuando ningún subconjunto de 2 o más elementos forma una figura de las informalmente definidas como interesante. Por ejemplo, en el caso de la distribución propuesta por Stone que ya mencionamos, el subconjunto de elementos pintado con verde forma un triángulo rectángulo isósceles:


Por lo que definimos esta disección como compuesta en contraposición a la simple que expone Skinner et. al.

Una disección puede ser simple y no perfecta, o viceversa. Así, y como venía diciendo, Brooks et. al. dicen que es posible dividir un triángulo equilátero en triángulos equiláteros de forma simple, aunque imperfecta. Dicha forma fue presentada por William Tutte, un famoso criptoanalista británico, y es así:


Y como en la vida misma, lo simple y lo perfecto perecen ser cualidades que cuesta ver en conjunto. Pero que, para belleza de la cosas, no es imposible de encontrar. Así es que me gustaría presentarles el cuadrado de menor orden que puede dividirse en cuadrados de forma simple y perfecta, descubierto por Adrianus Johannes Wilhelmus Duijvestijn la noche del 22 de Marzo de 1978:

Esta disección en 21 cuadrados desiguales que no forman subconjuntos de cuadrados es lo que se conoce como la disección de Duijvestijn, y se pueden comprar remeras con su estampa. Si bien Duijvestijn ya había descubierto disecciones perfectas simples del cuadrado de ordenes superiores, había probado, junto a Bouwkamp, que no era posible crear estas disecciones en órdenes menores a 20. De ahí el esfuerzo por encontrar la más pequeña de las posibilidades.

Espero no haberlos aburrido en demasía. Para mí fue muy entretenido y aprendí muchísimo sobre álgebra y geometría, así como formas de representación imaginativas de conceptos geométricos que permiten razonar de forma algorítmica. Si quieren aprender más sobre los temas tratados en esta entrada, pueden consultar la página Squaring.net que está totalmente dedicada a este tipo de puzzles e incluye biografía de las personalidades referentes del área, así como otros temas relacionados. Este post está fuertemente basado en esta web. El artículo de Wolfram MathWorld al respecto también es muy entretenido. Se puede chusmear la página de wikipedia sobre el problema de Squaring the square para una idea más breve de la representación de Smith.

log log binning

Una de las materias que hice el año pasado (estrictamente hablando, aún la estoy haciendo) fue Topología de Internet, con Nacho Alvarez-Hamelin. En ella estudié a Internet como sistema complejo, donde routers y/o ASs se interconectan y forman un grafo.

Una de las propiedades más características de los grafos es su distribución de grados. El grado es la cantidad de vértices que tiene un nodo. En el ejemplo de la izquierda, el nodo 4 tiene grado 3. La distribución de grados es una característica del grafo en su conjunto y no es otra cosa que contar cuántos nodos hay con grado 0, cuántos con grado 1, y así siguiendo. En el caso de la topología de Internet, no hay nodos con grado 0, ya que es una red totalmente conexa (triste sería estar conectado a ese router que no está conectado a nada más).

La topología de Internet (es decir, cómo se interconectan sus componentes) no se conoce a ciencia cierta (tema que quedará para otro post) pero hay algunos acercamientos académicamente aceptados. Uno de ellos es el de CAIDA que provee información sobre como están conectados los distintos sistemas autónomos. Esta data, después de modificar un poco su formato, puede ser analizada con el módulo Complex Systems Toolbox, para Scilab, un clon libre de Matlab.
Resulta ser que, al analizar la distribución de grados de la topología de Internet, uno se encuentra con una distribución de ley potencial (chocolate por la noticias, dirían los hermanos Faloutsos, que ya sabían esto desde 1999).

Esta ley de potencia (en inglés, power law) es una relación en que la frecuencia de un hecho cae de forma exponencial con respecto a la magnitud. Este tipo de distribuciones tiene una forma de panza hacia el eje de coordenadas y abunda en la naturaleza™, desde el crecimiento de los ríos hasta la popularidad de las personas en las redes sociales. Por su forma tan particular, se suele dibujar en ejes logarítmicos, quedando como una recta que se caracteriza por su pendiente (en el dibujo, b), que es el exponente de la curva en ejes lineales.

En estos dibujos, la curva es continua y elegante. Pero cuando uno va al mundo discreto de la modelización de fenómenos, la cosa cambia. Y mucho. Por ejemplo, este es el gráfico de la distribución de grados de la topología de AS, según CAIDA:

Los puntos rojos son las muestras discretas, las uní solo para que se aprecie mejor cuál va delante de cada cuál. Como se ve, la cosa no queda tan prolijita y agradable. Es que hay veces que la naturaleza™ se resiste a ser modelada con una fórmula y la estimación de al pendiente cuando se trata de datos experimentales puede ser complicada, sobre todo en la cola. Así es como llegamos al concepto de binning.

La idea es sencilla. Consiste en dividir el eje x es zócalos (bins) de tamaño fijo. Después tomar todas las muestras que caigan en un bin y promediarlas. Así, se grafica solo este promedio como un único punto que representa a todo el bin. Como estamos trabajando con ejes logarítmicos, el calculo del ancho de los bins requiere cierta aritmética, dado que estos se van ampliando exponencialmente (de forma tal que queden todos del mismo tamaño, o casi, al plotearlos). A esto lo llamamos log log binning.

Por suerte, el Complex Systems Toolbox tiene una función para hacer esta magia. Y aquí está el resultado:

Las muestras son las cruces rojas, mientras que los puntos verdes son los representantes de binning. Puede verse que están casi equidistantes, sobre todo después de 10. Por otro lado ¿no notan nada raro acá? Vamos por partes. En la parte inicial de la curva, ésta aparece por debajo de la línea de las cruces rojas. Esto empieza a tener poco sentido. Se supone que el promedio de un único punto es ese mismo punto.

Más grave aún es lo que ocurre en la cola. Ahí, esporádicos puntos (hay muchos ceros) generan una recta paralela al eje. Cuando uno promedia varios valores el resultado debería ser cada vez menor si la cantidad de ceros aumenta. Sin embargo, aquí la curva se suaviza hasta perder toda su inclinación.

Fue así como decidí mejorar esta funcion de log log binning (si, toda esta introducción para contarles esto... es que evidentemente soy muy pedante). A continuación, el mismo gráfico, resultado de mi propia implementación:

Algunas reimplementaciones por acá, fixeo de bugs por allá y ahora la pendiente se puede ver mucho más clara. Obvio que también podías leerte el paper de los hermanos Faloutsos, donde se explica que b está entre 2.1 y 2.4, pero no hubiese sido igual de divertido. Tuve que leer bastante y entender aritmética que había olvidado. Putié mucho contra scilab/matlab pero terminé descubriéndole cosas interesantes. En general, fue algo bastante entretenido.

La nueva implementación de log log binning ya está en el trunk de Complex Systems Toolbox y seguramente estará disponible en la próxima versión. También incluí novedades para graficar distribución de grados cuando los grafos son dirigidos y algunas otras pequeñeses de formato.

La ley de Benford y la vida real (tm)

Lo prometido. Hoy me gustaría hablarles algo que no tenía idea que existía y que me encontré en el apéndice 9 del libro La Proporción Áurea de Mario Livio. Es de esos sorprendentes conceptos que destruyen la intuición. Por un lado es simple desde lo formal, pero esconde algo casi mágico. Dicho concepto es: La ley de Benford

Para los que no hicieron click en el link anterior y dado que la entrada en la Wikipedia en español sobre el tema deja bastante que desear (estoy corrigiéndola), acá está mi breve explicación:

La ley de Benford, también conocida como la ley del primer dígito, dice que, en los números que existen en la vida realTM, la primer cifra tiene muchas más posibilidades de ser 1 que otro valor. Además, según crece este primer dígito, más improbable es que se encuentre en la primera posición.

A por un ejemplo, que seguro es más fácil. Tomemos una tabla con estadísticas cualquiera, como ser el área o población de las provincias argentinas, la capacidad de los estadios del mundo, los muertos por accidentes de tránsito o las estadísticas de visitas en tu blog. Como todo en estadística, mientras más grande la muestra mejor, así que vayan a por tablas realmente grandes.

Intuitivamente, uno podría pensar que, para cualquier número, las posibilidades que empiece con 1 son las mismas que con 9. Es decir, al agarrar una pelota de números cualquiera de la vida realTM se podría llegar a creer que, si la cantidad es lo suficientemente grande, más o menos 1/9 de la muestra empezarán con 1 (nótese que no tiene sentido que los valores empiezen en 0, por lo que las opciones son 9). Esto es porque creemos que los números que estamos analizando se comportan como si fuesen aleatorios. Si tiramos una moneda al aire una gran cantidad de veces, cerca de la mitad de las oportunidades será seca. Es algo que aprendimos hace mucho y nos parece intutivo que la naturaleza se comporte así. Como si $deity hubiese tirado un dado gigante para decidir el largo de un río, la población de un país o el precio de las acciones en el MERVAL.

Como en mi disco todavía tengo los datos utlizados para el post la chica bajo la curva (dating pool) voy a utilizar la cantidad de casados, por provincia, por edad (puede descargarse desde acá). En mi caso son 30843 regitros. Esta linea de bash cuenta cuantos de los valores empienzan con cada cifra:

$ for i in $(cat provincia_indec.csv | grep años | cut -d ';' -f 4); do echo ${i:0:1}; done | sort | uniq -c
10350 1
5581 2
3550 3
2744 4
2159 5
1903 6
1815 7
1406 8
1335 9

Puede verse que el 33.56% de las cifras empiezan con 1 y que, mientras mayor es el valor del primer dígito, menor es la cantidad de ocurrencias.

En efecto, nuestro nuevo amigo Benford describe este fenómeno y nos dice que, la probabilidad p de que el dígito d aparezca en el primer lugar está dado por la siguiente fórmula:

En el ejemplo anterior, el dígito 1 se encuentra en 10350/30843=0.336 de los casos. Puede verse que la predicción de la fórmula es bastante buena, ya que log10(1+1)=0.301. En la siguiente figura puede verse como se ajusta la fórmula a los datos de la práctica (primer dígito de la cantidad de personas casadas por provincia, por edad según el censo 2001):

De hecho, la misma fórmula puede aplicarse a más de un dígito. Por ejemplo, la probabilidad de que una cifra empiece con 42 (primer dígito 4, segundo 2) es log10(1+1/42)=0.010219. Modificando levemente el script (${i:0:2}) podemos estudiar la cantidad de cifras por la repetición de sus primeros dos números y compararlos con su valor teórico:

Impresionante.. no?

¿Y porqué pasa esto? Ocurre que a las magnitudes del mundo realTM están distribuidas de forma logarítmica.

Recordemos la fórmula: p(d)=log10(1+1/d)=log10(d + 1) − log10(d)
Es decir, cuenta cuántos números hay entre d y d+1 dentro de la escala logarítmica.

La mejor explicación que recibí para este fenómeno habla de un cambio de escala. Supongamos por un momento que la distribución de los primeros dígitos de lo largo de los ríos, lo alto de las montañas, lo profundo de los posos es constante. Ahora imaginemos que $deity se levanta una mañana y duplica el tamaño del planeta (o del universo, ustedes elijen). Las medidas que empezaban por 1 hora pasan a empezar por 2 o 3 (160*2=320). Lo que empezaba por 2 ahora lo hace por 4 o por 5 (290*2=580). El 3 se va a 6 o 7 (384*2=768). El 4 a 8 y 9.

¡Pero todos aquellas medidas que empezaban por 5, 6, 7, 8 y 9 ahora empiezan por 1! Si realizamos esta operación varias veces los valores se amontonan rápidamente en los iniciados por 1, generando la escala logarítmica en cuestión. Y acá está el tema. La mayoría de los valores de la vida realTM son resultados de multiplicaciones.

El siguiente gráfico invita a comparar las superficies rojas (valores que inician con 1) y azules (valores que inician con 8) para estudiar sus probabilidades de ocurrencia en el primer dígito:

Las distribuciones que cubren muchos órdenes de magnitud (que varían mucho entre número y número) cumplen relativamente bien con la ley de Benford. Sin embargo puede no ocurrir así siempre:

Nótese que la clave está en las grandes magnitudes (recuerden la explicación del universo que se duplica). Existen tablas de números de la vida realTM que no cumplen la ley dada que estan acotadas en cuento a su rango, por ejemplo los datos del cierre del MERVAL de los últimos 3 años. Si bien son números grandes, su máximo y mínimo es acotado. Imagino (no tengo uno a mano) que los precios unitarios de los productos en un ticket de supermercado tampoco se agustan a la ley por razones parecidas. La tabla de goleadores de un torneo de fútbol padece el mismo trauma. ¿Se les ocurre algún otro ejemplo excepcional a la regla?

Espero hayan aprendido algo nuevo y ahora quieran a la matemática un poquito más :)

PD: Me olvidaba. Tarea para el hogar: Demostrar que la vida realTM incluye a Fibonacci ;)

φbonacci

Mi conjunto de números favoritos son los enteros en general y los naturales en particular. Son los primeros números que aprendemos en la vida, sencillos, de apariencia intuitiva pero con poderosas propiedades. Dado que mi amateur aproximación a la matemática se dio por el camino de la teoría de números, fueron mi primer gran amor matemático.


Sin embargo, no es difícil encontrar fascinante a otros conjuntos de números. Muchas de estos patean el tablero de formas agradables, como los complejos, que se escaparon de la recta real para irse de vacaciones al plano. Entre los más impetuosos contra la intuición están, obviamente, los irracionales. Y a uno de ellos va dedicado este post.

Hace un par de meses divagué con π. Este semana terminé de leer el libro La Proporción Áurea de Mario Livio. Este libro, que evidentemente trata sobre la constante φ (phi), lo compré en Madrid, atraído por la promesa de desasnarme con respecto a la historia de este número.

Primero me gustaría hablarles sobre el libro como tal, el cual resultó sumamente entretenido, aunque tal vez le sobren unas 50 o 100 páginas. Es un paseo por la historia del arte plástico, arquitectónico, escultural y matemático con φ como eje central hilador. Además de dar ejemplos de como se expresan los números en la naturaleza, explica con profundo detalle ciertas propiedades matemáticas en sus numerosos apéndices e invita al lector a pensar sobre porque la matemática encaja también como explicación del universo. Por momentos se va por las ramas pero casi siempre de forma afable y atrapante. Son altamente rescatables los pasajes donde el autor trata con ácida ironía los esfuerzos de los numerólogos de meter a φ lugares arbitrarios cualquiera, como en las dimensiones de Panteón. En mi opinión es un libro altamente recomendable para el aficionado a la matemática y mi calificación (hace mucho que no califico libros con estrellas) es .

En segundo lugar quisiera comentar algunas nerdeadas matemáticas inspiradas en el la lectura de este libro. Empezando por lo principio, presentar a quienes no conozcan el número φ, en las palabras de Euclides:

Se dice que una línea recta está dividida en el extremo y su proporcional cuando la línea entera es al segmento mayor como el mayor es al menor

La frase dividida en el extremo y su proporcional hace referencia a la proporción de la que estamos hablando. La definición para mortales es:

La longitud total a+b es al segmento más largo a como a es al segmento más corto b

El valor en cuestión se puede calcular despejando algebraicamente tomando b=1, y es:

Puede verse que, al igual que π(pi), es un número irracional. Pero, a diferencia de π, es un número algebraico, lo que lo emparenta bastante con teoría de números. Sin embargo, su expresión como fracción continua compuesta de solo 1s (unos), hace que converja muy lentamente, convirtiéndolo en el más irracional entre todos los irracionales. En términos llanos, φ puede expresarse como la siguiente fracción continua:

Nótese que, cada iteración de esta fracción continua puede expresarse como (los primeros 15 valores, esta secuencia fue resultado de este script):

2 / 1 = 2
3 / 2 = 1.5
5 / 3 = 1.666666666666666666666666667
8 / 5 = 1.600000000000000000000000000
13 / 8 = 1.625
21 / 13 = 1.615384615384615384615384615
34 / 21 = 1.619047619047619047619047619
55 / 34 = 1.617647058823529411764705882
89 / 55 = 1.618181818181818181818181818
144 / 89 = 1.617977528089887640449438202
233 / 144 = 1.618055555555555555555555556
377 / 233 = 1.618025751072961373390557940
610 / 377 = 1.618037135278514588859416446
987 / 610 = 1.618032786885245901639344262

Aquel lector atento notará que las fracciones tiene cierto patrón. Por un lado, el numerador de cada reglón pasa a ser el denominador en el siguiente. Los números son:
1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,....
¡Exacto! ¡Es la sucesión de Fibonacci! Cada número es la suma de los dos anteriores. En efecto, siendo F(n) el termino n-ésimo de la serie de Fibonacci:

Así es como puede verse una fuerte relación entre φ y Fibonacci. Y si con Fibonacci se puede calcular la proporción áurea... ¿cómo es la relación a la inversa?

Con esta formula se puede calcular el valor del término n-ésimo de la serie de Fibonacci:

Es fácil reconocer que dentro de esa fórmula está φ.

La propoción áurea φ tiene un montón de raras y divertidas propiedades. Entre las más atractivas se encuentran:


En lo personal aprendí muchas cosas nuevas sobre la proporción áurea. Pero en el apéndice 9 (como dije, es un libro con muchos apéndices) se comenta un concepto que me voló la cabeza: la ley de Benford. El tema se toca tangencialmente, promediando el último capítulo, como un ejemplo de como las matemáticas sorprenden. Y sí que lo hacen.

Pero ese será tema del siguiente post.

la chica bajo la curva (dating pool)

Hace poco más de un año, como muchos de ustedes seguramente, leí esta simpática tira de XKCD. En ese momento empecé a buscar datos sobre la población para ver que tan real era ello. La pseudo-investigación se fue de cause y terminé en cualquier parte hasta que lentamente perdí el rumbo sin la más mínima intención de retomarlo.

Un par de semanas atrás, y por razones que no viene al caso, volví al tema desde cero. En este caso llegué a cosas medianamente concretas (dentro del delirio, claro). Así que aquí están algunos de los resultados que me gustaría compartir con ustedes.

Introducción:

Para aquellos que no tienen idea de los que estoy hablando, una breve introducción. En la famosa tira cómica se plantea una sencilla hipótesis que puede resumirse en la siguiente pregunta: "¿a partir de qué edad tus posibilidades de tener pareja empiezan a bajar?"

Para esto tengamos en cuenta dos elementos:

  • A mayor edad, menores las posibilidades de soltería. Es decir, si una persona tiene 20 años es más probable de que esté soltera a que ocurra lo mismo con alguien de 40 años.
  • A mayor edad, mayor es el rango de edad de los candidatos. Para poner un ejemplo, no es lo mismo que una persona de 40 salga con otra de 55 que un joven de 18 salga con alguien de 33. Es claro no hay edades para el amor, pero estamos hablando de posibles candidatos. Incluso hablamos de las posibilidades de tener cosas en común, de fijarse en el otro. Randall Munroe, el autor de la tira, propone una fórmula a la que llama "standard creepiness rule" (algo así como "regla estándar de viejo-verdez", asquerosidad, o algo del estilo). Según él (y muchos parecen coincidir), las personas no salen con alguien que tenga la mitad de su edad más siete. Por ejemplo, en mi caso y con 27 años, mi cota inferior está dada por (27/2)+7=20.5, lo que parece bastante razonable o, al menos, políticamente correcto. Esta misma fórmula también sirve como cota superior, ya que uno es el límite inferior de alguien mayor. Para mi edad corresponde a 40 años porque 40=(27-7)*2. Nótese que para una persona de 20 años sus candidatos van entre 17 y 26, mientras que para alguien de 30 sus opciones van entre 22 y 46. Se supone que hay más personas entre el segundo rango que el primero, al menos hasta que la taza de mortalidad empieza a hacer de las suyas.

Primera aproximación:

Lo interesante de esta situación es la posibilidad de analizarla con datos reales. Son datos que existen, que se preguntan en los censos, pero que no siempre están disponibles para cualquier mortal. Por suerte el INDEC (Instituto Nacional de Estadística y Censos) provee la información de una forma que, aunque críptica para el recién llegado, resulta interesante cuando uno le encuentra la vuelta. Así que fue allí a donde fui, a buscar el universo de la población argentina.

Tomando toda la población mayor a 14 años, por edades simples y situación conyugal, calculé la cantidad de personas candidatas para cada edad, tiendo en cuenta los rangos de edades de esos posibles candidatos. Consideremos candidatos a las personas no casadas (solteros, divorciados, separados legales y viudos). Aquí el gráfico:

Nótese la forma de W-invertida de la gráfica. El máximo absoluto se encuentra a los 27 años. Es decir, en este momento me encuentro en el cenit de la soltería. Es interesante observar, que después del punto de inflexión de los 41, a los 47 vuelve a haber un máximo. Llamemos a este punto El club de la divorciadas ;). Las estadísticas demuestran que la frase "la vida da revancha" tiene fundamento estadístico.

Pero los valor absolutos siempre me parecieron lejanos. Soy de los que disfruta hablar en términos de porcentaje, de probabilidades, es decir, en términos relativos. Así fue como generé este segundo gráfico, con la intención de responder a la pregunta "Si conozco a 100 personas dentro de mi rango de edad, ¿cuántas estarán no-casadas?":

Así, la cantidad de personas sin compromisos maritales dentro de un rango, sobre la cantidad total de personas de ese rango da un porcentaje de disponibilidad para cada edad. Acá la cosa se pone algo más pesimista, asegurando una clara caída hasta los 44 años, edad desde la cual se inicia un tímido y poco constante ascenso.

Segunda aproximación:

Esta visión es más egocentrista y está pensada en términos totalmente propios. En lo personal, estoy interesado por personas de género femenino, que no solo no estén casadas, sino que además no convivan en pareja (las considero personas en relaciones lo suficientemente fuertes como para quitarlas del conjunto de candidatas). A estas limitaciones le sumaré la restricción geográfica de que tenga residencia dentro de mi ciudad natal y alrededores, por lo que solo tendré en cuenta personas dentro de Buenos Aires y conurbano bonaerence. La ubicación geográfica puede acarrear cambios culturales que tengan efectos en la situación conyugal de las personas, por lo que considero importante tenerlo en cuenta.

Felizmente INDEC tiene una forma rápida de filtrar por estas restricciones, así que seleccioné las regiones geográficas y construí un filtro donde solo se refiera a personas de sexo femenino que no estén conviviendo con una pareja.

Nuevamente, las mismas gráficas:


Esta vez la W-invertida refleja un máximo absoluto muy diferente al inicial, 53 años. Tal vez se parezca más al modelo que, creo que intuitivamente, proponía Munroe. En el gráfico de porcentajes, la caída es mucho más brusca y profunda, perdiendo más de una decena de puntos en su mínimo, que además se da bastante antes, a los 38 años. La pendiente de ascenso es empinada y termina por provocar mayores valores hacia el final de la esperanza de vida que la aproximación anterior.

Suposiciones y limitaciones:

Estos análisis son un emporio de suposiciones y limitaciones. Después de todo, dicen que la estadística es la ciencia del prejuicio. Acá una lista de suposiciones que pueden ser ampliamente discutibles:

  • Los homosexuales y religiosos existen en cantidades despreciables. Así que todo hombre soltero busca una mujer y viceversa.
  • Las personas con alguna relación de pareja no convivientes son consideradas disponibles. El INDEC no pregunta acerca de estado amoroso de las personas.
  • La cantidad de personas con n y medio edad es la mitad de la cantidad de personas con n edad.
  • La fórmula "standard creepiness rule" es válida. Aunque posiblemente pueda repetirse la experiencia con fómulas que mejor se ajusten a cada cultura. En lo personal, creo tener poco en común con alguien de 40 años. De hecho, formulas independientes para el hombre y la mujer creo que serían más aplicables. Tal vez los hombres tiene un target más orientado a la izquierda del eje. Pero es medio que gusto de cada uno.
  • La información del censo corresponde a datos de 2001. Extrapolarlos no tiene sentido, ya que insertaría muchísimo error. Lo dicho, lo interesante son los números en proporciones.
  • La definición de "candidato" esta dada por edad, género, posición geográfica y estado conyugal. No se contempló gustos y esas cosas de esas que hace que las parejas funcionen... o eso dicen :P.

Todo lo necesario para repetir la experiencia se encuentra acá. Enjoy it ... que yo voy a estar buscando a esa chica bajo la curva :)

Asimov, Leibniz, pi, python, floats y evadirse de la realidad

La matemática tiene cosas sorprendentemente lindas. Y una de las que siempre me gustó de forma especial es la formula de Leibniz para el cálculo de π. También conocida como la serie de Gregory-Leibniz es una simpática manera de expresar el más famoso de los números irracionales:

O para aquellos no gustan de las notación sigma-grande:

Como verán, se trata de una serie sumamente simple y elegante. Y como suele ocurrir con estas cosas, aparecen en la vida de uno en momentos extraños, casi que al rescate.

Anoche me hallé frente a la biblioteca buscando nada en espacial. Necesitaba despejar la cabeza, olvidarme de los asuntos terrenales asociados con las complejas interacciones y relaciones humanas.

Fue en esa circunstancia que me encuentro con De los números y su historia de Isaac Asimov (que puede ser descargado desde aquí). Mientras lo hojeaba vi la formula de Leibniz, promediando el capítulo 6 e inmediatamente atrajo mi atención.

Después de expresar la serie, Asimov explica:

<<Ustedes podrán condenar mi falta de perseverancia, pero los invito a calcular la serie de Leibniz simplemente hasta donde la hemos escrito más arriba, es decir hasta 4/15. Incluso pueden enviarme una postal para darme el resultado. Si al terminar se sienten desilusionados al descubrir que su respuesta no está tan cerca de π como lo está el valor 355/113, no se den por vencidos. Sigan sumando términos. Sumen 4/17 al resultado anterior, luego resten 4/19, después sumen 4/21 y resten 4/23, etcétera. Pueden seguir hasta donde lo deseen, y si alguno de ustedes descubre cuántos términos se requieren para mejorar el valor 355/113, escríbanme unas líneas y no dejen de decírmelo. >>
En efecto, la fracción 355/113 parece ser la forma que mejor balancea precisión y simpleza a la hora de arrimarse a π desde lo números racionales, quedando a solo 2.66764189 × 10-7 de distancia. Mucha gente también utiliza la relación 22/7, aunque con menor precisión.

El desafío propuesto parecía interesante. Resultaba una entretenida oportunidad de jugar con floats en python, que siempre a resultado ser bastante tricky (además de ser un excusa para despejar la cabeza).

Empecé por escribir una versión relativamente obvia de la solución, que me dijo que al llegar al cociente 7497257 (n=3748629 en la sumatoria de Leibniz) el valor de la sumatoria estaría en 3.14159292035, quedando a 2.66764081935 x 10-7 de π. Dado que los decimales (floats, representaciones de punto flotante) en Python no se comportan de forma intuitiva, decidí hacer una segunda versión.

En esta versión traté de mudarme al predecible mundo de los enteros. Y obtuve valores levemente distintos. En el cociente 7497247 (n=3748624) se obtiene la primera aproximación mejor que 355/113, que es 3.141592386825... (a 2.66764162 x 10-7 de π)

Tampoco estoy seguro de que la segunda solución sea la correcta. Me pregunto cual será el promedio de valores en las postales que la viuda Asimov seguramente guarda en una caja de zapatos.

El hecho es que fue entretenido intentarlo y tal vez continúe con la experiencia la próxima vez que quiera desconectarme del mundo. Después de todo, como dijo el mismo Asimov: “Los hombres que se acostumbran a preocuparse por las necesidades de unas máquinas, se vuelven insensibles respecto a las necesidades de los hombres”, y hay veces que volverse insensible se ve, erróneamente, como una propuesta seductora. Hay gente que ahoga penas en alcohol, mucho más sano es ahogarlas matemáticas...

BTW, ya que tenía los datos armé un plot de los primeros 1000 valores de la serie para mostrar de forma gráfica la convergencia.

Ahora es momento de volver a la realidad, que buena o mala, irracional o racional (seguro que real al menos), inexacta o precisa, después de este recreo metal ya no se ve tan mal :-)

UPDATE: Sat, 20 Sep 2008 22:18:18 -0300: La solución estaba realmente cerca (en mi misma ciudad) y se llama Facundo, quien dejó un comentario. Bah.. se llama decimal, pero existe gracias a Facundo :). La biblioteca decimal permite manejar de forma exacta una cantidad arbitraria de decimales. La respuesta correcta es........ (redoblantes de suspenso) con n=(7497259+1)/2! aproxima a Π en 3.141592386825668744985771256 a solo 2.66764125 × 10-7 del número irracional. El nuevo script.. aquí.

Gracias Facundo, gracias decimal, gracias Asimov, gracias Leibniz....

fútbol y matemática, unidos por cumpleaños en común

No, no me refiero a que el fútbol y la matemática cumplan años el mismo día. Vamos por partes.

Antes que nada, una aclaración: aquellos que me conocen saben que a mí el fútbol, como cultura, me es tosco. No se por qué, tal vez algún prejuicio o trauma de la infancia, así que me siento bastante tonto hablando del tema. La razón por la que el siguiente experimento tiene al fútbol de protagonista está justificada en la página 149 del libro Matemática... estas ahí? de Adrián Paenza (que puede bajarse aquí para uso personal).

En la página a la que me refiero el autor explica, con no mucho detalle, la mal llamada Paradoja del Cumpleaños. Para quien no suele hacer clicks sobre los links, una definición fugaz sobre qué es: por más increíble que parezca, en un grupo de 23 personas existe el 50,73% de probabilidad de que dos personas cumplan años el mismo día del año.

En el mismo libro, Paenza propone:

Y si quieren poner esto a prueba, la próxima vez que participen de un partido de fútbol (once jugadores por equipo, un árbitro y dos jueces de línea), hagan el intento. Tienen más de 50% de posibilidades de que con las 25 personas haya dos que cumplan años el mismo día. Como esto es claramente antiintuitivo para muchos de los que participen del partido, quizás ustedes puedan ganar alguna apuesta.

Como últimamente juego poco al fútbol, decidí hacer la experiencia con los partidos del último torneo (Apertura ‘07) de la Liga Argentina. La idea es sencilla: tomar cada partido, averiguar qué jugadores fueron titulares, quién fue el árbitro y sus correspondiente fechas de nacimiento y ver si la teoría coincide con la práctica. Excluí de la experiencia a los jueces de línea, ya que conseguir sus datos era muy complicado y, después de todo, alcanza con 23 para que la esperanza matemática esté de nuestro lado (además, estrictamente hablando, no están dentro de la cancha :P).

Después de algunos scripts para parsear el fixture y un poco de trabajo manual me hice de una lista de partidos, con los jugadores y árbitros. La parte más complicada fue obtener las fechas de nacimiento. Estos últimos datos salieron de fuentes dispersas y no se que tan confiables, por lo que si algún lector friki encuentra algún error agradezco me lo haga saber.

Luego, con un poco de mi mediocre Python, escribí algunas lineas para ver en cuantas canchas del torneo coexistieron personas que pueden juntarse a festejar sus cumpleaños.

Los datos, los resultados y las conclusiones fueron:

  • En el torneo hubo 189 partidos. Son 20 equipos que jugaron todos contra todos, a excepción de Gimnasia vs Arsenal.

  • Participaron 484 personas, entre jugadores y árbitros.
  • Los nombres de pila más populares, en orden, son Juan, Pablo, Diego y Cristian.
  • Las colisiones se dieron siempre de a pares. Es decir, no hubo 3 o más personas en el mismo partido que cumplan años el mismo día.
  • En 11 partidos hubo dos pares de colisiones. Esto es curioso, porque se trata del 5,82% de los casos, cuando las probabilidades de que ocurran dos colisiones es del 22,5%.
  • En 4 partidos hubo tres pares de colisiones. Esto también es curioso, porque se trata del 2,11% de los casos, cuando las probabilidades de que ocurran tres colisiones es del 8,52%. Una de estas colisiones fue el superclásico River vs Boca.
  • La gran conclusión: hubo colisiones de cumpleaños en 94 partidos, lo que representa 49,74% del total de partidos.

El detalle de los resultados puede verse acá.

Querido pragmático experimentófilo, no se trata de otra tragedia de la ciencia. Afortunadamente, la matemática es la única ciencia donde la teoría siempre coincide con la práctica. Pero en el juego de las probabilidades, y si bajo la influencia de Paenza, hubiésemos apostado a todos los partidos del último campeonato, tal vez habríamos perdido algo de plata. Faltó un solo partido más con colisión para que la ganancia esté de nuestro lado... será el próximo campeonato.

El porcentaje 49,74% coincide casi a la perfección con la teoría. Es simpáticamente cercano (a 0,99 puntos) al número predicho, y es mucho más alto de lo que un simple mortal intuitivista podría haber arriesgado a primera vista :-).

Todos los archivos están codificados en utf-8. Las fechas están en formato día/mes/año

sudoku, algorítmos genéticos, la estrategia backtracking, programación lineal y R

/* Habiendo leído El curioso incidente del perro a medianoche le tomé cierto buen gusto a los títulos largos :-) */

Hace unas semanas, Mahoo me regaló un pequeño libro con un montón de sudokus para resolver. Si bien conocía el juego, nunca me atrajo particularmente. En esos días, yo estaba buscando algún tema original para uno de los trabajos prácticos de Inteligencia Artificial. La consigna se refería al uso de algoritmos genéticos para la resolución de algún problema. Lo importante no era el programa, sino el análisis de su comportamiento: estudiando, por ejemplo, qué método de cruzamiento se aplica mejor o qué función de aptitud es más representativa.

Viendo como Mahoo se entretenía con alguno de ellos (práctica en la que también se iniciaba) se me ocurrió que un resolver de sudokus podría ser una linda propuesta para mi TP.

Los algoritmos genéticos intentan emular a la naturaleza, a base de prueba y error, favoreciendo a las soluciones más aptas y castigando a las que no lo son tanto. Suponiendo que el cruzamiento de las buenas-soluciones generan aún-mejores-soluciones. Se trata de la búsqueda probabilística, muy parecida a meter muchas soluciones en un cubilete gigante y agitarlas hasta encontrar algo útil.

Al tratarse de un problema determinístico, la solución dista muchísimo de ser óptima. De hecho, ni siquiera se asegura que vaya a haber una solución. Pero me pareció algo simpático de intentar.

El resultado, escrito en mi rústico Python, puede ser bajado de aquí (incluye instrucciones para correrlo en Windows). No, no esperen que funcione bien, advertidos están. Es uno de los peores métodos posibles para este tipo de problemas. Sólo llega a una solución cuando la cantidad de incógnitas es (muy) limitada. Se plantean soluciones a base de llenar de random cada uno de los casilleros vacíos y chequeando cuantos valores se repiten en cada fila, columna y región. Cuando este chequeo da 0, se llega a una solución. Bastante cavernícola como notarán.

Es natural pensar en cuál sería la forma correcta de llegar a una solución. Recordé las clases de Investigación Operativa y la utilización del método simplex para la solución a problemas con restricciones. De hecho, es una solución que muchos proponen. No se si alguno de ustedes lo ha intentado. Yo sí, durante las clases aburridas me senté a pensar como sería el conjunto de ecuaciones y me encontré con una demencial y frustrante cantidad de ecuaciones. Acá hay una linda explicación, la que resumo, haciendo énfasis en las complicaciones:
Se necesitan variables binarias de la forma xijk donde 1 significa que el símbolo k (de 1 a 9) va en la celda (i,j) de la solución. 0 significa que no está. Esto genera un total de 729 variables (93) lo que, como mínimo, asusta. Veamos las ecuaciones:

(1) Para que cada celda (i,j) tenga un símbolo y éste sea único. Se necesitan 81 ecuaciones como éstas (una por cada celda).
(2) Para que en la fila i cada símbolo esté una vez y que en todas las columnas sea distinto. Se necesitan 81 ecuaciones como éstas(una por cada columna y cada símbolo posible).
(3) Para que en la columna j cada símbolo esté una vez y que en todas las filas sea distinto. Se necesitan 81 ecuaciones como éstas(una por cada fila y cada símbolo posible).
(4) Para que en cada región cada símbolo esté una y solo una vez. Se necesitan 81 ecuaciones como éstas (una por cada región y cada símbolo posible).
(5) Representa el enunciado, es decir, el problema a resolver. Por ejemplo, x115=1 significa que en la celda (1,1) hay un 5. Dependiendo cuantos casilleros vengan asignados es la cantidad de igualdades como estas que se necesitan; típicamente, ~30.
(6) Restringe las variables al conjunto binario.

¡En total son más de 350 ecuaciones! Hay propuestas con menos ecuaciones, pero siempre serán muchísimas. Evidentemente, ésta tampoco es la solución óptima (aunque es mucho mejor que los algoritmos genéticos). Y su problema radica en que, desde algún punto de vista, el método simplex no se ajusta al problema. Gráficamente, las ecuaciones representan semiplanos en un hiperespacio multidimencional (de 9 dimensiones?) cuya intersección es, en caso que haya una única solución, un único punto. /* Puede que le esté pifiando en esta conclusión final y cualquier ratificación o rectificación es bienvenida */

Simplex está pensado para restricciones de máximos y mínimos donde el objetivo es maximizar o minimizar y las variables binarias intentan ampliar el método para restricciones de este tipo. Da soluciones múltiples en forma de un polígono, donde a una o más se las llama óptima, porque maximiza o minimiza la función objetivo. Es claro que el problema del sudoku no usa sus ventajas y abusa de sus debilidades.

Curiosamente, cuando comenté este problema a un reciente conocido, surgió que también él tuvo que hacer un trabajo práctico que resolvía sudokus. En este caso, el TP giraba entorno a la gestión de la pila para recorrer árboles. Particularmente, árboles empleados en la estrategia de backtracking. Así pues, éste es su programita, sencillo, simpático y rápido. Gracias Nacho :).

Los métodos basados en búsqueda combinatoria sobre árboles parecen ser particularmente buenas para el problema del sudoku. En la wikipedia figuran dos interesantes formas: backtracking y ramificación y poda.

Para terminar, una última casualidad: Por razones que no vienen al caso ahora y que seguramente provocarán un nuevo post en el futuro estoy aprendiendo un lenguaje para el procesamiento de señales llamado R. Estoy trabajando mucho con una biblioteca llamada sound. Buscándola en el repositorio de bibliotecas, me encuentro con una llamada sudoku. No resistí la tentación de probarla :). Un ejemplo de su uso:

> install.packages("sudoku")
> # es necesario instalar tcltk si se quiere la parte gráfica
> install.packages("tcltk")
> library(sudoku)
> library(tcltk)
> library(tkrplot)
> miSudoku <- generateSudoku(Nblank=50, print.it=TRUE)
  +-------+-------+-------+
  |   6   |   7   |   8 2 |
  | 4 8   |     1 | 7     |
  |       | 8 2   | 5     |
  +-------+-------+-------+
  |       | 1     | 9 7   |
  |       |     2 |   5 1 |
  | 5 1 6 |   9 7 |       |
  +-------+-------+-------+
  |       |   4 8 |       |
  | 6 5   | 7   9 | 8     |
  |       |       |   9 7 |
  +-------+-------+-------+
> # la variable miSudoku es una matriz
> miSudoku
       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    0    6    0    0    7    0    0    8    2
 [2,]    4    8    0    0    0    1    7    0    0
 [3,]    0    0    0    8    2    0    5    0    0
 [4,]    0    0    0    1    0    0    9    7    0
 [5,]    0    0    0    0    0    2    0    5    1
 [6,]    5    1    6    0    9    7    0    0    0
 [7,]    0    0    0    0    4    8    0    0    0
 [8,]    6    5    0    7    0    9    8    0    0
 [9,]    0    0    0    0    0    0    0    9    7
> #La biblioteca incluye una función para para solucionarlo
> solveSudoku(miSudoku)
       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    1    6    5    9    7    3    4    8    2
 [2,]    4    8    2    5    6    1    7    3    9
 [3,]    3    7    9    8    2    4    5    1    6
 [4,]    2    4    8    1    5    6    9    7    3
 [5,]    7    9    3    4    8    2    6    5    1
 [6,]    5    1    6    3    9    7    2    4    8
 [7,]    9    3    7    2    4    8    1    6    5
 [8,]    6    5    1    7    3    9    8    2    4
 [9,]    8    2    4    6    1    5    3    9    7
> # Incluso trae soporte gráfico para resolverlo en una ventanita :)
> playSudoku()

Así fue como, un simple regalo, un TP universitario y un montón de simpáticas casualidades tuvieron su punto de conexión. Y que divertido que resultó ser :). Ahora tengo que escribir el informe sobre los algoritmos genéticos en el sudoku. La semana que viene espero publicarlo aquí.

UPDATE August 6th: El informe y los archivos relacionados ya está publicados.

Hollywood y Matemática

Todos sabemos que del bosque de acebos pueden salir de las más variadas clases de fenómenos. Pero pocos deben recordar a Danica McKellar. Tal vez alguien la ubique si les digo que su peinado de la niñez fue famoso gracias a una serie llamada Los Años Maravillosos [*] (aka The Wonder Years).

¿Todavía no la tienen?

En la misma serie hacía de Winnie Cooper, la inocente novia de Kevin Arnold (Fred Savage).

¿Ya casi?

Seguramente estas fotos le refresque la memoria a más de uno:

Es claro que si no la ubicaste a esta altura, posiblemente no sepas quién es. Para aquellos que sí saben de quien estoy hablando les digo: no se dejen engañar por estas imágenes ochentosas... los niños crecen. Crecen y se destacan en campos donde uno ni podría imaginarse.

Así como la ven, Danica McKellar es coautora de la demostración de un teorema matemático, llamado teorema de Chayes-McKellar-Winn y explicado en el paper Percolation and Gibbs states multiplicity for ferromagnetic Ashkin–Teller models on Z2. Me encantaría poder hacer algún comentario acerca de la publicación pero, obviamente, no tengo idea del tema. La muchacha en cuestión participó de la demostración incluso antes de graduarse en la Univerdad de UCLA y tiene un número de Erdős-Bacon igual a 6.

El número de Erdős-Bacon es una frikiada interesante, inspirada en la teoría de los seis grados de separación. Vamos por partes, resulta ser que existió un matemático húngaro llamado Paul Erdős. Éste muchacho realizó centenares de publicaciones (el segundo en cantidad después de Leonhard Euler). Así es como surge el número de Erdős, que se calcula así:

  • Erdös tiene número de Erdős igual a 0
  • Todo el que aparezca junto a él en alguna publicación tiene número de Erdős igual a 1
  • Todo el que haya publicado junto a alguien que aparece en alguna publicación junto a Erdős tiene número de Erdős igual a 2
  • Y así siguiendo...

Por ejemplo, el argentino Alberto Calderón tiene un número de Erdös de 3.

El número de Bacon es la versión hollywoodense de lo mismo pero con Kevin Becon. Ahora la relación no es "publicar con" sino "aparecer en los créditos de una película con".

El número de Erdős-Bacon es, sencillamente, la suma de ambos. Algunos ejemplos bizarros:

  • el mismo Paul Erdős tiene un Erdős-Bacon de 3. Obviamente, el primero de lo coeficientes es 0. El segundo se da al haber participado de la película N is a Number, donde Mark Adler puso la música original, al igual que en The Rat Pack, donde actuó Joe Mantegna, quién también actuó en Queens Logic con Kevin Bacon.
  • Matt Damon tiene un número de Bacon de 2, a través de Eric Bruno Borgman. Se hizo de un número de Erdős 3 cuando trabajó en Good Will Hunting, donde Dan Kleitman, un matemático con número 2, fue consultor técnico. Así Matt Damon suma 5 como número de Erdős-Bacon.
  • Por último, la principal protagonista de este post: Danica McKellar. Con valores 4 y 2 en los números de Erdős y Bacon respectivamente tiene un muy meritorio 6. En su publicación comparte la autoría con Lincoln Chayes quien trabajó con Roman Kotecký, y éste a su vez trabajó con David Preiss. Éste último realizó una publicación con Erdős en 1976.

Así fue como la frialdad del mundo del espectáculo se mezcló con la frialdad de las matemáticas.

Para terminar, hablamos mucho de Paul Erdős. Y de él es esta frase, propia de su irónica visión de las cosas:

Un matemático es un dispositivo que convierte el café en teoremas

[*] Alguién me comentó que en algunos lados se llamó Aquellos maravillosos años

(visto y fuertemente basado en Gaussianos)

mathematical beauty

Dado que esta semana tengo varios exámenes y que mi procrastinación me impidió estudiar, dediqué el fin de semana a la lectura.

Leí La Matematica como una de las Bellas Artes de Pablo Amster. Un libro entretenido, corto e interesante, que por momentos peca de subestimar al lector cuando no profundiza en algunos temas por tratarse "de cosas demasiado complejas". Si bien se trata de un texto de divulgación (aka. "estimular al lector antes que espantarlo" (sic)) en algunos de sus párrafos los fundamentos y explicaciones tienen sabor a poco.

Si sos de esas personas que, como yo, describen al Círculo de Euler como algo simpático, este libro puede interesarte. Mucha anécdota, mucha rareza y mucha clasificación filosófica. Cientoveintitantas páginas bastante entretenidas que invitan a pensar sobre lo lindo de la matemática y la belleza de los teoremas.

pi lover

Cuando uno se obsesiona con algo termina por convertirse en eso. A mí me está empezando a obsesionar los números, por lo que suelo pendular entre lo imaginario, natural, irracional, real y complejo, entre otros estados.

Con este cuadro, me imagino, no es raro encontrar cosas donde no las hay o patrones entre lo caótico. Pero díganme que no estoy loco, y que el número de emergencias del Subte no es un número al asar!

¿No será una nueva avanzada de la constante para conquistar el mundo? :P

UPDATE (20:25 UTC): En la página de Ministerio del Interior se puede ver lo siguiente:

Lo que me deja mucho más tranquilo.