Las soluciones matemáticas se pueden encontrar en lugares sorprendentes, incluidos los reinos oscuros de Internet. En 2011, un póster anónimo en el tablero de imágenes ahora infame 4chan planteó un rompecabezas matemático sobre la serie de anime de culto clásico La melancolía de Haruhi Suzumiya. Aunque el tablón de anuncios se ha llenado de contenido odioso, violento y extremo, esa publicación original condujo a una solución al sofisticado problema matemático.
La primera temporada de esta serie de anime consta de 14 episodios que fueron diseñados para que pueda verlos en cualquier orden que desee. (Para las personas que no están familiarizadas con el mundo del anime como yo: un thriller de acción en vivo de ocho partes llamado Caleidoscopio en Netflix sigue el mismo principio). En algún momento de una discusión de 2011 de la serie sobre 4chan, alguien preguntó el número mínimo de episodios que tendrían que ver para haberlo visto en todos los ordenes posibles.
De hecho, esta pregunta está relacionada con las llamadas superpermutaciones. Y resulta que esta área matemática tiene muchos rompecabezas: hasta el día de hoy, los matemáticos aún no pueden responder completamente el problema que el usuario 4Chan había planteado.
Sobre el apoyo al periodismo científico
Si está disfrutando de este artículo, considere apoyar nuestro periodismo galardonado con suscripción. Al comprar una suscripción, está ayudando a garantizar el futuro de las historias impactantes sobre los descubrimientos e ideas que dan forma a nuestro mundo hoy.
Pero sorprendentemente, en esa discusión, uno de los usuarios anónimos hizo una estimación de la cantidad mínima de todos los episodios para ver con un enfoque que anteriormente era desconocido para los matemáticos. “Necesitaré [elaborate on] Esto en múltiples publicaciones. Por favor, búscalo en busca de lagunas que haya perdido ”, escribió el usuario, quien explicó en varios pasos cómo llegaron a su estimación. Otros usuarios tomaron los argumentos y los discutieron, pero fuera de 4chan, nada de esto hizo olas. Nadie parecía tomar nota.
Extremo atracón
En matemáticas, dos objetos permiten cuando son reorganizados o recombinados. Por ejemplo, puede permutar AB a BA. Si una serie de anime consistiera en solo dos partes, podría ver el primer y luego el segundo episodio (1-2) o el segundo y luego el primero (2-1).
Si desea ver una serie en múltiples arreglos, tal vez para descubrir qué secuencia de episodios tiene más sentido, necesita una superpermutación. Esta es una secuencia de todas las permutaciones posibles. Imagine un maratón que muestra dónde ves el primer episodio, seguido del segundo, y luego mira el segundo episodio, seguido del primer (1-2-2-1). Para evitar ver el segundo episodio dos veces seguido, una superpermutación más corta sería 1-2-1; Solo tendría que ver tres episodios para que todavía tenga todos los pedidos posibles cubiertos.
Si una serie consta de tres episodios, se vuelve un poco más complicado encontrar la superpermutación más corta. En este caso, hay 3! = 6 secuencias diferentes: 1-2-3, 1-3-2, 2-3-1, 2-1-3, 3-1-2, 3-2-1. Afortunadamente, no tiene que ver 3 × 6 = 18 partes, pero puede encontrar un atajo inteligente, en este caso: 1-2-3-1-1-1-1-3-2-1. Esa orden contiene todas las permutaciones posibles de los números 1, 2 y 3, ¡pero solo tienes que ver nueve episodios!
Los matemáticos también han calculado las superpermutaciones más cortas para una serie que consiste en norte = 4 y norte = 5 episodios (33 y 153 episodios, respectivamente). Más allá de eso, sin embargo, están en la oscuridad. Las superpermutaciones más cortas para norte > 5 no se conocen.
De hecho, el desafío se relaciona con uno de los problemas más intratables en las algoritmics: el problema del vendedor ambulante. En este problema, una persona quiere visitar diferentes ciudades y terminar en su ciudad natal. La tarea es encontrar la ruta más corta que conecta todas las ciudades. La superpermutación más corta es una variación de este problema en el que las permutaciones individuales representan diferentes ciudades. En este caso, asigna diferentes distancias entre las ciudades determinando la superposición de las permutaciones. Por ejemplo, las ciudades 1-2-3 y 2-3-1 tienen una gran superposición: los últimos dos dígitos de la primera permutación coinciden con los dos primeros dígitos del segundo, por lo que se pueden combinar para formar 1-2-3-1. Por lo tanto, podemos asignar una corta distancia entre esas dos ciudades. Por otro lado, 1-2-3 y 2-1-3 no se superponen. (Para ver ambas secuencias, debe mirar las seis partes completas; no es posible ningún atajo). Por lo tanto, estas ciudades tienen una gran distancia entre ellas.
Para encontrar la ruta más corta dentro de las permutaciones, conectas las permutaciones que más se superponen. Solo hay una dificultad: no hay un algoritmo conocido que resuelva el problema del vendedor de viajes rápidamente. Si estamos tratando con algunas ciudades, o, en el caso de una serie de anime, algunos episodios, este no es un gran inconveniente. Pero tan pronto como el norte se vuelve grande, las computadoras fallan en la tarea porque el tiempo de computación crece exponencialmente con norte.
Las computadoras pueden calcular las superpermutaciones para norte = 4 y norte = 5 Pero no para nada más allá de eso. Y aunque es posible calcular las superpermutaciones elaboradas para un número mayor, encontrar la superpermutación más corta se vuelve más difícil.
Por lo tanto, los expertos deben conformarse con las estimaciones. Por ejemplo, hay un algoritmo que ayuda a estimar la longitud de la superpermutación más corta posible para norte Objetos: 1! + 2! + 3! + … + norte! Usando ese algoritmo, si norte = 2, obtienes una superpermutación de longitud 1 + 2 = 3. Para norte = 3, esto da como resultado una longitud de 1 + 2 + 6 = 9. Para norte = 4, obtienes 33. Y para norte = 5, obtienes 153, que corresponde a la superpermutación más corta en cada caso.
Para más grande norte, Sin embargo, este algoritmo ya no se aplica: las computadoras han podido encontrar superpermutaciones más cortas de lo que sugiere que existe. De hecho, la Fórmula 1! + 2! + 3! + … + norte! sobreestima masivamente la longitud de la superpermutación más corta para norte. Aunque el algoritmo ofrece solo una respuesta aproximada, los matemáticos la usan como un lugar de partida, con el objetivo de reducir las opciones para encontrar respuestas más precisas.
Coincidencias y redescubrimientos
En 2013, Nathaniel Johnston, ahora profesor de matemáticas en la Universidad Mount Allison en New Brunswick, aterrizó en un Melancholia de Haruhi Suzumiya Página de fandom. El propio Johnston no era fanático del anime. Había llegado al sitio después de buscar en Google algunos términos de búsqueda relacionados con las superpermutaciones. Allí se encontró con la discusión que se había celebrado en 4chan casi dos años antes, que un usuario había copiado en el sitio de fandom.
Johnston no se molestó en hacer las matemáticas pero citó la publicación de fandom en su blog. Este comentario también pasó desapercibido durante varios años.
Luego, en octubre de 2018, el matemático Robin Houston se encontró con la publicación de blog de su colega a través de una curiosa coincidencia. Houston acababa de enterarse de que el autor de la ciencia ficción australiana Greg Egan había encontrado un nuevo máximo Longitud para las superpermutaciones más cortas, expresadas como:
norte! +(norte –1)! + (norte – 2)! + (norte – 3)! + + norte – 3
Eso en sí mismo era extraño. Pero cuando Houston comenzó a aprender más sobre este resultado, se dio cuenta de que la longitud mínima de una superpermutación había recibido un nuevo valor por un usuario anónimo de fandom de anime (no sabía sobre los orígenes en 4chan en ese momento). La fórmula para la longitud mínima es:
norte! +(norte – 1)! + (norte – 2)! + + norte – 3
Houston compartido Su descubrimiento en Twitter (ahora x) el 23 de octubre de ese año. “Una situación curiosa. El mejor límite inferior conocido para la longitud mínima de las superpermutaciones fue probado por un usuario anónimo de un wiki dedicado principalmente al anime ”, escribió.
Junto con sus colegas, los matemáticos Jay Pantone y Vince Vatter, Houston, decidió revisar la prueba del usuario 4chan y escribirla de manera matemática. Los investigadores publicaron su trabajo matemático a la enciclopedia en línea de secuencias enteras ese mismo mes, y el primer autor figura como “póster anónimo 4chan”.
Entonces, ¿qué nos dicen estas fórmulas? Si quieres ver todos los episodios de un norte-PARTA DE PARTE En todas las combinaciones posibles, debe sentarse al menos norte! +(norte – 1)! + (norte – 2)! + + norte – 3 episodios, esa es la contribución del usuario 4chan, y a lo sumo norte! +(norte – 1)! + (norte – 2)! + (norte – 3)! + + norte – 3, que conocemos a través del trabajo de Egan.
En el caso de la serie de ocho episodios Caleidoscopio, Tendría que ver al menos 46,085 y, como máximo, 46,205 episodios. Para La melancolía de Haruhi Suzumiya, o Haruhi, Con 14 episodios, el número aumenta drásticamente: un mínimo de 93,884,313,611 episodios y un máximo de 93,924,230,411. Recuerde que esta no es una solución completa: solo establece un rango para el tamaño de una superpermutación que le permitiría ver eficientemente la serie en cada orden posible.
Afortunadamente, Egan también proporcionó un algoritmo para construir la superpermutación correspondiente. Esto permite Haruhi Fans para resolver el mejor orden de visualización de episodios. Pero con una duración promedio del episodio de alrededor de 24 minutos, tomaría unos 4 millones de años para sentarse a través de esta superpermutación.