Por @Alvy — 3 de Abril de 2014

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.)

Compartir en Flipboard Compartir en Facebook Tuitear

PUBLICIDAD




PUBLICIDAD


Microsiervos Selección


Los números trascendentes

EUR 11,40 (Reseña en Microsiervos)

Comprar


The Code Book: The Secret History of Codes and Code-breaking

EUR 9,68

Comprar


Amazon Associates

Los productos aquí enlazados están a la venta en Amazon. Incluyen un código de Afiliado Amazon Associates que nos cede un pequeño porcentaje de las ventas. Los productos están seleccionados por los autores del blog, pero ni Amazon ni los editores de los libros o fabricantes de los productos participan en dicha selección.

Más libros y productos en:

Microsiervos Selección