Por @Alvy — 12 de Septiembre de 2022

Este curioso vídeo de Polylog es un curioso crossover entre dos de mis temas favoritos: el cubo de Rubik y la criptografía. Explica cómo utilizar la técnica Meet-in-the-Middle («Encontrarse a medio camino») para resolver un cubo de Rubik. Esta técnica se emplea para atacar algunos algoritmos criptográficos, y no es precisamente la ideal para resolver el cubo. Pero sirve para hacerse una idea de cómo funciona este tipo de ataques convirtiendo un ataque imposible por fuerza bruta en otros dos más pequeños que sí son factibles. El vídeo está además estupendamente ilustrado con muy buenas animaciones.

La cuestión es que enseña a ver los movimientos del Cubo como un grafo, algo que puede suceder en otras situaciones, en el que unas posiciones (vértices) llevan a otras con cada giro, en un grafo que podría ser equivalente al de una red social o al de la teoría de los seis grados de separación. Encontrar la solución sería ir de la posición A (mezclado) a la B (resuelto) recorriendo el camino óptimo que tenga menos pasos. Y eso muchas veces puede hacerse, aunque depende de la complejidad y el número de vértices y caminos.

Contamos con una ventaja: para el Cubo de Rubik tradicional de 3×3×3 sabemos que 20 es el número máximo de movimientos necesario para resolverlo de forma óptima. Ojo a los matices, que mucha gente se lía: es el número máximo para resolverlo de forma óptima, que no el mínimo –que pueden ser muchos menos si el cubo está casi resuelto– ni el máximo absoluto –que puede ser infinito si te pones a hacer el tonto girando siempre la misma cara–. El número total de posiciones distintas de un cubo se sabe desde la antigüedad que es 43.252.003.274.489.856.000 (unas 1020).

El problema es que usar la fuerza bruta para llegar a todas las posiciones no sirve porque 1020 es un número un poco inabarcable; que esto es un juguete, no un satélite espía enemigo en el que invertir millones y millones. Pero curiosamente la forma de abordarlo con la técnica Meet-in-the-Middle permite explorar todas las posiciones a las que se pueden llegar con 10 movimientos desde el cubo mezclado (unas 1010) y al mismo tiempo las 1010 posiciones a las que se pueden llegar desde el cubo resuelto. Como está demostrado que el máximo necesario son 20 movimientos, eso quiere decir que si se solapan esos grafos alguna de esas posiciones (que ocupan unos 80 GB, así que se necesita mucha RAM) coincidirá. Se toma un camino del primera grafo, otro del segundo y esa será el camino ideal a la solución. Problema resuelto. Nota: esto solo funciona si el número de posiciones crece de forma suficientemente exponencial.

Incidentalmente, resulta que así es como se atacan criptográficamente sistemas de cifrado como el DES (con una clave única de 56 bits), calculando los dos grupos de 228 bits (algo más abarcable) y solapándolos. Por esta razón se quedó obsoleto y se inventó el Triple DES que usa 168 bits (3×56).

Ya lo hemos dicho antes: este algoritmo Meet-in-the-Middle no es óptimo por poco práctico –muchas veces la fuerza bruta no lo es– pero enseña algunas cosas interesantes. El código puede verse en Github (Rubik MITM Solution) donde se cita a Cube Explorer como sitio en el que encontrar algoritmos mucho más rápidos basados en otras ideas.

En God’s Number is 20 puede leerse algo más sobre cómo se resolvió el problema del número máximo de movimientos y en un vídeo de J Perm se explica lo del conteo de las 4,3 ×1019 posiciones distintas de un cubo 3×3×3.

Relacionado:

Compartir en Flipboard Tuitear

PUBLICIDAD



Por @Alvy — 10 de Septiembre de 2022

Matemápolis / Lola Morales / https://dibumatica.gumroad.com/l/kgoxo

Matemápolis es una ilustración de Lola Morales profesora de matemáticas e ilustradora, que reúne en un póster tamaño A2 ni más ni menos que 200 personas y objetos matemáticos. 200 horas de trabajo por auténtico «amor al arte» que se pueden comprar como PDF en Gumroad para imprimir a todo color. El precio lo decides tú (está en la modalidad paga-lo-que-quieras) y el PDF que se recibe son 77 MB; también hay versiones en TIFF y JPEG.

A simple vista, así desde lejos, se ve una banda de Möbius, una pirámide de Sierpinksi, la escalera imposible de Penrose y un Cubo de Rubik. Fijándose bien –porque la ciudad es grande y está llena de gente y edificios– se pueden ver un cono y sus cónicas, una estructura que es una esponja de Menger o un cuadrado mágico a modo de graffiti. Acercándose algo más se distingue una niña jugando sobre la legendaria vaca esférica, la fórmula más bella del mundo o al rey indio jugando al ajedrez, una de las explicaciones más entretenidas sobre el crecimiento exponencial.

Vaca Esférica / Matemápolis / Lola Morales / https://dibumatica.gumroad.com/l/kgoxoLa lista de personajes matemáticos históricos tampoco es corta: desde Euler a Gauss o Ada Lovelace, Maldelbrot, Emily Noether o Fermat. Están los clásicos como Diofanto de Alejandría, Eratóstenes e Hipatia, que comparten cartel con matemáticos actuales como Eduardo Sáenz de Cabezón, Clara Grima o Pablo Beltrán-Pellicer.

También pueden encontrarse diversos problemas, teoremas y conjeturas, algunas de forma muy sutil: desde la fascinante igualdad 0,999… = 1 al problema de Monty Hall o la paradoja de Aquiles y la tortuga. También está el Hotel de Hilbert, los monos escribiendo a máquina o las teselaciones de M.C. Escher. Si te lo planteas como juego, o como entretenimiento para una clase de matemáticas divulgativas, es un no parar.

En Behance hay otros portafolios son trabajos de la autora: Behance: Lola Morales.

Relacionado:

Compartir en Flipboard Tuitear

PUBLICIDAD



Por @Alvy — 6 de Septiembre de 2022

Marc Evastein, un programador que a la vez es pianista y compositor musical, ha estado explorando la música de los números primos, como decía el título del famoso libro. Es de ese tipo de investigaciones de las que no se espera gran cosa excepto que el resultado «suene bien» y para ello utiliza la naturaleza rítmica de los ciclos de los números primos.

La base de todo el asunto es la archiconocida criba de Eratóstenes. El matemático griego ya explicó cómo elaborar la lista de todos los números que no son divisibles de forma exacta por ningún otro, excepto por sí mismos y la unidad. Se hace comenzando por el primero y tachando los múltiplos primero de 2, luego de 3, luego de 5 (el siguiente primo), 7, 11, 13, etcétera, en ciclos de distinta longitud. Se pueden usar colores para marcar las factorizaciones (si tiene múltiplos de 2, 3, 5, 7, etcétera).

El asunto consiste en hacer la criba por cada valor en una fila distinta y luego ir recorriendo esos valores desde el principio rítmicamente. Dependiendo de qué múltiplos tengan se puede hacer sonar algo diferente (por ejemplo un golpe de batería); si son primos habrá una especie de silencio. La idea se puede extender cambiando el concepto y usando un solo instrumento pero variando las notas según los múltiplos de los números. La melodía resultante puede resultar un poco rara, porque se utilizan notas que no son las de la escala habitual (do-re-mi…) sino algunas frecuencias intermedias. Como los números primos van haciendo bajar más y más las notas –y son cada vez menos frecuentes– esto se puede apreciar con menos silencios y notas que tienden a ser más graves [en el vídeo: ~5:55] .

Si tienes buen oído también puedes escuchar las dos notas graves parejas que dejan los primos gemelos. Esos son los que están separados dos unidades, como 11 y 13 o 71 y 73.

El software que genera la música está programado en Python con las librerías SCAMP para crear música sintetizada y con las animaciones en Processing.


Relacionado:

Compartir en Flipboard Tuitear

PUBLICIDAD



Por @Alvy — 26 de Agosto de 2022

Esta curiosa película llamada Rythmetic es un trabajo de Norman McLaren y Evelyn Lambart, dos pioneros del cine de animación moderno que eligieron la aritmética y la magia de los números para transmitir algo de ritmo, humor y, por qué no, educación matemática.

Con una duración de algo más de 8 minutos lo cierto es que hoy en día se hace un tanto lenta para los estándares del siglo XXI. Pero es divertido ver a los números jugando y haciéndose bromas al ritmo de los parcos efectos sonoros. Situemos esto en contexto a mediados del siglo XX donde las películas en color eran algo todavía novedoso. Las técnicas de animación todavía estaban en pañales y utilizar conceptos abstractos como números y operaciones matemáticas sencillas estaba prácticamente fuera de lugar.

Trabajos como estos se utilizaron profusamente en programas infantiles como Barrio Sésamo, donde nos educamos muchos de los que pertenecemos a la generación X, de modo que es normal que nos resulten adorablemente familiares. Los pequeñajos de la época podían pasar horas y horas hipnotizados frente a la pequeña pantalla viendo letras, números o formas de colores moverse y comportarse como personajes. Es increíble cómo esas historias dotan de humanidad y sentimiento a las formas geométricas o, como en este caso, los números y signos matemáticos.

(Vía The Kid Should See This.)

Relacionado:

Compartir en Flipboard Tuitear

PUBLICIDAD




PUBLICIDAD


Desarrolla más rápido con Xojo