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.










lunes, 6 de diciembre de 2021

Trenzas y orden

 Vamos a plantearnos un reto. Supongamos que disponemos de un conjunto de tres elementos ordenados en fila, por ejemplo {1, 2, 3} y ponemos una regla simple: A cada paso sólo pueden intercambiar el orden dos elementos contiguos. La pregunta que podríamos hacernos sería ¿Cuáles serían los pasos mínimos necesarios para disponer de todas las posibilidades de orden. 

En el ejemplo dado habría que buscar la forma de obtener las 6 posibles formas de ordenar estos 3 elementos. Es decir, 123, 132, 213, 231, 312 y 321. Pero recordando la regla, sólo un intercambio de dos elementos contiguos cada vez.

Un solución sería: 123, 132, 312, 321, 231, 213. Si la visualizáramos en un grafo esta solución se vería más fácil:



Llegado a este punto resulta fácil percatarse de que dicha solución es única si nos permitimos decir que la simétrica es la misma solución o si se empezara desplazado un paso.

CUATRO ELEMENTOS.

La cosa se complica cuando disponemos de cuatro elementos {1, 2, 3, 4} (NOTA: A veces pongo {0, 1, 2 3} Total, el uso de números es sólo gráfico no significan nada). Después de muchos intentos llegamos a la conclusión de que sólo hay cuatro maneras de disponer de los 24 conjuntos ordenado posibles de 4 elementos. Estos son:







En próximas entregas se demostrará que sólo pueden existir estas cuatro maneras de conseguir los 24 elementos diferentes de las 24 (4!) formas diferentes de disponer 4 elementos distintos. Para ello se utilizará sistemas de grafos. 
Se supone que una solución simétrica, antisimétrica o desplazada de las anteriores es la misma solución.

Nota: Aún es pronto para atreverse a 5 elementos (5!=120 ordenaciones diferentes)