miércoles, 16 de abril de 2014

1302 - Una variante sobre las supermutaciones mínimas

A raíz de los comentarios de Vicente Iq. y Carlos Rivera de la entrada sobre supermutaciones mínimas para los números del 1 al 5, surgió la siguiente inquietud:

Es posible con cinco dígitos formar una cadena la cual incluye una sola permutación, ej: ABCDE
Con seis dígitos podemos obtener una cadena con dos permutaciones diferentes: ABCDEA (ABCDE - BCDEA)
Así para n dígitos vamos obteniendo un máximo de n-4 permutaciones, por ejemplo en la cadena de 14 dígitos ABCDEABCEDABCE estan incluidas las siguientes 10 permutaciones (todas diferentes):

ABCDE
BCDEA
CDEAB
DEABC
EABCD
ABCED
BCEDA
CEDAB
EDABC
DABCE

Si tomamos también como válidas las permutaciones tomadas de derecha a izquierda vemos que en esta misma cadena se pueden formar otras 10 permutaciones, es decir que dentro de esta cadena de 14 dígitos hay 20 permutaciones diferentes si vale la lectura en ambos sentidos.

a) ¿Cuál es la mayor cadena de n dígitos, compuesta por los dígitos del 1 al 5 que pueden obtener, la cual contenga  n-4 permutaciones distintas leidas de izquierda a derecha?

b)¿ Cuál es la mayor cadena de n dígitos, compuesta por los dígitos del 1 al 5, que pueden obtener, la cual contenga 2n-8 permutaciones distintas si vale la lectura en ambos sentidos?
Si lo quieres compartir o guardar
Share/Bookmark

1 comentario:

  1. Para la parte b):
    Algunas cadenas óptimas para longitudes de 6 a 11 dígitos.
    6 dígitos {2,1,3,5,4,2} contiene 4 permutaciones (2x6-8)
    7 dígitos {3,5,2,1,4,3,5} 6 permutaciones.
    8 dígitos {4,3,2,5,1,4,3,2} 8 permutaciones.
    9 dígitos {4,2,1,5,3,4,2,1,5} 10 permutaciones
    10 dígitos {3,2,1,5,4,3,2,1,5,4} 12 permutaciones
    11 dígitos {5,3,2,1,4,5,3,2,1,4,5}, 14 permutaciones.

    Vicente iq.

    ResponderEliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!