TU ANUNCIO / YOUR PUBLICITY

AQUÍ PODRÍA ESTAR TU ANUNCIO: / HERE COULD BE YOUR AD E-mail

domingo, 26 de diciembre de 2021

Trenzas y orden (II)

 El paso siguiente es tomar uno de los sistemas de ordenación y basar el resto de sistemas en éste. Se toma el sistema "α":

Se ha supuesto un orden de las 24 formas en que se pueden ordenar los elementos del conjunto {1, 2, 3, 4}.Éstos van recorriendo la línea azul oscuro. Las líneas azul claro serían "atajos", otras posibilidades.
Lo mejor es verlo tomando un punto, por ejemplo el 9: [1423] si se cambian dos contiguos de la serie α serían el 8: [1243] o el 10:[4123] y no contiguo de la serie sería el 16:[1432].
El plan para buscar otras soluciones sería bastante simple. Hay que imaginar que los puntos son clavos y que lo que se quiere es recorrer todos los puntos con un hilo sin pasa dos veces por el mismo punto y por los caminos azules (claros u oscuros).

Aclaración: se ha establecido este sistema ya que sería más simple que aplicar la fuerza bruta. 24 cruces en tres posiciones cada uno sería 324 = 282.429.536.481. Y si se tuviera en cuenta que una de la posiciones no pudiera repetirse sería 224 = 16.777.216.

La forma de ir buscando soluciones sería ir tomando camino y descartando el resto, de la forma:


Ésta es sólo una parte. Al ir buscando recorridos cerrados se van encontrando soluciones y al descartar las repetidas se obtiene un pequeño número de recorridos:

De esta forma queda demostrado que sólo hay 4 soluciones cíclicas que permiten obtener los 24 posiciones posibles de 4 elemento cambiando sólo 2 elementos colaterales en cada paso.

Se subraya la palabra cíclica porque si no se deseara que el final de los cambios volviera al principio habría alguna solución más como la siguiente:

¿Y si no fuera una solución cíclica?


Un sólo contraejemplo daría pie a buscar las posibles soluciones no cíclicas. En la figura superior hay una. La cuestión ahora es saber cuantas más habrá. Pero eso quedará explicado en otro momento.










No hay comentarios:

Publicar un comentario