Acomodando Fichas

Ponente(s): Itzel Anahí Marcial Campos, Mika Olsen, Julián Alberto Fresan Figueroa.

El ejercicio consta en tener una gráfica con los vértices numerados y acomodados, sobre estos vértices se tienen fichas numeradas, pero en desorden, de tal forma que se tienen que acomodar de acuerdo con el orden que tiene los vértices y con la condición de que solo se pueden intercambiar aquellas fichas que las conecte una arista. Entonces la pregunta que se hace es: ¿Cuál es la cantidad máxima de pasos para poner todas las fichas en su lugar? Teniendo presente todo esto, se analiza si existe alguna fórmula para encontrarlo. En un principio se analizan las trayectorias con un número de vértices mayor a 2: con esto se hace una gráfica a partir de todas las posibles combinaciones de los números y de acuerdo con el número de pasos que se tienen que llegar para que todas las fichas se encuentren en su lugar. Entonces se hacen notables propiedades que cumple esta gráfica, por ejemplo, que es bipartita y por lo tanto 2-coloreable. Además de que si se hace un isomorfismo de la misma gráfica se pueden observar ciclos y se ven unidos entre ellos, destacando que estos ciclos se pueden en la gráfica que se forma con un vértice menos. Este análisis lleva a encontrar una fórmula [(n*(n-1)) /2]. Después de la trayectoria se plantean 2 tipos más de grafos; estrellas y ciclos, con n número de vértices. Consideramos el mismo número de vértices que el de fichas, es decir hay n número de vértices y n número de fichas. Numeramos tanto las fichas como los vértices empezando por el 1, después el 2, continuando así hasta llegar a n, entonces podemos acomodar las fichas de acuerdo con el número con el vértice que le corresponde. Pero suponiendo que las fichas no se encuentran en su lugar, solo se pueden intercambiar entre ellas si los vértices en los que están son adyacentes, por lo que a cada intercambio que se haga se contara como un movimiento. Teniendo presente lo anterior, hacemos n=4, tanto para la estrella como para el ciclo y así se plantea el averiguar cuál es el número máximo de movimientos que se tienen que hacer para que todas las fichas se encuentren en su lugar. Lo cual nos lleva a formar nuevas gráficas, pero los vértices están conformados por las combinaciones y son adyacentes si, de acuerdo con el tipo de gráfica, entre ellos es un intercambio valido de fichas. Se concluye con las variaciones que se le pueden dar a este ejercicio y que pueda ser útil para su aplicación.