Una superpermutación mínima es la cadena de símbolos de longitud en mínima en la que aparecen todas las permutaciones de esos símbolos en algún punto de la cadena.
Por ejemplo con los números 1, 2 y 3 sería 123121321 porque cualquier cadena (ej. 312) aparece en su interior; y así con todas las combinaciones de 1-2-3.
Examinando el problema para n dígitos, de forma genérica, para n=1 la cadena es 1 y para n=2 la cadena sería 121, que contiene tanto 12 como 21. Para n=3 es 123121321 – el asunto crece rápido.
Ahora bien, para n=4 la cadena es
123412314231243121342132413214321
una complicación descomunal respecto a la solución anterior.
Y para n=5 se desconoce todavía la solución. En otras palabras: se conocen ciertas soluciones con todos los símbolos 1-2-3-4-5 (al fin y al cabo hay 120 combinaciones y se podrían hasta poner todas seguidas) pero no cuál es la solución mínima, la superpermutación. Es tremendamente difícil de calcular por fuerza bruta, incluso con potentes ordenadores.
Así que a lo mejor podrías encontrarla tú.
(Vía MathPuzzle.)
No hay comentarios:
Publicar un comentario