Una superpermutación de n símbolos es una cadena que contiene todas las permutaciones de esos n símbolos como subcadenas. En el mundo del anime japonés, determinar la superpermutación de 14 símbolos se llama problema de Haruhi. En una wiki de anime, un usuario anónimo ha publicado la mejor cota mínima a la longitud de una superpermutación de n símbolos, en concreto, n! + (n−1)! + (n−2)! + n−3, junto a una sencilla demostración. Varios matemáticos han verificado dicha demostración y la han formalizado con rigor. El matemático Aaron Williams demostró en 2013 que la mejor cota máxima para n ≥ 7 es n! + (n−1)! + (n−2)! + (n−3)! + n−3. Como ves, la nueva cota mínima no es muy ajustada, se encuentra (n−3)! por debajo.

El problema de determinar el tamaño mínimo de una superpermutación se suele divulgar usando series de TV. Con n episodios, si quieres verlos todos en todos los órdenes posibles, ¿cuál es el número mínimo de episodios que deberías ver? Una superpermutación óptima es la que tiene longitud mínima. Las primeras cuatro superpermutaciones óptimas son únicas y tienen longitudes de 1, 3, 9 y 33. Para n=2 la respuesta es sencilla, la secuencia 121, de longitud 3 = 1! + 2!. Para n=3 tienes que pensar un poco más para llegar a la secuencia 123121321, de longitud 9 = 1! + 2! +3!; la figura te muestra cómo dicha superpermutación contiene las 6 permutaciones de los tres primeros números naturales. Usando esta solución puedes construir la óptima para n=4, como te muestra la figura, con longitud 33 = 1! + 2! + 3! +4!. Dicha construcción permite obtener 2 de las 8 superpermutaciones óptimas con n=5. Pero no funciona para n=6, pues predice una longitud de 1! + 2! + … + 6! = 873, cuando se conoce una mejor de solo 872 símbolos.

La nueva cota mínima se publicó en «The Haruhi Problem,» wiki; me he enterado gracias a un tuit de Robin Houston‏ @robinhouston. La versión formal aparece en Jay Pantone, «A lower bound on the length of the shortest superpattern,» PDF 22 Oct 2018. Si te interesan las superpermutaciones te recomiendo leer a Greg Egan, «Superpermutations,» Web Oct 2018. La figura y la construcción hasta n=5 son de Nathaniel Johnston, «The Minimal Superpermutation Problem,» Blog, 10 Apr 2013; que no funciona para n=6 se muestra en Nathaniel Johnston, «“Obvious” Does Not Imply “True”: The Minimal Superpermutation Conjecture is False,» Blog, 22 Aug 2014. Y la prueba de Aaron Williams de la mejor cota máxima está en «Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 … n) and τ = (1 2),» arXiv:1307.2549 [math.CO].