Rango Finito

fotoscódigoobservatorioshermanocerdo temas plots

problemas

Codility

Codility es una plataforma en línea para evaluar habilidades de programación. Ayer, una de las empresas a las que he enviado hojas de vida me envió allá a hacer un examen de aptitud. Todavía no me he animado a hacerlo, pero ayer mismo estuve probando la plataforma aprovechando que ofrecen algunos problemas de prueba. Son problemas típicos (y (a posteriori) sencillos) de diseño de algoritmos. Hice dos más o menos rápido. En el que quedaba me embolaté y me fui a dormir cansado y frustrado pero la ansiedad que determina el 98% de mi existencia me despertó a las cuatro de la mañana con una idea vaga de cómo escribirlo (y otros pensamientos menos agradables). Finalmente me levanté a las seis e hice el deber. Al final, después de varios intentos, logré soluciones satisfactorias a todas las preguntas. Como lenguaje elegí Python, que también está disponible como opción en la prueba que tengo que hacer. Algo bueno de Python es que me puedo desentender de problemas de desborde con números muy grandes (varios de los tests que hacían a las soluciones intentan romperlas así.) Aquí subí las soluciones sin mayor comentario. Espero que el código sea suficientemente claro.

3

Es bonito este problema de álgebra elemental: si $x$ es un número tal que $$x + \frac{1}{x} = 1,$$ calcular $$x^N + \frac{1}{x^N}$$ para algún $N$ entero grandote e intimidante (digamos $2.345.871$).

1

Los resultados de Pisa merecen atención pero también cuidado en su interpretación. Pisa, como todo examen, evalúa un contenido dado. Se parte del supuesto de que este contenido es estándar. Se asume que el diseño del examen toma en cuenta sesgos culturales. ¿Qué tanto? Es difícil de saber. Sin duda Pisa se acomoda mejor al sistema educativo de ciertos países que a otros. En últimas lo que Pisa mide es la cercanía del sistema educativo de un país al ideal que la organización propone. No creo que las personas al frente de la educación colombiana tengan claro cuál es ese ideal que Pisa promueve implícitamente con su examen. (Es discutible (o debería serlo) que ese sea un objetivo que debamos adoptar, por cierto.) Ni siquiera creo que esas personas tengan algún objetivo claro en mente. La verdad es que el sistema educativo colombiano está tan a la deriva y su existencia es tan difusa que es casi imposible tomar los resultados de Pisa como demostración de algo distinto a su abandono. La capacidad del examen para evaluar algo profundo (estilo “la capacidad de los muchachos para resolver problemas” — de paso: ¿cómo se puede esperar medir con un examen escrito la capacidad para resolver problemas cotidianos de unos muchachos que no saben leer ni escribir?) es contingente a que contemos con un sistema educativo relativamente organizado y mínimamente funcional, cosa que en Colombia, no nos mintamos, todavía no existe. En tanto que la calidad del sistema educativo dependa de la buena voluntad de héroes anónimos dispersos rodeados de un mar picado de mediocridad los resultados lamentables en las pruebas Pisa no hablarán de maestros ni de estudiantes ni de colegios sino de la ineptitud de los políticos y funcionarios y su desprecio más que evidente por el futuro del grueso de los colombianos.

Capicúas

Esta tarde escribí un cuaderno de iPython para jugar con números capicúas. La motivación fue este problema propuesto por Cédric Villani en su sección recién inaugurada de juegos matemáticos de Le Monde. (Loable el esfuerzo de Villani por promover personalmente la matemática entre la gente del común, por cierto. Y adorable su uso (francesísimo) de tablero y tiza para presentar y resolver los problemas. Cada vez me cae mejor.)

Raíces

Las raíces anidadas (o contínuas) son sucesiones de términos de la forma: $$S_k = \sqrt{a_1+\sqrt{a_2 +\sqrt{a_3 + \cdots+\sqrt{a_k}}}}.$$ Como es usual, si $S_k$ converge a $L$, entonces decimos que $$L=\sqrt{a_1+\sqrt{a_2 +\sqrt{a_3 + \cdots+\sqrt{a_n+\cdots}}}}.$$

El ejemplo típico es $a_i=1$ para todo $i$. En ese caso se obtiene la expresión $$\sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}.$$ Si sabemos que esta raíz anidada es convergente (hay varios métodos para concluir esto) y suponemos que su límite es $L$ entonces $$L=\sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}=\sqrt{1+L},$$ de donde se desprende que $L^2=1+L$ y por ende $$L=\frac{1+\sqrt{5}}{2}.$$

Cuando Ramanujan empezó a hacer matemática, enviaba preguntas a la revista de la sociedad matemática india. En 1911 propuso como problema encontrar el valor de $$\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+\cdots}}}}.$$ Esta es una raíz anidada donde (si no estoy mal) $a_1 = 1$ y $a_n=(n a_{n-1} )^2$ (para $n\geq 2$).

Un año más tarde, Ramanujan envió esta solución a la misma revista:

Primero que todo, defina $f(n)=n(n+2)$. Ahora note que $$\begin{eqnarray*} f(n) & = & n \sqrt{(n+2)^2} \\ & = & n\sqrt{n^2+4n+3+1} \\ & = &n\sqrt{1+(n+1)(n+3)} \\ &=& n\sqrt{1+f(n+1)}.\end{eqnarray*}$$ Por tanto, recursivamente, $$\begin{eqnarray*} f(n) &=& n\sqrt{1+f(n+1)}\\ &=& n\sqrt{1+(n+1)\sqrt{1+f(n+2)}} \\ &=& n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{1+f(n+3)}}} \\ &=& \cdots \\ &=& n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{1+(n+3)\sqrt{1+\cdots}}}}. \end{eqnarray*}$$

Cuando $n=1$, obtenemos $$f(1)= \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+\cdots}}}},$$ que es precisamente el valor que estamos buscando. Y sabemos que, por definición, $f(1) = 1 (1+2) = 3$.

Este es un problema difícil con una solución muy sencilla de presentar y apta para (casi) todo público. Mi duda didáctica es qué tanto se puede ofrecer como ayuda sin entregar la respuesta. O mejor: en qué punto la solución se vuelve de repente evidente (para un estudiante promedio de primer año de universidad, digamos).

Adenda: En el segundo ejercicio de esta tarea del curso de cálculo que dicté el verano pasado puse a los estudiantes a explorar la convergencia de otra de las famosas fórmulas de Ramanujan (creo que el problema proviene del libro de Spivak). El tercer apartado tomó mucho más trabajo del que pensaba. Tuve que ayudarles un poco a organizar los cálculos.

Hay otros mundos

Diez diferencias entre los terroristas blancos y los otros ¶ Cromatoforas (?) de calamar al ritmo de Cypress Hill ¶ Los cambios recientes en twitter ilustran bien el problema principal de las “redes sociales” centralizadas ¶ Un catálogo de técnicas para atrapar en imágenes estáticas (o casi estáticas) el paso del tiempo ¶ Es lindo el diario ilustrado de Gemma Correll ¶ Las vacas de Narayana se reproducen musicalmente (aquí un artículo al respecto (en alcanforado postscript) escrito por el compositor (Tom Johnson) y su amigo matemático) ¶ En tiempo de caudillos la política de ideas colapsaSiete problemas (pdf) que tal vez nunca oyó correctamente (con soluciones) ¶ Y un graficador tipográfico de flujos o algo así.

Hay otros mundos

Miguel Gualdrón resucita tras leer El Rey Pálido ¶ Laura Acosta defiende a la Tigresa de Oriente ¶ Inés Gallo recomienda Person, de Sam Pink ¶ Jorge Aranda recuerda a un amigo muerto ¶ Tatiana Luján piensa en las enfermedades de los viejos de su familia ¶ Gloria Esquivel responde un cuestionario de Sophie Calle ¶ El papá de Óscar Rodríguez descubre una partida de bautismo que lo vuelve dos años mayor ¶ Constantino Villegas confronta a los gramáticos apocalípticos ¶ Y Helen DeWitt publica un cuento titulado Recovery en Electric Literature.

Las series poderosas

Con el teorema del valor medio es sencillo demostrar que $$e^x>x+1$$ para todo $x > 0$. Pero no es inmediato. A los estudiantes sin experiencia previa les cuesta muchísimo seguir argumentos que no están encadenados por igualdades o donde sea necesario tomar elecciones y confeccionar funciones. En cambio, si se conoce la representación con series de potencias de $e^x$ el problema se disuelve por completo, pues la serie de potencias de $e^x-x-1$ resulta ser $$\sum_{n=2}^\infty \frac{x^n}{n!},$$ que es claramente positiva para $x>0$.

Otro: intente demostrar que $$\int_1^\infty \frac{e^{-x^2}}{x}\, dx$$ converge. Sin series de potencias, el camino más sencillo es una comparación con algo como $$\int_1^\infty xe^{-x^2}\, dx.$$ Con series de potencias, creo, llegar a la conclusión toma una línea de cálculos directos más una nota, si acaso, explicando por qué se puede integrar término a término la serie.

Otro más (y un clásico): evalúe $$\lim_{x\to 0} \frac{\sin x}{x}.$$

No deja de sorpenderme la cantidad de problemas de cálculo elemental con pretensión conceptual que se vuelven mecanizables hasta que parecen casi vacíos con tres series de potencias bien recordadas y un par de teoremas no muy complicados sobre la solidez (bajo manipulaciones varias) de sus respectivas convergencias.

Paciencia

La paciencia es una virtud de la cual carezco. Envidio a los pacientes. Envidio su capacidad amplificada para la minuciosidad y la disciplina. El trabajo de Mónica requiere paciencia y atención. A ella le sobran. Los procesos y experimentos de su laboratorio se desenvuelven lentamente y el fracaso es constante. La paciencia permite continuar pese a los baches, asimilarlos como avance. Las personas pacientes tienen una relación amistosa con el tiempo: no lo encaran como un oponente; es un medio que se habita. El arte que disfruto y admiro es producto de paciencia y disciplina. Aprecio las construcciones cuidadosas, el método, la creación sistemática. Quisiera poder escribir así. No encuentro mucho valor en la literatura de los escritores, digamos, viscerales, que no asumen control sobre sus historias y estructuras.

Tengo el propósito regular de volverme una persona más paciente. Primero con el tiempo y luego (más difícil) con los demás. Entre mis ejercicios está imponerme proyectos pequeños (y a veces reiterativos) que sé que me tomarán varios días y requerirán esfuerzo creciente. También procuro, no siempre lo logro, cocinar evitando el fuego alto. He notado (y cuánto me cuesta) que un cierto nivel de organización facilita la práctica de la paciencia. Cuando las herramientas no están dispuestas apropiadamente el progreso se convierte en un conjurador de distracciones y bifurcaciones que tientan mi tendencia natural a renunciar. La ansiedad y la paciencia no se llevan bien.

Búsqueda y destrucción

Un hombre recibe una misión: encontrar a una persona con un tatuaje del Pato Donald estampado en el culo. Es un problema aparentemente difícil de resolver. En general puede tomar mucho tiempo y esfuerzo encontrar a alguien así pero, en contraposición, corroborar que el hombre cumplió su misión es sencillo: basta bajarle los pantalones al candidato.

Soldados buscan
Soldados buscan cartas entre los restos carbonizados de una oficina de correo en Dublin, 1922.

Muchos problemas de búsqueda tienen la particularidad de que, aunque parezca difícil (en términos de tiempo) encontrar lo que se desea, verificar la validez de una solución es relativamente rápido. La pregunta es si de verdad son tan difíciles de resolver como aparentan ser. No es claro. De pronto siempre existe al fondo una manera rápida de buscar.

Por ejemplo, determinar si un número es primo parece un problema de este tipo. Requiere constatar la existencia (o no) de un divisor. Encontrar un divisor, al menos siguiendo la estrategia más obvia, tarda demasiado, pero verificar que es un divisor sólo requiere dividir y revisar el residuo (esta operación puede tomar tiempo, pero no demasiado en relación a la longitud de los números involucrados). Por muchos años se sospechó que el problema de decidir si un número era primo o no debería ser rápido de resolver, pero sólo hasta hace diez fue descubierto un procedimiento que lo hace de manera rápida, concluyente y sin condiciones en los números a evaluar.

Detrás del juego de dibujar esta versión de la Mona Lisa en un sólo trazo (uniendo con líneas rectas unos puntos elegidos de antemano) se oculta el famoso problema del agente viajero, otro de esos que parecen (y probablemente sean) difíciles de resolver aunque verificar una solución sea sencillo.

Otros problemas no han tenido la misma suerte pero tampoco han tenido la suerte opuesta: no se ha podido demostrar que no existe una solución rápida. En otras palabras, no se sabe si existen problemas de búsqueda con verificación de solución rápida que sean esencialmente difíciles. A los problemas con verificación de solución rápida los llaman NP. A los problemas con solución rápida los llaman P. Otra manera de plantear la pregunta es sí todo problema NP es en realidad P o si definitivamente existen problemas NP que no son P.

Muchos algoritmos de encriptación de uso diario basan su solidez en problemas de búsqueda con verificación rápida de solución que por lo pronto parecen ser esencialmente difíciles de resolver, como la factorización de números enteros (en el caso del algoritmo RSA). Si se demostrara que todo problema NP es P, la seguridad de estos sistemas se derrumbaría (y probablemente con ella la civilización como la conocemos). La conjetura más popular, por ende, es que P≠NP. Ese es el verdadero sacramento de nuestra fe.

La ilusión de que NP no sea lo mismo que P nos protege.

Escalafón

Problema (muy probablemente con nombre, apellido y soluciones conocidas y optimizadas): dada una base de datos (suficientemente extensa) de jugadores de un cierto juego (imaginen Tetris) que recopila su historial ordenado de puntajes, cómo decidir, a partir de la información en la base de datos y sin tomar en cuenta las particularidades del juego, quién es el mejor jugador. Una solución burda es simplemente elegir a aquel que obtuvo el puntaje más alto. Otra es elegir a quien tiene el promedio más alto. Estas soluciones no son satisfactorias: un jugador puede obtener un puntaje elevado por simple suerte pero ser regular en general y otro puede tener un promedio superior que otro sólo porque ha jugado un juego mientras el otro ha jugado cien. Tal vez, antes de proponer una solución, debería aclararse cuáles serían las condiciones de una solución satisfactoria. Una posible condición es que la solución diferencie a los jugadores tanto como sea posible, i.e., si el historial del jugador A y el historial del jugador B son distintos, (casi) siempre debería ser capaz de decidir si A o B es mejor. En el fondo, obviamente, la pregunta es cómo definir ser mejor dada la información disponible. Recibo ideas, sugerencias, referencias, extensiones, críticas, dudas, increpaciones gratuitas y demás en los comentarios. Es para un amigo.

Miércoles

Atendí estudiantes de once a seis casi sin descanso. No vinieron muchos, pero cada visita duraba entre una hora y una hora y media, aunque se solapaban unos con otros. Un noventa por ciento de las preguntas son debidas a inseguridades o exceso de autoconfianza y casi ninguna a verdadera incomprensión. Cuando no hay suficiente práctica, es difícil medir la dificultad de los problemas y es frecuente que los estudiantes los consideren imposiblemente difíciles (y entonces no sepan qué hacer o les parezcan por fuera de su alcance) o increíblemente idiotas (en cuyo caso se preguntan por qué diablos eso es un problema y, peor, por qué su respuesta obvia y directa por simple sentido común no coincide con la respuesta del libro o con la, en comparación, complicadísima respuesta de un amigo). Parte de mi labor, he descubierto, consiste en guiarlos dentro de los problemas mucho más que a través de ellos y por otro lado convencerlos de que cuentan con muchísimas más herramientas para valorarlos y enfrentarlos que las que creen que tienen. Se siente, por momentos, como despertar un poder sobrenatural dormido del que no tienen conciencia. Ahora estoy en el tren y miro a una mujer frente a mí maquillarse compulsivamente por al menos treinta minutos. Su amiga la ayuda a sostener el espejo para las operaciones más delicadas, alrededor de los ojos. Aún no veo diferencia entre el antes y el después. Tal vez todavía no hemos llegado al después.

Viernes

Penúltima clase. Pocas preguntas. Pocas respuestas. Leo varias reseñas al respecto de The Pale King. Pienso que tal vez debería postergar su lectura un rato, unos años, incluso, y decantarme por algún clásico reciente estilo The Recognitions para el verano (Andrés me sugiere el no tan reciente La Montaña Mágica). Le confío a mis estudiantes un secreto, algo sencillo pero importante que he aprendido con los años. Les digo: ¿recuerdan que en las películas los genios matemáticos miran el tablero y en el acto los números y símbolos se iluminan, giran, vuelan, se combinan y se reorganizan hasta que mágicamente aparece en el centro una respuesta? Pues eso no funciona. Les explico que garabatear fórmulas ordenadamente en un papel es un método mucho más eficiente para solucionar este tipo de problemas (si no todos los problemas). Igual ellos miran la integral inexpugnable en el tablero a la espera de una respuesta. Conozco esa mirada. Encarna una especie de fe juvenil en el poder y alcance de su propia inteligencia así como el desprecio a todo lo que implique esfuerzo. No los culpo, estoy seguro de que alguna vez yo también intenté resolver problemas a punta de miradas, desde la distancia, sin hacer nada. Como tantos otros adolescentes, estaba convencido no sólo de que podía mover cosas con la mente sino que buena parte de la realidad exterior era responsabilidad directa de mi mente, presta a ser alterada/perturbada/redefinida en respuesta a mi todopoderosa (y voluble) voluntad. No recuerdo cuándo aprendí que el mundo no funcionaba así. No fue hace mucho, probablemente.