Hace mil años, los músicos indios idearon un método para memorizar patrones rítmicos. Hoy sabemos que el mismo principio sirve para decodificar mensajes en binario y recomponer textos electrónicos. ¡Un viaje que nadie esperaba!
Este vídeo se incluye en el proyecto TelecoRenta, un plan a nivel nacional para la promoción de los estudios de telecomunicaciones. En el futuro habrá más vídeos, sobre criptografía y series de Fourier, que creo que estarán de toma pan y moja.
Sobre las secuencias de De Bruijn
Aunque el vídeo solo comenta las secuencias en binario (aquellas que usan los dígitos \{0,1\}), ¡el concepto es válido para cualquier conjunto de cifras! Podemos preguntarnos por una secuencia que contenga todos los quintetos formados por los números \{0,1,2,3\}, y la solución se puede encontrar con el mismo método de la ciudad imaginaria. He repasado las ideas principales en un artículo independiente, con algunas animaciones adicionales.
Sobre el problema de Königsberg
Hay muchas versiones del problema de Königsberg, y no todas coinciden. Algunos consideran que el problema original se pregunta si existe una ruta circular que recorra todos los puntes. Otros se preguntan si existe una ruta, a secas, ya sea lineal o circular. Sin ir más lejos, la Wikipedia inglesa y la española presentan versiones distintas del problema.
El artículo original de Euler (referencias [5] y [7]) no pregunta por una ruta circular, sino por una ruta cualquiera. Supongo que cuando el mundo académico creó el concepto de grafo euleriano (aquel en el que existe una ruta circular) modificó la manera de explicar el origen del problema. Digo yo, vamos.
En cualquier caso, la demostración que da Euler, y la que presento yo en el vídeo, es una demostración incompleta. Según el argumento de Euler, para que exista una ruta circular es necesario que cada punto del grafo tenga un número par de puentes. Pero eso, teóricamente, no garantiza la existencia de la ruta. Solo te dice que, si existe, el grafo debe tener un número par de conexiones en todos los puntos. Pero no te asegura que exista.
Eso sí: Euler concluyó que la ruta existía siempre, aunque no diera la demostración. Hubo que esperar hasta 1873 para que Carl Hierholzer diera un argumento completo.
Sobre el acertijo de la ciudad
Una ciudad siempre tiene un número par de «zonas con puentes impares». O sea: o no tiene zonas impares, o tiene dos, o tiene cuatro, o tiene un número par. Es fácil demostrar por qué, pero eso te lo dejo como reto.
En consecuencia, las ciudades formadas por dos o tres zonas siempre tienen una ruta que cruza todos los puentes sin repeticiones, porque estas ciudades siempre admiten una ruta abierta o cerrada (como mucho tienen dos zonas impares). Lo digo porque lo normal es que las ciudades con río solo tengan dos zonas (como Londres) o tres (como Roma), y es razonable que los vecinos no se hagan preguntas sobre los puentes. Hacía falta una ciudad con al menos cuatro zonas para que alguien se planteara el problema que dio inicio a la teoría de grafos.
Bibliografía y referencias
[1] Basado en el texto de S. K. Stein: Mathematics, the Man-Made Universe (1963). El libro es una locura, recomendadísimo. El capítulo 10 lo dedica a las «Memory wheels», los ciclos de De Bruijn.
[2] A. H. Fox Strangways, «The Music of Hindostan». Oxford at the Clarendon Press, 1914.
[3] Telégrafo de Baudot (véase también referencia [16]).
https://museotelecomvlc.webs.upv.es/telegrafo-baudot/
[4] T. E. Stern y B. Friedland, «Application of Modular Sequential Circuits to Single Error-Correcting P-Nary Codes», 1959.
[5] Para el problema de los puentes de Königsberg voy a citar a L. Euler, «Solutio problematis ad geometriam situs pertinentis» (1741). Hay una versión traducida al inglés en el libro «Graph Theory: 1736-1936», de N. L. Biggs, E. K. Lloyd y R. J. Wilson.
[6] Sobre la pronunciación de Euler: Mucha gente lo pronuncia como se escribe en español, /euler/. La pronunciación alemana es parecida a /oilah/, pero el acento Suizo la aproxima más a /oiler/. También está la versión latinizada del nombre: Eulero.
En cualquier caso, estas son pronunciaciones que no introducen sonidos ajenos al español, ni vocales extrañas. Intento elegir este tipo de pronunciaciones: similares al nombre original pero evitando fonemas no españoles. Lo mismo podríamos decir de Königsberg, donde la «ö» no es la del español, está a medio camino de sonar como una «e».
[7] Sobre la historia los puentes de Königsberg, hay una recopilación de cartas que muestran las impresiones de Euler:
H. Sachs, M. Stiebitz y R. J. Wilson, «An Historical Note: Euler‘s Konigsberg Letters», 1988.
https://www.ime.usp.br/~yw/2012/grafinhos/aulas/material-aulas/Paper-Euler-Letters.pdf
[8] En el vídeo solo consideramos grafos conexos: aquellos en que puedes ir a cualquier zona de la ciudad cruzando puentes. No hay zonas aisladas.
[9] He elegido la versión de «Graphs and Digraphs», de G. Chartrand y L. Lesniak (1986). En él, también consideran la versión del teorema con grafos dirigidos.
[10] SOLO PARA GRAFOS CONEXOS, COMPADRE.
[11] La mesa está expuesta en el Museo de las Matemáticas de Huesca. Aprovecho para dar las gracias a Julio.
https://planetariodearagon.com/museo-matematicas/
[12] I. J. Good, «Normal Recurring Decimals». 1946.
[13] Considero que este es el mismo teorema de Euler, como comento en [9]. La demostración es análoga en el caso de grafos y digrafos.
[14] Claramente, el artículo explica el método para secuencias de cualquier longitud, y solo da el caso de los tríos como un ejemplo.
[15] Varias cosas sobre N. G. de Bruijn.
- Sobre las secuencias de De Bruijn: https://mathworld.wolfram.com/deBruijnSequence.html
- En «A combinatorial problem» (1946) calcula cuántas soluciones distintas tiene el problema. https://dwc.knaw.nl/DL/publications/PU00018235.pdf
- En «Acknowledgement of priority to C. Flye Sainte-Marie…» (1975) explica que ya habían demostrado lo mismo en 1894 (ay, ¡qué faena!).
http://alexandria.tue.nl/repository/books/252901.pdf - El nombre, hasta donde he podido averiguar viendo la televisión holandesa por Internet, se pronuncia de forma similar a como lo digo.
[16] La patente americana es de 1888.
https://patents.google.com/patent/US388244A/
La directora del museo de las telecomunicaciones me pasó un «Tratado de telegrafía eléctrica», de H. Thomas, 1903, que es una delicia.
[17] En efecto, las letras latinas son un código en sí. Todo lenguaje necesita un código.
[18] No es el diseño original que aparece en [16]. Le he quitado algunos dientes que no servían para imprimir letras, sino para tareas de control.
[19] Sobre el código de Baudot, se puede consultar la Wiki o visitar «The Evolution of Character Codes, 1874-1968» de Eric Fischer https://ia800606.us.archive.org/17/items/enf-ascii/ascii.pdf
[20] ¿Usamos secuencias de De Bruijn para la corrección de errores en 2023? Es difícil contestar, porque en realidad nunca se han usado directamente. Lo que usamos son propiedades de grupos finitos para codificar y decodificar mensajes de forma eficiente. Muchas de estas propiedades son equivalentes, después de varios pasos lógicos, a la existencia de los ciclos de De Bruijn. En los años sesenta, la relación era bastante clara (en el artículo [4] aparecen ciclos de forma explícita). Pero la tecnología avanza y la corrección de errores es cada vez más elaborada; en consecuencia, más alejada de algo que se pueda reconocer como secuencias de De Bruijn.