viernes, 22 de abril de 2016

EL PROBLEMA DE LOS CUATRO COLORES


           

Los cuatro colores
            Hay problemas de la matemática que empiezan con una pregunta inocente y van cobrando importancia a medida que se resiste a los mejores intentos de solución. Este es el caso del llamado Teorema de los cuatro colores que nos brinda un ejemplo claro de cómo trabaja la matemática a lo largo del tiempo.
            Los cartógrafos supieron desde siempre que cuatro colores son suficientes para colorear cualquier mapa plano, de modo que países con frontera común tuvieran colores distintos.
            En 1852 un estudiante le preguntó a su profesor de matemática, si conocía una demostración de tal hecho. El profesor era nada menos que Augustus De Morgan, un inglés que hizo aportes significativos a la teoría de conjuntos.
            Sin embargo al principio, la pregunta no despertó el interés de la comunidad matemática ni tampoco supieron responderla los pocos que lo intentaron. La dificultad del problema radica en que hay infinitos mapas planos posibles y de las formas más diversas. No hay una manera exhaustiva de atacar el problema porque aunque pruebe con muchos mapas, siempre hay otro con el que queda probar y la forma de los países puede ser de lo más caprichosa que uno se pueda imaginar.
Pasaron 25 años y en 1878 uno de los padres del álgebra moderna, Arthur Cayley consideró interesante el problema e intentó resolverlo pero sin éxito. Esto le dio visibilidad al problema y muchos otros se interesaron en él. Un año después, un abogado inglés de nombre Alfred Kempe presentó una demostración que reducía el problema a analizar cuatro configuraciones básicas de mapas.
Mapa de Martin Gardner. Antes de que saliera
la solución de Apel y Haken hizo una broma
afirmando que se necesitaban cinco colores.
El problema parecía resuelto. Sin embargo, 11 años después, en 1890, otro inglés, Percy Heawood, descubrió un error insalvable en una de las reducciones de Kempe. El problema quedó pues sin solución (abierto decimos los matemáticos) por muchos años. Conforme el tiempo pasaba, la fama del problema del mapa de los cuatro colores iba creciendo y el desafío era irresistible para muchos matemáticos y aficionados.
En 1969 H. Heesch introduce un método novedoso de análisis. Siguiendo las ideas del equivocado Kempe y las de Heawood (que también atacó el problema sin éxito), reduce el problema a 8900 configuraciones básicas. Una cantidad demasiado grande para poder analizar una por una pero un salto inmenso, teniendo en cuenta de que hay infinitos mapas.
Un día de 1976 el New York Times tenía en su portada la foto de dos matemáticos sonrientes que habían resuelto el problema. Kenneth Apel y Wolfang Haken consiguieron reducir la cantidad de configuraciones básicas a analizar solo 1476 mapas. Todavía un número grande para hacerlo uno por uno. Pero esta vez, contaban con un auxiliar inestimable que los matemáticos del pasado no habían tenido: la computadora. Appel y Haken diseñaron ingeniosos algoritmos para que las computadoras de hace 40 años, hicieran el resto. Decía el New York Times:
 “Ahora la conjetura de los cuatro colores ha sido demostrada por dos matemáticos de la Universidad de Illinois. Han usado una herramienta invaluable que matemáticos de otras épocas no tuvieron. La prueba descansa en su mayor parte en las 1200 horas de cálculos de computadora, lo cual significó unas diez mil millones de decisiones lógicas que había que hacer. La prueba de esta conjetura de los cuatro colores quizás no tenga una aplicación práctica, sin embargo, es uno de los mayores retos intelectuales de los seres humanos. Nos da en algún sentido una nueva visión de la naturaleza del espacio bidimensional y de las formas en que ese espacio puede dividirse en porciones discretas”.

            Así el Teorema de los cuatro colores quedaba demostrado aunque con la resistencia de muchos matemáticos por el uso tan potente de las computadoras. Una crítica de la época decía

“Una buena prueba matemática es similar a un poema, ¡pero esto es una guía teléfonica”
  La historia de este problema ilustra de una manera clara la aventura del pensamiento matemático: se formula el problema. El problema va ganando espacio en la comunidad científica. Se resiste. Éxitos parciales y estrepitosos fracasos. Muchos hacen aportes que serán esenciales para la solución, aunque tal vez nunca lo sabrán. El contexto social y tecnológico acompaña este proceso: lo que no es abordable en un momento, lo es a los pocos años. Finalmente la solución del problema. Parece el esquema del guión de una película de aventuras.


domingo, 8 de febrero de 2015

EL INFINITO

Agosto de 2013
O… LOS INFINITOS

El infinito ha sido siempre un tema de reflexión religiosa, filosófica y científica. Tres regiones del pensamiento humano con fronteras difusas y en permanente conflicto.
La idea del infinito produce simultáneamente vértigo y fascinación ya que es un concepto escurridizo y misterioso que cada vez que nos parece atraparlo, se nos escapa.
Así, como un cazador tenaz, la matemática ha perseguido a esta difícil presa que le ha provocado más de una sorpresa, alguna de las cuales, presentaremos en esta columna.

Ideas del infinito
El infinito es un concepto inherente al pensamiento humano. La clara percepción de nuestra finitud nos hace tener una idea del infinito desde muy pequeños. Estamos más dispuestos a aceptar el infinito por abstracto que nos parezca que la finitud del universo porque eso nos obligaría a aceptar la nada que resulta mucho más inquietante… Parece que preferimos el miedo al infinito que el horror a la nada…
Voy a ensayar algunas imágenes, prosaicas algunas y más poéticas las otras, que pretenden acercarnos a una idea del infinito.

El profesor loco
Se cuenta que un profesor de matemática, el día que tenía que explicar a sus alumnos lo que era el infinito, se apareció con una caja de tizas. Empezó a trazar una línea en el pizarrón de arriba hacia abajo. Cuando se le acabó el pizarrón, siguió en la pared y luego en el piso por el pasillo que conducía a la salida. Sus alumnos asombrados, lo vieron salir del aula y el portero, de la escuela, siempre con la tiza en la mano continuando la línea. Terminó la hora de clase y el profesor había desaparecido. En la calle se podía ver, calle abajo, la línea de tiza que el profesor no había dejado de trazar, pero ni rastro de él… Pasó una semana y a la clase siguiente, pasaron unos cuantos minutos sin que el profesor entrara a dar su clase. De repente, con tiza en mano, entró el profesor con la barba crecida, sucio y con claros signos de agotamiento. Siguió trazando una línea hasta que llegó al pizarrón donde se detuvo y dijo: “Esta es una línea larguísima, pero ni punto de comparación con el infinito…”

La sala de los espejos
La semana pasada estuve de jurado, junto con otros 16 colegas, en el Certamen Nacional de la Olimpíada Matemática Argentina. Nos tocó trabajar en un hotel frente al mar con salones muy amplios y señoriales. Uno de ellos, donde corregimos las soluciones a los problemas que los 500 estudiantes que participaron habían realizado, se llama el Salón de los espejos. Es muy hermoso y tiene la particularidad de que sus paredes, salvo los ventanales que dan al mar, están cubiertos de espejos. Si uno se para en el salón y mira hacia una de las paredes, ve como el salón se reproduce una y otra vez hasta el infinito. La misma sensación se tiene en algunos ascensores o baños que tienen espejos a ambos lados y dan la sensación de que jamás terminan…  

Borges y el infinito
Una figura más poética, es la que nos da Borges sobre el infinito en alguno de sus cuentos como El Aleph por ejemplo. Aleph es la primera letra del alfabeto hebreo y simboliza, con un poco de imaginación, a un
hombre con un brazo que toca la tierra y el otro brazo que señala el cielo como alegoría del intento humano de abarcar el infinito. En la Cábala es la ilimitada e infinita divinidad Borges, se propone describir el Aleph:

¿cómo transmitir a los otros el infinito Aleph que mi temerosa memoria apenas abarca? …Como una esfera cuyo centro está en todas partes y la circunferencia (se refiere al borde) en ninguna

La idea que toma Borges de los místicos es muy interesante porque se parece a la actual concepción del Universo: hago centro en cualquier punto, no importa cual, y considero esferas con centro en ese punto cada vez más grandes. A medida que aumento el radio (que termina siendo ninguno) van ocupando todo el espacio. 
Los físicos contemporáneos nos explican que una esferita de magnitud infinitesimal y masa infinitamente concentrada, en algún momento (mal usado la frase en algún momento pero el lenguaje y nuestra mente tienen limitaciones para describirlo de otra manera) produjo el Big Bang  y se expandió en todas direcciones.
Releo el Aleph de Borges porque es fascinante su similitud:
Una esfera cuyo centro está en todas partes y la circunferencia en ninguna

Las torres de Hanoi
Una última imagen me viene de mis años de estudiante de Álgebra. El profesor Gentile en su clase de
combinatoria nos contaba el siguiente problema que se conoce como las Torres de Hanoi y se comercializa hoy en día, como juego de ingenio en las jugueterías:
En un templo de la India se creía que Dios, al crear el mundo, colocó tres varillas de diamante como pequeños obeliscos de metro o metro y medio cada uno. En la primera de las varillas, ensartó 64 discos de oro (con un agujero en el medio para poder ensartarlos en la varilla) todos de distinto diámetro. Los discos estaban ordenados por tamaño. En la base de la pila de discos el de mayor diámetro y arriba de todo el de menor diámetro. Los monjes del templo, cada hora tenían que mover un disco de oro que estuviera arriba de una pila de discos, de una varilla a otra, con el objetivo de pasar todos los discos a la tercera de las varillas. La única regla que había puesto Dios, era que nunca un disco de diámetro menor podía estar debajo de un disco de diámetro mayor. Es decir, siempre en una pila de discos, los discos debían estar desde el más ancho al más pequeño. Cuando los monjes terminaran con el trabajo el mundo terminaría. Esta tarea tenía entretenidos a los monjes y los obligaba a organizar turnos para no desobedecer a la divinidad.
El problema con el que nos desafiaba el Dr. Gentile era saber después de cuántos años sobrevendría el fin mundo si la leyenda fuese profecía. Volví a hacer la cuenta para esta columna y volví a sorprenderme como cuando era estudiante. En la cuenta interviene la exponencial y su crecimiento del que ya hablamos en otra columna y vimos de lo que era capaz de provocar. Efectivamente, la cuenta nos dice que pasarán más de 2 mil billones de años. Es decir, si aceptamos que desde el Big Bang han transcurrido 15 mil millones de años, el Universo es todavía muy joven para estos monjes hindúes. Transcurrirán 140 mil veces más 15 mil millones de años siempre que los monjes sigan allí haciendo su trabajo...
El número es 2 105 792 702 478 259
La leyenda terminaba diciendo que, una vez completada la tercera varilla con los 64 discos como Dios manda, empezará la infinita eternidad…
El juego de las Torres de Hanoi se debe al matemático Eduard Lucas y en las jugueterías no tiene 64 discos sino 5 por las razones que acabo de contar: no hay humano que pudiera terminar de lograr el objetivo con 64 discos. Parece que la leyenda también se debe Lucas y que es apócrifa. La usó solo para promocionar su juego que resulta ser un hermoso juego de ingenio y lo recomiendo para los que le gusta este tipo de entretenimientos. Como en la leyenda hay que pasar los 5 discos de la primera varilla a la tercera varilla con la regla de Dios, de que nunca un disco puede estar arriba de un disco de menor diámetro que dicho disco. En este caso la cantidad de movimientos necesarios es igual 31.

El infinito entre los griegos
Estas imágenes, dan en alguna medida, una sensación de lo que puede ser el infinito pero lo describen más como un adjetivo que como un sustantivo.
Como me suele pasar en estas columnas, cada vez que voy en búsqueda de los primeros vestigios de un concepto, casi siempre termino en la cultura griega y en sus primeros filósofos y matemáticos.
Los griegos definían el infinito como lo que no tiene límite. Sabemos que nadie puede construir toda la serie de números naturales 1, 2, 3, 4, … pero potencialmente sabemos que no tiene límite. Los griegos aceptaban este tipo de infinito potencial, aquel al que se podía llegar potencialmente pero que en realidad era inaccesible. Decía Aristóteles:

No es posible que el infinito exista como ser o como substancia (lo que llamaríamos infinito real o actual)… Está claro que la negación absoluta del infinito es una hipótesis que conduce a consecuencias imposibles... de modo que solo existe potencialmente…

Esta prohibición aristotélica del infinito real no les permitía concebir, por ejemplo una línea (un segmento de recta) como una colección infinita de puntos alineados y hubo que esperar hasta finales del siglo XIX para tener un concepto más claro del infinito actual. Aún hoy, estudios estadísticos, muestran que más de la mitad de la población no acepta la existencia del infinito actual. Vamos a tratar en esta columna de sumar algunos más para el bando de los que creemos en él, por lo menos como un modelo adecuado para entender el universo.  

  
Zenón de Elea
A pesar de esta aversión por el infinito, los griegos se valieron de él para argumentar a favor o en contra de teorías propias y ajenas.
Para los pitagóricos el universo era plural y la idea de número era la base con la se explicaba todo en él. El tiempo y el espacio eran susceptibles de ser medidos.
Una corriente filosófica rival liderada por Parménides planteaba justo lo contrario: el Universo era inmóvil e infinito. Zenón de Elea (sur de Italia) discípulo de Parménides, generó una serie de argumentos que hoy se conocen como Paradojas de Zenón que inauguraron el método dialéctico de reducción al absurdo hoy imprescindible no sólo en la matemática sino también en las ciencias, sean éstas sociales o exactas… Supongo que tu hipótesis es verdadera y llego a una contradicción, por lo cual tu hipótesis es falsa.
Por ejemplo, Zenón, fiel a su maestro que decía que el universo era inmóvil trató de demostrar que el tiempo era indivisible y que, por lo tanto el movimiento era imposible y que sólo es una percepción de los sentidos. ¡Menudo enunciado para ser digerido!
El argumento de Zenón era el siguiente. Si quiero ir de Buenos Aires a Mar del Plata, digamos a 400 km una de la otra, si marcho a una velocidad constante de 100 km por hora, todo el mundo sabe que tardaré 4 horas en llegar. Pues bien, para recorrer los primeros 200 km me llevará 2 horas de tiempo, pero me quedarán 200 km por recorrer. Para recorrer estos 200 km tendré que recorrer primero, 100 km en 1 hora más. Ya van 2 horas más 1 hora, 3 horas de viaje y todavía me faltan 100 km por recorrer. Para recorrer estos 100 km, primero hay que recorrer 50 km. Media hora más de viaje y todavía faltan 50 km. Para recorrer la mitad de ellos, 25 km, tendré que usar 15 minutos más, quedan 25 km. Pero antes debo recorrer la mitad de 25 km en la mitad de 15 minutos, quedan 12 km y medio. Antes de llegar tengo que recorrer la mitad de 12,5 km en la mitad de la mitad de 15 minutos y así siguiendo, siempre va a faltar un tramo por recorrer para el que tendré que gastar un instante más de tiempo, de modo que tardaré una cantidad infinita de instantes (cada uno la mitad del anterior) en llegar. Concluía Zenón, como la suma infinita de tiempos me dará infinito tiempo, nunca podré llegar al Casino de Mar del Plata ni mojarme los pies en el mar, por lo que el movimiento es imposible.
Los amantes del mar pueden quedarse tranquilos porque lo de Zenón es falaz, en el sentido de que la suma de infinitos números SI puede ser un número finito, como es en este caso. En el curso de Análisis del Ciclo Básico, nuestros estudiantes aprenden a sumar sumas infinitas y ven cómo esta suma geométrica termina dando 4 hs como era de esperar. La historia fue un poco injusta con Zenón, porque a pesar de estar equivocado, dio lugar a casi 2 mil años de cavilaciones sobre el tema e inauguró una manera de razonar que fue madre de muchísimas teorías. Vaya pues mi homenaje a Zenón que más que griego parece un personaje gauchesco.

Los infinitos de Cantor
Me voy a meter en un terreno inquietante: el del infinito actual o real al que Aristóteles se negaba siquiera considerar. Más aún, voy a tratar de convencerlos de que hay más de un infinito. Es una buena oportunidad para cambiar de radio o para que los que nunca  pensaron en estas cuestiones se sorprendan como me sorprendí yo.

En 1870 el matemático George Cantor, ruso de nacimiento y residente en Alemania de niño, enunció un resultado importante del análisis matemático sobre la representación de fenómenos físicos con sumas infinitas (llamadas series de Fourier) un poco más complejas que las sumas de Zenón. Pero su resultado tenía un problema: tenía excepciones… y no eran pocas. Es más, fallaba en infinitas ocasiones. Esto lo motivó a estudiar un poco más la estructura del conjunto de números reales.
Así comenzó a nacer lo que se dio en llamar teoría de conjuntos que revolucionó la matemática de la primera mitad del siglo XX y la educación matemática de gran parte de la segunda mitad.
Antes de Cantor, el infinito se representaba con el famoso símbolo del ocho acostado que al igual que el halo de los santos, da idea de algo que nunca termina. La carta de Tarot que representa al gran Mago lo hace con un halo con el símbolo del infinito como el halo de los santos. En realidad no es un ocho acostado sino una curva que en geometría se llama lenmiscata, pero eso es otra historia.
Cantor vislumbró la idea de que había distintos tipos de infinito. Es allí donde aparece la primera letra hebrea Aleph que Cantor usa para indicar los sucesivos infinitos. Con Aleph – cero, Cantor indicó el primer infinito, con Aleph – uno al siguiente y así siguiendo… Los llamó números transfinitos.

El Hotel de Hilbert
Pero vayamos más despacio…
Para entender la idea de Cantor, tenemos que recordar qué quiere decir contar.
Imaginemos que tenemos un hotel con 10 habitaciones singles y 10 pasajeros que llegan en forma independiente. Uno puede decir que hay tantas habitaciones como pasajeros. Pero aún sin saber la cantidad de habitaciones y de personas podemos saber, si dos conjuntos tienen la misma cantidad de elementos. Pensemos en dos chicos de dos o tres años con una bolsa de caramelos. No saben cuántos hay ni saben contarlos pero si pueden repartirlos: uno para vos, uno para mí, uno para vos, uno para mí… hasta terminar la bolsa. Si hay una cantidad par de caramelos ambos chicos, que no saben contar, tendrán la certeza de que tienen la misma cantidad de caramelos. En el caso del hotel también se podría haber llegado a la misma conclusión haciendo entrar en cada habitación un pasajero y comprobando que se establece una correspondencia perfecta entre cantidad de habitaciones y cantidad de pasajeros.
Cantor observó que entre conjuntos finitos es lo mismo decir que tienen la misma cantidad a que entre ellos se establece una correspondencia perfecta, “uno a uno” entre ellos y usó esta idea simple y elemental para contar conjuntos infinitos. Entre conjuntos infinitos se pierde la idea de cantidad pero no la de correspondencia perfecta “uno a uno”.  Para dos conjuntos infinitos podemos establecer correspondencias perfectas como hicimos entre los 10 pasajeros y las 10 habitaciones o con los caramelos. Pero comienzan a ocurrir cosas raras…  
Sigamos con el ejemplo del hotel. Ahora tenemos un hotel de infinitas habitaciones singles. Las hemos numerado 1, 2, 3, etc.
Imaginemos que tenemos todas las habitaciones ocupadas. En estas circunstancias llega un pasajero pidiendo una habitación.
-         Señor, lamentablemente tenemos el hotel lleno y no le podemos dar una habitación.
-         ¿Pero cómo? Es de noche, estoy cansado y me dijeron que el hotel Hilbert – que  así se llama nuestro hotel – tiene  infinitas habitaciones.
-         Si señor, pero están todas ocupadas. Es imposible darle un lugar. Lo lamento.
Sigue la discusión hasta que llega el conserje, que en nuestro cuento se llama George (como Cantor) e interviene para solucionar el problema.
-         No se preocupe, el hotel Hilbert nunca deja a un pasajero sin hospedaje. En unos momentos le haremos lugar.
¿Qué hace nuestro conserje George? Le pide al huésped de la habitación 1 que se pase a la 2, al de la 2 que se pase a la 3, al de la 3 que se pase a la 4 y así siguiendo. Terminado este proceso infinito, nos queda libre la habitación 1 para el recién llegado. Todos felices.
Pero al día siguiente, llega una delegación de infinitas personas que quieren alojarse en el hotel Hilbert. Nuestro conserje no pierde la calma. Le pide ahora al huésped que ocupa la habitación 1 que se mude a la 2, al de la 2 que se mude a la 4, al de la 3 que se mude a la 6 y así a cada huésped que se mude a la habitación que tenga como número el doble de la que estaba ocupando. Quedan vacías todas las habitaciones con numeración impar (¡que son infinitas!) y pueden entrar los nuevos e infinitos huéspedes. En otras palabras, una parte del todo es igual al todo. La cantidad de pares (que es una parte propia de todos los números) resulta ser la misma que la de todos los números.     

Esta perplejidad del hotel fue creada por David Hilbert, con la intención de explicar las cuestiones paradójicas que surgen con los números transfinitos introducidos por Georg Cantor.
El menor número transfinito (aleph–cero: א0) es el que representa la cantidad de números naturales (1, 2, 3,…). Debo apresurarme a decir que no es un número propiamente dicho sino un indicador de que todos los conjuntos que se puedan poner en correspondencia “uno a uno” con él tienen en este nuevo mundo del infinito, la “misma cantidad” de elementos.
Como vimos se producen curiosidades tales como que cualquier subconjunto infinito propio (por ejemplo el de los números pares) tenga la misma cantidad de elementos que el total de números naturales.
La correspondencia perfecta o “uno a uno” que demuestra esta afirmación es la que asigna a cada número su doble.
n -----> 2n


Densidad e infinito
El flujo continuo que imaginaban los pitagóricos con el que se explicaba el universo se basaba en la idea de la densidad que tienen los números y que también nos hace chocar con la idea del infinito. Todos sabemos que después del 4 viene el 5, cuando estamos usando los números para contar (los días del mes por ejemplo). Sin embargo, esto deja de ser cierto si a la colección de números les agregamos las fracciones. Entre 4 y 5 está por ejemplo, el número 4,5. Entre el 4,5 y el 5 está el 4,75… Siempre entre dos números cualesquiera hay otro número fraccionario. Se pierde la idea de “número siguiente”. Mientras que entre los naturales el siguiente del 4 es el 5, no hay un número siguiente al 4 entre los números fraccionarios. Esto es inquietante. Cada candidato a ser el siguiente, por esta idea de la densidad, encuentra uno anterior (el promedio entre 4 y el candidato por ejemplo). De la misma manera, no hay número siguiente al cero. Por pequeño que elija a un supuesto candidato siempre puedo encontrar a otro más pequeño que él (la mitad del candidato por ejemplo).
Vuelvo a valerme de Borges que, como no podía ser de otra manera, se fascina con esta idea y lo refleja en su cuento el Libro de Arena. En un momento al personaje (que es el mismo Borges) es desafiado a abrir el libro de Arena por la primera hoja:
Me dijo que su libro se llamaba el Libro de Arena porque ni el libro ni la arena tienen principio ni fin (otra vez el infinito en la literatura de Borges)

Me pidió que buscara la primera hoja. Apoyé la mano izquierda sobre la portada y abrí con el dedo pulgar casi pegado al índice. Todo fue inútil: siempre se interponían varias hojas entre la portada y la mano. (Infinitas hojas me permito corregir a Borges). Era como si brotaran del libro.

Otra vez Borges juega con el infinito en su literatura con una sutileza y maestría maravillosa.




Las fracciones no son tantas como parecen
Pero volvamos a George Cantor y a su obsesión por el infinito. Hasta aquí hemos encontrado que la cantidad de números naturales es la primera clase de número transfinito. Cantor se preguntó ¿qué pasa con el conjunto de las fracciones?
Para su sorpresa (y la de muchos de sus colegas) vio que las fracciones eran la misma cantidad que los números naturales. Es decir que pueden venir infinitos pasajeros al hotel de Hilbert cada uno con una fracción distinta en su remera, que todos encontrarán una habitación para alojarse. Esto ya era mucho para Cantor. Le escribió a su amigo y matemático Dedekind “lo veo pero no lo creo”. Pero era creer o reventar porque la demostración de Cantor estaba allí. Cantor ideó una simple correspondencia “uno a uno” que asocia cada número natural a cada fracción.
La cuento rápidamente pero si no se entiende, los invito a buscarla en la web (Ver Segunda Muestra de Matemática) o en el libro Qué es la matemática  de Courant – Robins o también en unas conferencias del escritor Guillermo Martínez editadas como Borges y la Matemática del que tomé algunas cosas para la columna de hoy.
Supongamos que el Hotel de Hilbert tiene la siguiente disposición de sus habitaciones. En el primer piso está el comedor y el centro de reuniones. Las habitaciones están ubicadas a partir del segundo piso: una habitación en el segundo piso, 2 habitaciones en el tercero, 3 en el cuarto y así hasta el infinito. Están numeradas 1, 2, 3, etc. empezando desde el segundo piso hacia arriba. De modo que el hotel tiene la misma capacidad de siempre: aleph – cero podemos decir ahora con autoridad académica.
Llegan al hotel infinitos huéspedes, cada uno con una remera que tiene dibujada una fracción. Está el señor que tiene la remera con 3/5 y el señor o la señora que tiene en la remera el 25/2. Todas. Incluso algunas con remeras que representan el mismo número: por ejemplo dos hermanos que tienen el 1/3 uno y 2/6 el otro.
-         Son infinitos – dice el empleado que está en el mostrador. ¡Para colmo están densos y ansiosos con conseguir su habitación!  Se pegotean unos con otros…
George, nuestro conserje, una vez más, viene en nuestra ayuda.
Una fracción se arma con dos números: el numerador que va a arriba y el denominador que va debajo de la raya de fracción. George suma esos dos números y con eso determina el piso en el que va a ubicar a ese huésped.
En el segundo piso, coloca en la habitación 1, la única del piso, al 1/1 que es la  única fracción que suma 2.
En las dos habitaciones del tercer piso ubica 1/2 y al 2/1.
En las tres habitaciones del cuarto piso duermen el 1/3 , 2/2 y 3/1
… …
En cada piso se alojan las fracciones que tienen la misma suma entre numerador y denominador.  Por ejemplo el 25/2 se aloja en el piso 27 junto entre otros, con el 24/3. Nuestro conserje encontró una correspondencia perfecta “uno a uno” de modo que hay tantas fracciones como números naturales.
Lo veo y no lo creo dijo Cantor. Su incredulidad era comprensible. Recordemos la idea de Borges en el Libro de Arena. Entre el cero y el 1 hay infinitos fracciones. El cero sería la tapa del libro de Borges mientras que el 1 sería la contratapa. Por más que Borges se esforzara siempre cuando abría el libro quedaban infinitas páginas antes. Más desconcertante aún (aunque Borges no lo dice), según la correspondencia de Cantor, es que la hoja en la que abría Borges el libro de Arena tenía un número de página… Lo veo y no lo creo. ¿Cómo creer algo que choca tanto con la intuición?  

Un infinito más grande
Hasta aquí, uno podría explicar estos sorprendentes descubrimientos diciendo que todos los conjuntos infinitos pueden ponerse en correspondencia perfecta y que es poco interesante estar contando clases de infinitos ya que todo es lo mismo. De hecho vimos que los fracciones que son densas, están pegoteadas al punto que siempre entre dos podemos encontrar otra, también son Aleph – cero como los naturales y todas podrían descansar en el hotel de Hilbert. Pero Cantor fue más allá.
En términos de los números decimales, los números fraccionarios son aquellos que tienen un desarrollo que termina (1 medio es igual 0,5 y siguen ceros) o que tienen un desarrollo periódico (0,3333,… es un tercio y 0,201320132013… también es un número fraccionario que se puede calcular).
Los números que no son fracciones se llaman irracionales y tienen desarrollos decimales no periódicos. Por ejemplo la raíz cuadrada de 2 (lo que mide la diagonal de un cuadrado de lado 1) o pi son ejemplos de números irracionales. Los pitagóricos fueron los primeros en darse cuenta de que había medidas, como la diagonal del cuadrado de lado 1 que eran incomparables (inconmensurables es más preciso) con fracciones exactas de la unidad. Fue un golpe terrible para su filosofía, al punto de que cuenta la leyenda que Hipaso, su descubridor, fue asesinado por la secta por tal herejía.

Cantor descubrió que cuando agregaba los números irracionales, los que tienen desarrollo decimal no periódico, éstos eran más que los naturales y que las fracciones. En otras palabras que si todos esos números venían al hotel de Hilbert, no alcanzarían las habitaciones para ubicarlos y nuestro ingenioso conserje se vería superado por las circunstancias…
Aunque la demostración de Cantor es elemental y no requiere matemáticas sofisticadas, no puedo contarla por radio. Solo diré, en honor a Zenón, que usó la misma idea de reducción al absurdo para su demostración y que es de una belleza infinita. No dejen de verla en algún libro o en la web.
Lo que puedo es tratar de convencerlos de que es como Cantor dijo: los reales son más.
Aceptemos, como todos vimos en la escuela y les dije hace un momento, que las fracciones tienen un desarrollo decimal que en algún momento termina o se repite. Las así llamados números decimales periódicos.
Los no periódicos son los restantes números reales que llamamos irracionales.
Ahora imaginemos que tenemos un dado de 10 caras, con los números del 0 al 9.
Con Analía jugaremos a un juego imaginario e infinito:
Yo voy a apostar por los irracionales y Analía por las fracciones.
Con el dado nos vamos a construir un número decimal. Si el número resultante es irracional, yo gano, si sale fraccionario, gana Analía. El número lo vamos a ir construyendo al azar con el dado de la siguiente manera.
Tiramos el dado una vez. Supongamos que sale 4 por decir algún número. Anotamos 4. Volvemos a tirar el dado y sale 1 que será el primer decimal. Anotamos 4,1. Otra vez y vuelve a salir 4, anotamos pues 4,14. Una vez más y sale 7, anotamos 4,147. Repetimos esto infinitas veces y nos queda al final del juego un número decimal con infinitas cifras decimales.
Si tiene una cola infinita de ceros o se repite una tira de su parte decimal a partir de una tirada y para siempre, será una fracción y ganará Analía. Pero si el número no tiene ninguna regularidad en su desarrollo decimal que lo haga periódico, yo gano.
¿Qué les parece que será más probable? ¿Ganaré yo o ganará Analía? ¿A favor de quién van las apuestas?
En términos de probabilidad, Analía tiene probabilidad cero de ganar mientras que yo tengo probabilidad del 100 por 100 de obtener un número no periódico. Y esto ocurre porque hay más números irracionales que fraccionarios.
Una vez más, podemos decir:   Lo veo y no lo creo

El infierno de Cantor
George Cantor nació en Rusia, de padres dinamarqueses, pero desde los 11 años vivió en Alemania. En 1874, junto con el nacimiento de su Teoría de Conjuntos y su “aritmética de los números transfinitos”, nacía una feroz oposición a ella, encabezada por uno de sus maestros, L. Kronecker. La idea del infinito, que como vimos siempre estuvo en el foco de controversias, hicieron eclosión en la vida y la obra de Cantor. Pronto estas diferencias científicas se convirtieron en cuestiones personales. Kronecker llegó a calificar de “renegado” y “charlatán” a Cantor y a negar o demorar la publicación de alguno de sus trabajos en la revista en la que era editor: Los números los hizo Dios, lo demás es invento de los hombres, escribió Kronecker para descalificar a Cantor. Esta disputa personal no ayudaba a una salud débil de Cantor que toda su vida padeció de una serie de colapsos nerviosos que hoy se cree eran una psicosis maníaca depresiva que se fue agudizando con los años. Algunos especulan que su enfermedad, lejos de desempeñar un papel totalmente negativo, pudo haber proveído de la energía y tenacidad obsesiva con las que promovió sus ideas. Pero me cuesta consolarme con esa idea tan deshumanizante.
En 1884 tuvo la primera de esas crisis nerviosas que lo iban a acompañar durante los últimos 33 años de vida. Hacia el final de su vida, obtuvo el merecido reconocimiento. Murió en 1918 en un sanatorio para enfermos mentales.
El reconocimiento de uno de los matemáticos más grandes de su época, basta para dimensionar su obra. Dijo Hilbert de la aritmética transfinita:

El más sorprendente producto del pensamiento matemático y una de las realizaciones más bellas de la actividad humana en el dominio de la inteligencia pura.
Nadie nos expulsará del paraíso que Cantor ha creado para nosotros.

La hipótesis del continuo
Una última sorpresa.
Cantor llamó a la cantidad de números reales con la letra c de continuo porque los números reales “llenaban” todas las medidas posibles y conjeturó que entre el Aleph – cero de los números naturales y las fracciones y el continuo no había ningún número transfinito. Es decir, que el continuo era Aleph – uno. La Hipótesis del Continuo que así se pasó a llamar esta conjetura, fue formulada por George Cantor en 1874 pero no logró demostrarla a pesar de que le dedico muchísimo tiempo y esfuerzos.
Hilbert, lo presentó entre los 23 problemas célebres a resolver durante el siglo XX en su conferencia en París del año 1900 durante el Congreso Internacional de Matemática
A mitad del siglo Gödel, demostró que había ciertos enunciados de la matemática que eran indescidibles por verdad o mentira con las premisas o axiomas con los cuales se construía cualquier teoría matemática. Esto inquietó a los matemáticos pero Gödel no pudo mostrar ningún ejemplo. Solo demostró que existían tales enunciados.
En 1963 Paul Cohen, demostró que la Hipótesis del Continuo es un problema indecidible en el sistema axiomático habitual. Esto es que el sistema axiomático no tiene contradicciones sea cierto o no la Hipótesis del Continuo. ¡Bien difícil para entender!  Será para contar en una próxima columna.


El desafío
Me despido de este espacio, como es habitual, con un desafío.
Se trata de un juego. Sobre una mesa rectangular (no son importantes sus medidas) Analía y yo jugamos al siguiente juego. Por turno, cada uno coloca una moneda de un peso en la mesa. Tenemos muchas monedas. La única condición es que la moneda que colocamos, no se encime con ninguna moneda ya colocada ni que tampoco mueva o empuje a ninguna moneda ya colocada. Podemos agregar como regla que la moneda no sobresalga de la mesa para evitar conflictos con la gravedad o el viento. La mesa se irá llenando de dinero. Llegará un momento en que será difícil encontrar un lugar para ubicar la moneda. Hasta el punto que alguno de los dos no lo podrá hacer. Al que le pasa eso pierde el juego y el otro se queda con todas las monedas.
El desafío es:
¿Qué conviene, ser el primero en jugar o el segundo?
Respondida esta pregunta, ¿cómo debo jugar para asegurarme el triunfo?



jueves, 5 de febrero de 2015

CODIGOS

Agosto de 2013
La criptografía
La clave es hallar la clave
La generación de claves secretas que permita transmitir información segura, fue uno de los problemas más importantes a resolver a lo largo de la historia. Con la posibilidad de desarrollar lo que hoy conocemos como Internet, este problema se convirtió en el mayor desafío de la posguerra. La criptografía, rama de la matemática, fue protagonista en esta y otras encrucijadas de la historia de la humanidad.
 A lo largo de la historia, gobernantes, generales y poderosos han dependido de comunicaciones eficientes y seguras para llevar adelante sus propósitos fueran estos nobles o no tanto. Todos ellos eran conscientes de las consecuencias negativas que se podían producir si alguno de sus mensajes y comunicaciones caían en manos equivocadas.
Este temor de que el enemigo interceptara mensajes secretos, motivó el desarrollo de códigos y cifrados que aseguraran que los mensajes sólo fueran leídos por los receptores a los que iban dirigido. Al mismo tiempo, la posibilidad de conocer por anticipado los planes de un rival, sirvieron para desarrollar el arte y las técnicas para descifrar códigos llamado criptoanálisis. Unos y otros, han librado una guerra silenciosa que atraviesa toda la historia de la humanidad.
Con la llegada de Internet esta preocupación se democratizó. Recientemente hemos tomado cuenta de escándalos de espionaje a través de las redes sociales y de Internet. Los nombres de Assange (asilado en la embajada de Ecuador en Inglaterra) y de Snowden (asilado en Rusia) han cobrado notoriedad en los últimos meses por dar pruebas de lo que muchos intuíamos: los imperios vienen haciendo espionaje a gran escala.
Voy a contar algunos momentos de la historia donde la matemática, a través del cifrado y descifrado de códigos secretos, jugó un papel crucial y cambió el rumbo de la historia. Ustedes juzgarán si para bien o para mal.
Tristemente, estos momentos tienen que ver con etapas oscuras de la historia, como lo fueron por ejemplo la Primera y la Segunda Guerra que se desataron el siglo pasado. Dudé un poco en relacionar a la ciencia que amo con acontecimientos tan terribles, pero después de pensarlo un poco, acabé por pensar qué son en esas circunstancias terribles cuando se generan las encrucijadas más notables de la historia.
Hagamos un poco de historia.
Aunque hay antecedentes hasta mitológicos, uno de los primeros en usar códigos en forma sistemática para ocultar sus mensajes fue Julio César. El método que usaba, básicamente, era el de reemplazar cada letra por otra: la A por la H, la B por la I y así hasta completar todo el alfabeto. Si el receptor sabía la correspondencia de cada letra, no tenía problemas en decodificar los mensajes que llegaran en clave. Variantes de este método de sustitución se usaron durante cientos de años. Uno notable que registra la historia fue
La Conspiración de Babington
Ubiquémonos en el 1586 en Inglaterra. El 15 de octubre de ese año, María Estuardo, reina de Escocia, entró en la sala de justicia del castillo de Fotheringhay. Se la acusaba de traición por liderar a un grupo de jóvenes nobles católicos, decididos a eliminar a la reina Isabel, protestante y sustituirla por María, católica como ellos. A pesar de la grave acusación y de años de encarcelamiento, se la veía tranquila y segura. Era difícil para el tribunal demostrar el vínculo entre los conspiradores y ella. Para Isabel había razones políticas para no condenar a muerte a su prima. Necesitaba pruebas contundentes para tomar una decisión tan drástica. Al fin de cuentas además de primas, ambas eran reinas y lo que hoy le pasara a una, mañana le podría pasar a la otra…
En realidad María había autorizado toda la trama pero se había asegurado que toda su correspondencia con los conspiradores se hubiera escrito en clave; una suerte de nomenclador que reemplazaba letras por símbolos y algunas palabras usuales tales como “cuando”, “no” “esto” y otras más con símbolos especiales. La clave convertía sus dichos en una serie de símbolos sin sentido y que, incluso si hubieran sido interceptadas por los servicios secretos de Isabel, no podrían deducir el significado de las mismas. “¿Se me puede hacer responsable de los proyectos criminales de unos pocos hombres desesperados que planearon sin mi conocimiento? argumentó María en su defensa.
Desgraciadamente para María, Sir Francis Walsingham, secretario privado de Isabel y jefe del espionaje de Inglaterra, no solo había interceptado la correspondencia sino que encargó a Thomas Phelippes, un experto analista de cifras, que le dijera el contenido de la correspondencia. Walsingham había descubierto la existencia de la codificación en un libro del matemático italiano Cardano, del cual hablaremos en otra columna. Phelippes estudió cada carta que Walsingham le entregó. Analizando la frecuencia con la que aparecía cada símbolo y comparándolo con la frecuencia que aparece cada letra en el leguaje corriente fue experimentando posibles valores de cada uno de ellos y logró descifrar los mensajes. En uno de ellos, Sir Babington proponía a María Estuardo el asesinato de Isabel. Walsingham esperó la respuesta de María con la que firmaría su sentencia de muerte. Cuando ésta llegó no se detuvo allí. Para destruir completamente la conspiración, le pidió a Phelippes que falsificara una posdata a la carta de María (codificada obviamente) donde invitara a Babington a dar nombres: “Me alegraría conocer los nombres y las cualidades de los seis caballeros que llevan a cabo el plan…”. El 8 de febrero de 1587 en la misma sala del castillo, María fue decapitada. 

La lección que nos da esta historia, es que una codificación débil puede ser peor que no codificación en absoluto. Tanto Babington como María fueron explícitos en sus intenciones, confiados de que el cifrado les brindaba seguridad.

El telegrama de Zimmermann
A fines del siglo XIX y principios del XX los criptógrafos estaban buscando una nueva cifra que fuera segura. El criptoanálisis, tal como lo había hecho Phelippe en la historia anterior, había derribado uno a uno las variantes que se fueron creando. El desciframiento más notable de esta época fue el de un telegrama que cambió el rumbo de la primera guerra.
A pesar de la demandas de propios y ajenos, el presidente Wilson se negaba a intervenir y mantenía a los Estados Unidos neutral. En 1916 Alemania designa un nuevo ministro de Asuntos Exteriores: Arthur Zimmermann. Los diarios estadounidenses titularon “Nuestro amigo Zimmermann” y “Liberalización de Alemania”. Sin embargo, Zimmermann tenía otros planes. El 9 de enero de 1917 participó de una reunión donde el Alto Mando Supremo le planteó al Káiser alemán el siguiente plan:
1) emprender desde el 1 de febrero, una guerra submarina sin restricciones con los 200 submarinos con los que contaban. Esto cortaría las líneas de suministro británicas y haría que el hambre la obligara a rendirse en menos de seis meses.
2)  El ataque submarino sin restricciones provocaría necesariamente el hundimiento de barcos civiles norteamericanos y esto la empujaría a la guerra. Era esencial obtener una rápida rendición antes de que Estados Unidos entrara en la guerra.
3) Para demorar la intervención de Estados Unidos, Zimmermann enviaría (y así lo hizo) un telegrama a México para proponerle a este país, que le declare la guerra a EE UU, exigiendo los territorios perdidos de Texas, Nuevo México y Arizona. A cambio Alemania, proporcionaría ayuda militar y económica.
El objetivo era claro: crearle problemas a Estados Unidos en su propio territorio para que no pudiera enviar tropas a Europa. En pocas semanas, Alemania ganaría la batalla en el mar, ganaría la guerra en Europa y se podría retirar de la campaña americana. El plan fue aceptado.
Zimmermann codificó el telegrama porque era consciente de que los británicos interceptaban sus comunicaciones. Efectivamente el telegrama fue interceptado el 16 de enero de 1917 y enviado a la Sala 40, la agencia de códigos y cifras de la Marina británica. La Sala 40 era una rara mezcla de lingüistas, eruditos clásicos y aficionados a los crucigramas, todos con talento para el desciframiento. La codificación era difícil, pero el miedo a una derrota y el ingenio hicieron que en pocas horas pudieron descubrir parte del mensaje. Suficiente para comprender la gravedad del tema. Montgomery y De Gray, así se llamaban los dos analistas, le informaron al almirante Hall de lo que sabían.

Para no entrar en detalles propios de una película de espionaje el asunto terminó en pocas semanas cuando el 23 de febrero de 1917, con la guerra naval ya iniciada por Alemania, al embajador norteamericano en Inglaterra le entregan el contenido del telegrama. En rueda de prensa Zimmermann afirma “No puedo negarlo. Es verdad” No quedaban dudas.
El presidente Wilson que a principios de año había dicho que sería “un crimen contra la civilización” llevar a la nación a la guerra, el 2 de abril había cambiado de opinión. Los historiadores dicen que Estados Unidos hubiese sido empujado a la guerra de todas maneras pero que también hubiese sido tarde si se demoraba más esa decisión. El desciframiento del telegrama Zimmermann, para estos historiadores, cambio el curso de la historia.

La Enigma
            En los años siguientes, la Sala 40 continuó vigilando las comunicaciones alemanas sin mayores inconvenientes para descifrar sus códigos. En 1926 comenzaron a interceptar mensajes que los desconcertaron. Había llegado la Enigma. Rápidamente abandonaron todo intento de descifrarla. Tampoco los franceses y los norteamericanos le pusieron mucha energía al tema. Alemania tenía ahora, las comunicaciones más seguras del mundo.     
Una descripción de la máquina Enigma se puede encontrar en la red y en varios libros. Para los fines de esta columna, baste decir que Enigma era una especie de máquina de escribir con una serie de ingeniosos componentes: un teclado donde el operador escribía el mensaje, 3 modificadores circulares con cableados. Cada modificador sustituía cada letra tecleada por otra. Pero cada vez que se accionaba el teclado los modificadores giraban cambiando de esa manera la sustitución de letras que se hacia. La máquina tenía otros rasgos que aumentaban su seguridad, llevando la cantidad de posibilidades de codificación a más de 10 billones. Parecía inexpugnable.
            ¿Cómo operaba? Antes de mandar su mensaje el operador debía colocar los modificadores en una posición particular. La posición inicial de los modificadores determinaba cómo se codificaba el mensaje. Esa era la clave. Para descifrar el mensaje, el receptor necesitaba tener otra máquina Enigma y una copia del libro de códigos que contenía la posición inicial de los modificadores para ese día. El enemigo necesitaba no solo tener una máquina Enigma sino también el libro de códigos de cada día.  
A diferencia de Gran Bretaña, Francia y los Estados Unidos que estaban confiados, había una nación que no podía relajarse: Polonia. Amenazada por Alemania que quería recuperar los territorios perdidos en la primera guerra, decidieron crear una oficina de códigos. Consiguieron de los franceses una máquina Enigma e invitaron a 20 matemáticos de la Universidad de Pozman, la más importante del país. Tres de ellos, demostraron aptitud para resolver cifras y fueron empleados en la oficina. El más talentoso de ellos se llamaba Marian Rejewski. Su trabajo se centró en el hecho de que la repetición es el enemigo de la seguridad en la distribución de códigos. El análisis de miles de mensajes le permitió tener una profunda inspiración y reducir los 10 billones de codificaciones posibles a poco más de 100 mil. Eran muchas, pero para Polonia era cuestión de vida o muerte. Toda la oficina se puso a trabajar sobre esas 100 mil posibilidades y descifraron la Enigma. Las comunicaciones alemanas se volvieron transparentes.

Hasta 1938 la habilidad de Rejewski permitía descifrar cualquier mensaje. Lo que no sabía él era que la inteligencia polaca había podido acceder sistemáticamente a los libros de códigos y que no hubiera sido necesario tanto trabajo. ¿Por qué le hicieron eso? Querían que aprendiera para cuando esta posibilidad no se tuviera. Por desgracia para Polonia, concurrieron dos hechos en 1938 que la dejaron sin posibilidad de seguir descifrando los mensajes de los nazis. Perdieron contacto con su espía en Alemania y le agregaron a la máquina Enigma dos modificadores más, aumentando a muchos miles más la cantidad de posibilidades. La nueva invulnerabilidad de la Enigma fue un golpe devastador para Polonia. El 1 de septiembre de 1939 con la estrategia de “guerra relámpago” Hitler invadió Polonia y éstos no pudieron hacer mucho. Pero previendo esto, dos meses antes el jefe de la inteligencia polaca entregó a británicos y franceses los avances de Rejewski. Si ellos no podían beneficiarse que lo hicieran otros, dijo. Y así fue.  
            Los avances polacos habían demostrado el valor de emplear a  matemáticos como descifradores. La Sala 40 fue sustituida por la Escuela Gubernamental de Códigos y Cifras que se instaló en Bletchley Park. Desde allí estudiaron los avances polacos y cada día, durante el otoño de 1939, con sus métodos trataban de descifrar los mensajes alemanes. Cuando podían descubrir la disposición de los modificadores de la Enigma de ese día, el personal podía empezar a descifrar los mensajes alemanes que habían acumulado en el día. A veces tenían éxito, pero muchas veces no. Si Bletcheley conseguía descifrar la Enigma las comunicaciones alemanas se volverían transparentes y la guerra tomaría otro giro. Los británicos empezaron a darle una importancia máxima al trabajo de los matemáticos allí concentrados. El 4 de septiembre de 1939 se incorpora al equipo un personaje que sería crucial en esta historia: Alan Turing. Profesor de Cambridge, era famoso por haber diseñado en forma teórica los rudimentos de una computadora programable. Un lógico. Un matemático puro.
            Turing, al igual que Reweski, se basó en el principio de que la repetición era el punto débil de la Enigma. En lugar de estudiar los mensajes del día, se puso a estudiar los mensajes viejos ya descifrados. A comienzos del 1940, había demostrado ser un genio. Consiguió diseñar una máquina a las que llamaron bombas de Turing que podía ser capaz de atacar a la Enigma con éxito. Pero los primeros resultados no fueron satisfactorios. Necesitaba muchas bombas de Turing para tener alguna esperanza de éxito y más personal para poder trabajar a la velocidad que la guerra imponía. El 21 de octubre de 1941, Turing y otros se insubordinaron y decidieron escribirle directamente a Winston Churchill, pidiéndole más recursos. La respuesta fue inmediata. “que tengan todo lo que quieran, con extrema prioridad e infórmeme de que así se ha hecho”, escribió Churchill.
            Con el sistema de bombas de Turing y con increíbles tareas de espionaje para obtener algunos libros de códigos, la Enigma podía ser descifrada. Era vital que los nazis no sospecharan de esto, para lo cual me imagino que Churchill y los que tomaban las decisiones aliadas deben haber pasado por encrucijadas terribles. Sabiendo que tal objetivo propio iba a ser atacado, evaluar si era conveniente advertirle o no para que los alemanes no sospecharan. La matemática es fácil, lo difícil es la vida…
          
  Algunos historiadores, afirman que los logros de Bletcheley Park fueron el factor decisivo de la victoria aliada. Sus proezas se mantuvieron en secreto hasta los años setenta. La Escuela de Códigos fue desmantelada y sus miembros dispersados. Alan Turing no vivió lo suficiente para recibir ningún reconocimiento público. Lejos de ser aclamado como un héroe, fue perseguido por su homosexualidad. En 1952, en oportunidad de denunciar un robo, declaró ingenuamente que vivía con su pareja y fue detenido, juzgado y humillado públicamente, obligado a hacer un tratamiento con hormonas. En 1954 con 52 años, uno de los genios del criptoanálisis, atormentado por una profunda depresión se suicidó. 


Internet
Los hombres y mujeres de Bletchley Park no solo descifraron la Enigma sino otra cifra llamada Lorenz mucho más potente, que usaba Hitler para comunicarse con sus generales. Para ello desarrollaron el Colossus que marcó de alguna manera la criptografía durante la segunda mitad del siglo XX signada por el uso de computadoras donde la capacidad de complejizar un código y la velocidad para procesarla generaban nuevos desafíos.
En los años sesenta, el Departamento de Defensa de los Estados Unidos comenzó a financiar un proyecto de investigación llamado ARPA. Era el germen de lo que en 1969 sería ARPAnet, manejado solo por el Pentágono y algunos grupos de investigación. De allí, en 1982, nació Internet.
La distribución de claves se convirtió pues, en el problema más acuciante para los criptógrafos. Si dos partes querían comunicarse en forma segura, necesitaban de una tercera para distribuir la clave. Los costos crecientes que esto implicaba ponían a las empresas y a los estados en un dilema que parecía no tener solución. El problema fue resuelto por dos norteamericanos que cruzaron sus vidas en forma curiosa. En 1974 Whitfield Diffie, un criptógrafo independiente, fue invitado a un laboratorio de IBM en Nueva York a dar una charla. De un auditorio escéptico lo único que obtuvo fue datos sobre la existencia de un criptógrafo en California que estudiaba el mismo problema: Martin Hellman. Esa misma tarde Diffie recorrió en su auto los 5 mil kilómetros que lo separaban de la costa oeste para encontrarse con el hombre que compartía su obsesión. Hellman, que nunca había oído hablar de Diffie, le concedió un encuentro de mala gana esa misma tarde. Dos años después, en la primavera de 1976, ambos dieron con una estrategia para resolver el problema de la distribución de claves, usando la llamada aritmética modular.
Un año después tres matemáticos, Rivest, Shamir y Adleman diseñaron el sistema RSA (sus iniciales) que hoy sigue en uso.
La idea feliz de Diffie y Hellman que pretendo contarles por radio es la siguiente:
            Quiero mandarle un mensaje secreto a Natalia que está del otro del vidrio en la radio, pero Analía que la tengo al lado lo puede interceptar y espiar. Para que no lo vea, lo coloco en una caja y le pongo un candado del que solo yo tengo llave (mi clave). La caja pasa a manos de Natalia y aunque Analía la intercepte, no podrá ver su contenido porque no tiene la llave de mi candado. El problema es que Natalia tampoco tiene llave y no puede abrir la caja. Lo que hace ella, sin abrir la caja porque no puede, es ponerle su propio candado y cerrarlo con su llave que solo ella tiene (la clave de Natalia). Ahora la caja tiene dos candados y Natalia me la envía de nuevo a mí. Si Analía interceptara la caja estaría peor que antes: tiene dos candados y ninguna llave para abrirlo. ¿Qué hago yo con la caja otra vez en mi poder? Simplemente acciono mi llave y saco mi candado. La caja queda pues con un solo candado cuya llave solo tiene Natalia del otro lado del vidrio. Cuando le envíe a Natalia la caja, Analía seguirá impedida de poder ver su contenido porque ahora tiene un candado. Cuando la recibe Natalia, acciona su llave, abre la caja y saca finalmente el mensaje secreto que yo le envié. Esto, básicamente, ocurre con Internet con un mensaje de texto o con las redes sociales, para que solo el receptor pueda ver el mensaje. Esto es lo que los matemáticos llamamos una idea feliz. Simple y brillante. Lo primero que nos sale decir es ¿cómo no se me ocurrió a mi si es tan sencilla? Pues bien, se le ocurrió a ellos. Claro que solo con la idea no alcanzaba y había que fabricar esos candados y esas llaves. Allí la matemática juega un papel crucial. Hay operaciones que son fáciles hacer y difíciles de deshacer. Por ejemplo multiplicar 131 por 171 es una tarea que cualquier calculadora hace en décimas de segundo. Pero responder a la pregunta, el producto de qué dos números es 22401 es bastante más difícil. Si en lugar de ello ponemos un número de 100 mil cifras no hay computadora actual ni algoritmo que tarde menos de un par de años en resolverlo.

El desafío
Tenemos 7 cartas boca abajo. Nos dicen que entre ellas hay exactamente dos reyes pero no sabemos cuáles son. Nos proponen la siguiente apuesta: elegir dos cartas. Si ninguna es un rey ganamos. Pero si alguna de las dos es un rey perdemos la apuesta.
¿Es justa la apuesta? O dicho de otra manera: ¿tenemos mayor probabilidad de ganar o de perder?

El desafío está relacionado con la distribución de probabilidad hipergeométrica aunque no hace falta saberla para poder resolverlo. Esta distribución tiene aplicaciones en muchos campos tales como el control de calidad, en la toma de decisiones para la aceptación de lotes, etc. 

CRECIMIENTO EXPONENCIAL

Julio de 2013

Un desafío a la intuición 

¿Qué tienen que ver el Ajedrez, las finanzas y los terremotos con doblar una hoja de  papel?
Trataremos de establecer una relación entre estas cuestiones aparentemente distantes entre sí.
La comprensión de ciertos procesos nos ayuda a pensar y a entender algunos comportamientos generales. Muchas veces la matemática nos brinda una herramienta eficaz para esta comprensión y nos ayuda a desarrollar un sano espíritu crítico.
Es común escuchar que tal o cual cosa (en general una desgracia) crece en forman exponencial: “el precio del pan crece exponencialmente”, “tal epidemia está creciendo a escala exponencial”, “la deuda externa crecía en forma exponencial”, “tal candidato está creciendo en las preferencias electorales en forma exponencial”… Bueno, a veces exageran…La cuestión es saber cuándo.
El crecimiento exponencial aparece en varios modelos matemáticos para estudiar cuestiones tan variadas como,
ü      Crecimiento poblacional.
ü      Propagación de enfermedades.
ü      Intereses de una deuda.
ü      Energía atómica.
ü      Datación de restos fósiles.
ü      Autenticidad de obras de arte.
entre muchas otras.
Pero el objetivo de esta columna no es extenderme en las aplicaciones del crecimiento exponencial, sino en que el oyente se haga una idea de qué se quiere decir cuando se dice que algo crece exponencialmente y juzgar así si están exagerando o se habla con propiedad.
Para ello voy a empezar con un experimento que será imaginario para que todos lo podamos hacer, ya sea que estemos en la cama, en el colectivo o estudiando para un final.
Tomemos una hoja rectangular de papel. No importa el tamaño: puede ser una de carpeta, una del diario o de una publicidad que nos hayan dado. Imaginemos que es una A4 para fijar ideas. Podemos decir que el grosor de la hoja es de una décima de milímetro. En ese grosor vamos a poner la atención. Hasta aquí no hicimos nada. Ahora doblamos la hoja por la mitad. El grosor por lo tanto se duplica: dos décimas de milímetro. Volvemos a doblar la hoja. El grosor se vuelve a duplicar. Es decir mide 4 décima de milímetro. Una vez más y otra y otra… ¿Se hace difícil, no? Dije que era imaginario. Supongamos que pudiéramos doblar la hoja 50 veces (no lo intenten porque es imposible). En cada doblez, el grosor se duplica. Crece exponencialmente (un matemático agregaría en base 2 por eso de que se duplica cada vez). Después de 50 dobleces… ¿cuál es el grosor? Usemos la intuición. Les doy algunas opciones para que no tengan que hacer la cuenta. Es grueso como
·        Un libro gordo. Un guía de teléfonos por ejemplo.
·        La altura de Analía que mide 1,60 metros
·        La altura de este estudio de radio, que tendrá unos 3 metros.
·        La altura del obelisco (67 metros)
·        La distancia de la Tierra a la Luna.
·        La distancia de la Tierra al Sol.
Si se hace la cuenta (y el oyente la puede hacer para convencerse si lo desea, hay que hacer 2^50 (2 elevado a la 50) por 0,1 milímetros) obtenemos un resultado que sorprende al más entrenado en estos cálculos: La cuenta de un poco más de 100 millones de kilómetros. La distancia de la Tierra a la Luna es de unos 400 mil kilómetros. La de la Tierra al Sol es de aproximadamente 150 millones de kilómetros. Es decir que con un doblez, más, volvemos a duplicar, superamos con creces esa distancia de la Tierra al Sol.
Este experimento nos ilumina sobre que el crecimiento exponencial es enorme y difícil de dimensionar intuitivamente.
Esto de no poder dimensionar bien es lo que le pasó a un legendario rey de la India ante el inventor del juego del ajedrez. En su caso no supo dimensionar el alcance de sus promesas. La historia, en forma resumida, es la siguiente:
 Cuenta la leyenda que hace mucho tiempo, tanto que la historia no da cuenta de ello, el rey Iadava era señor de la provincia de Taligana en la India y fue uno de los más sabios y generosos que haya existido. La guerra golpeó en sus fronteras cuando un brutal invasor intentó invadir su territorio. El rey Iadava poseía un talento militar no frecuente y con un pequeño ejército elaboró un plan de batalla tan hábil y tan bien ejecutado que logró vencer al invasor. Sin embargo, entre los jóvenes caídos en el campo de batalla se encontraba su hijo y gran visir, el príncipe Adjamir que había defendido con patriotismo, en lo más encendido del combate, la posición  que le había dado la victoria a su padre.
El rey Iadava prohibió toda celebración y fue invadido por una gran amargura y tristeza que comenzaron a repercutir en la buena gestión del reino, ya que cada vez con menos frecuencia se ocupada de los asuntos de su pueblo. El rey reconstruía en su mente y en un pizarrón improvisado en la arena, una y otra vez las peripecias y circunstancias en las que Adjamir había muerto, preguntándose si podría haberlo evitado.
Venido desde los confines del reino, un joven brahmán le solicitó una mañana audiencia al rey. No era la primera vez que lo intentaba pero el rey se negaba siempre a recibirlo. Pero esta vez accedió al pedido del brahmán. Sessa, que así se llamaba el joven, le traía de regalo un juego que había inventado con el objeto de distraer y entretener al monarca y mitigar así su tristeza y amargura. El rey Iadava era muy curioso de modo que no pudo contener el deseo de aprender este nuevo juego que no era otro que el juego del ajedrez.
Sessa explicó al rey y a sus cortesanos en qué consistía el juego y las reglas esenciales para poder jugarlo. Las piezas pequeñas, los peones, representan la infantería que avanza hacia el enemigo. Secundan a éstos, los elefantes de guerra (las torres), la caballería que pueden saltar por encima de otras piezas y los dos visires del rey (los alfiles) que son dos guerreros llenos de nobleza y de prestigio. El rey quiso saber por qué la reina estaba dotada de amplios movimientos y era más poderosa y más eficiente que las otras piezas, incluido el rey.  Le explicó Sessa que la reina representaba el espíritu del pueblo y que es allí donde reside la fuerza del trono. La pieza que representa al rey es débil si se encuentra aislada pero es muy poderosa si está amparada por las demás piezas del juego.
Al cabo de pocas horas, el rey era un experto jugador de ajedrez y lograba vencer a sus ministros y colaboradores. En un momento dado, en pleno juego, el rey observó con gran sorpresa que la posición de las piezas parecía reproducir la batalla final en la que su hijo había caído. El inteligente brahmán le hizo observar que, para ganar esa partida, era indispensable sacrificar al alfil (al gran visir) y que ello, a veces, es lo que debe ocurrir fatalmente, para asegurar la paz y felicidad del pueblo. 
El rey Iadava comprendió la lección y dijo que no creía que el ingenio humano pudiera producir otro juego tan interesante e instructivo como el ajedrez. En recompensa, le dijo a Sessa, que pidiera lo que deseara, dentro de lo que él podía darle, ya que le sería concedido. Sessa agradeció la generosidad del rey pero dijo que le alcanzaba con la satisfacción que le daba saber que el ajedrez aliviaría las horas de tristeza y melancolía que al rey solían perturbar. Dijo el rey sorprendido, que la modestia, cuando es excesiva, no es virtud. Entonces, Sessa quiso darle al rey Iadava una última lección. No deseo, poderoso rey, ni oro, ni tierras, ni palacios. Deseo mi recompensa en granos de trigo. Poniendo el tablero de ajedrez en el medio del recinto, dijo: me darás un grano de trigo para la primera casilla del tablero, dos para la segunda, cuatro para la tercera, ocho para la cuarta y así,  duplicando la cantidad de granos hasta llegar a la última de las 64 casillas del tablero. Todos los miembros de la corte se rieron junto con el rey por lo exiguo del pedido de Sessa. Eres un insensato dijo el rey por pedir recompensa tan ridícula. Mandó el rey a calcular la cantidad de granos que debía darle a Sessa en recompensa. Al cabo de unas horas vinieron los contadores y algebristas de la corte con caras de preocupación.
Rey Iadava, calculamos el número de granos de trigo y obtuvimos un número inconcebible para la imaginación humana. Sembrados todos los campos de la India, no darían ni en 2 mil siglos la cantidad de trigo requerida. El número de granos es
18. 446.744.073.709.551.615 granos
Esta cantidad de granos es enorme. Equivale a 9 billones de toneladas de trigo. Se acabaría el problema del precio del pan por muchos siglos…
Concluyó Sessa que desagraciado es el gobernante que no es capaz de dimensionar el alcance de sus promesas. Le daba así al rey Iadava una última lección de humildad.

Esta historia la leí por primera vez en el hermoso libro El Hombre que calculaba de un escritor brasileño que firma con el seudónimo Malba Tahan.




Un experimento y una leyenda me han servido para explicar qué es el crecimiento exponencial. Pero no quiero dejar afuera la vida real. Quiero contarles brevemente la relación que hay entre la exponencial y los terremotos. ¿Cómo hacen los expertos en sismos para medir su intensidad?
La forma más extendida a nivel de los medios es la escala de Richter, creada por este geólogo y un colega en 1935. Es una escala arbitraria que asigna un número para cuantificar la energía liberada por un terremoto y fue diseñada en función del tipo de sismómetro usado por aquel entonces. Por las limitaciones tecnológicas de ese sismómetro, la escala de Richter no permite medir correctamente temblores que superen los 6,8. Por ello, en 1975, se ha modificado esta escala por otra llamada de momento sísmico y que tiene la gran ventaja que coincide con la escala de Richter cuando la magnitud está por debajo de 6,8 y puede medir magnitudes mayores. De modo que cuando en los medios de comunicación escuchamos que un terremoto ha sido de magnitud 7 u 8 en la escala de Richter no es correcto. Se está usando la escala de momento sísmico.
La relación que tienen estas escalas con la exponencial es que en sus fórmulas aparece un logaritmo (Analía acaba de poner cara de que nos estamos quedando sin oyentes al usar esa palabra…)  Trataré de explicar brevemente esta palabra terrible. Aunque no se pueda creer, los logaritmos fueron creados para facilitar las cuentas por John Napier (Neper) alrededor del 1600. El logaritmo convierte productos en sumas y divisiones en restas y cuando no existían las calculadoras estas cuentas eran muy penosas cuando había que efectuarlas sistemáticamente. El astrónomo Kepler, contemporáneo de Neper, hizo un buen uso de ellos. Luego, con la revolución industrial y hasta el advenimiento de las computadoras, los logaritmos jugaron un rol esencial en los cálculos. Hoy cumplen otras funciones importantes en la ciencia como esta que les cuento. El logaritmo, es la operación inversa de la exponencial. Es decir, al crecimiento descomunal de la exponencial ilustrado en el cuento del ajedrez, se contrapone un crecimiento lentísimo del logaritmo.
El logaritmo de un número, dicho rápidamente, cuenta la cantidad de ceros del número. Por ejemplo, el logaritmo de 100 es 2 porque 100 tiene dos ceros, el logaritmo de 1000 es 3. El logaritmo de 500 estará pues entre 2 y 3. El logaritmo de 1 millón es 6. Observemos que para pasar de 3 a 6 con el logaritmo tuvimos que pasar de 1000 a 1 millón. Allí se ve lo del crecimiento lento.
           
Volvamos a la escala de Richter o la de momento sísmico. El logaritmo incorporado a estas escalas hace que los valores asignados a cada nivel aumenten a escala logarítmica. 
Por ejemplo, si la energía liberada por un terremoto la asimilamos con la cantidad de TNT (parecida a la dinamita) tenemos las siguientes equivalencias:
Escala Richter              TNT                    Referencia
1,0                              170 g                     Pequeña explosión en un sitio en construcción.
2,0                              910 g                     Bomba convencional. Segunda guerra.
            3,0                              181 kg                   Planta de gas
            4,0                              6 ton                      Bomba atómica
            5,0                              200 ton                       
            6,0                              1270 ton                Terremoto de Oxaca 2012 (México)
            7,0                              200 mil ton             Terremoto de Pto Príncipe 2010 – Haití
            8,0                              10 mill ton              Terremoto de Pisco 2007 – Perú
            9,0                              240 mill ton            Japón 2011
           

El Desafío de hoy
Le voy a proponer a Analía un negocio y los oyentes tendrán que decirnos si mi propuesta es una ingenuidad de mi parte o bien, es una estafa.
La propuesta es la siguiente: nos intercambiamos nuestras cbu bancarias y desde el lunes yo le depositaré cada día, durante 20 días hábiles, 100 mil pesos cada día.  Hasta aquí parece muy atractivo para Analía aceptar el negocio. A cambio, Analía, depositará en mi cuenta el primer día, 2 pesos, el segundo día, 4 pesos, el tercer día, 8 pesos y así hasta el día 20, duplicando cada vez el depósito con respecto al día hábil anterior.
El desafío pues, es saber quién de los dos, hará un buen negocio con esta propuesta que le hago a Analía y que estamos ya firmando ante escribano.


Hasta la próxima.