/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)

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.

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 ;)

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....

porqué el 'Debian/OpenSSL debacle' no afecta mi creencia de que Debian es el mejor OS del mundo

En estos días escuché cosas como “Seguramente provocaste la mayor migración de usuarios de la historia, ya nadie querrá usar Debian en sus vidas”. Otros párrafos sobre la vergüenza que caía sobre los desarrolladores, sobre nuestros procesos de calidad llovieron de a decenas en mi inbox.

Este tipo de cosas me hizo reflexionar. Y es esta reflexión la que me gustaría compartir con ustedes.

Hace un tiempo ya, cuando casi sin querer y por accidente me encontré con el problema, simplemente me negué a creerlo. No podía ser. Era tan trivial y estuvo ahí, frente a nuestras narices tanto tiempo... parecía ser evidente de que yo estaba haciendo algo mal. Tardé mucho en confirmarlo, y aún con la duda lo reporté.

Junto a mi reporte adjunté un parche ridículo, casi insultante. Consistía en:
-/*
- * Don’t add uninitialised data.
MD_Update(&m,buf,j);
-*/

Esto fue el día 5 de Mayo. Al día siguiente tenía una respuesta, con una clara dirección de trabajo. A los pocos días se me informaron la fecha en la que el DSA saldría. Todo fue tan expeditivo, tan admitido, sin subestimaciones, pero con un fuerte sentido de la responsabilidad. Me pareció de una brillante sensatez el desarrollo de dowkd.pl antes del anuncio.

El 14 de Mayo el usuario tenía todos los elementos para defenderse. El paquete openssh-blacklist resultó ser sumamente útil y fue un aliciente entre el caos generado.

En mi vida no he enviado muchos advisories grandes (es el primero que hago totalmente por mi cuenta). Pero me pregunto: ¿Qué hubiese pasado si un problema como este hubiese surgido en algún otro software de alguna empresa? ¿Qué hubiese pasado si, en vez de ser un desarrollador de Debian el descubridor fuese un empleado de esta compañía? El bug dejaría de ser un vergonzoso accidente para convertirse en un devaluador de acciones. La baja de ingresos por clientes perdidos podría hundir la empresa.

En esta caso la historia hubiese sido distinta.

Es por esto que creo que el modelo de software libre es bueno, y en particular Debian es bueno, porque no responde a presiones comerciales, porque no oculta sus problema y porque su prioridad es el usuario.

Sin duda, problemas en el software habrá siempre. Sin duda, este fue un problema de proporciones épicas. Sin duda, la confianza en Debian se ha visto afectada. Pero la lección está aprendida. Y Debian sigue siendo mi sistema operativo favorito.

Esto no es una justificación, sino una profunda opinión personal.

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)