Planeta octaédrico

Enunciado

Este problema es más complicado (o, por lo menos, más largo) de lo que parece a simple vista. Si tratamos de crear una de esas rutas por las aristas, de forma que pasen por todas, estamos, de nuevo, haciendo un problema de recorrido, pero si buscamos todas las rutas, también tenemos que hacer algo de combinatoria.

Ver que se pueden trazar rutas de este tipo es sencillo. Puesto que la ruta debe ser un circuito (acaba donde empieza), es evidente que en los vértices deben unirse una cantidad par de aristas, ya que por cada camino entrante hay uno que sale. En la figura que nos ocupa sí se cumple esto, porque en cada vértice concurren cuatro aristas.

Octaedro con vértices

Podemos nombrarlas, para aclararnos, como A (ciudad alta), B (otro vértice del ecuador, unido con A por una arista), C (polo norte), D (el otro vértice del ecuador, al lado opuesto a B), E (polo sur) y F (las antípodas de A). Una ruta del tipo que buscamos podría ser ABCDACFEBFDEA. Podemos confirmar que es válido porque pasa por todos los vértices dos veces (tres por el A, porque sale y llega a él), y por tanto usa todas las aristas, bien sea para entrar o para salir. Aunque debemos cuidar que no se repita ningún par de vértices (por ejemplo, EB y BE en la misma ruta). En total, siempre van a contar con 13 letras, siendo la primera y la última una A.

Si queremos hacer una estimación, podemos partir de cuatro caminos que salen de A, y que cada vez que lleguemos a un vértice (por primera vez) contamos con 3 caminos posibles. Si llegamos por segunda vez, sólo quedará un camino, salvo que volvamos a A, en cuyo caso quedarán 2 caminos. A partir de ahí, no hay más bifurcaciones, por lo que tendríamos un total de 4*3*3*3*3*3*2 posibilidades, lo que asciende a 1944 caminos. Sin embargo, algunos de estos caminos desembocan por tercera vez (y se acaban) en A antes de tiempo, por lo que el número real será inferior, y no conozco una alternativa mejor que contar uno a uno los caminos (me gustaría que si alguien la tiene, me informase). Mi idea consiste en trazar poco a poco los caminos, resumiendo en la medida de lo posible.

Partiendo de A, hay cuatro caminos que ofrecen simetría completa, por lo que vamos a contar a partir de uno de ellos, y luego multiplicaremos por 4. Supongamos entonces que empezamos por AB. Hay dos opciones a partir de aquí que son simétricas, doblar a C y doblar a E. De estas dos, bastará considerar sólo una, y luego multiplicar por dos los caminos. La opción de seguir a F hay que considerarla a parte.

Este bloque, entonces, lo empezamos con ABC.

Si volvemos a A (ABCA), tenemos dos opciones: D y E. Si llegamos a D (ABCAD), tenemos tres opciones (C, E, F). En C pasamos a F (ABCADCF) y volvemos a tener tres opciones, B, D y E. Por B, llegamos a E (ABCADCFBE) y sólo tiene dos opciones válidas (recuerda que no podemos llegar a A demasiado pronto): ABCADCFBEDFEA y ABCADCFBEFDEA. Si hubiésemos tirado por D, también pasamos a E y tenemos otras dos: ABCADCFDEBFEA y ABCADCFDEFBEA. Si hubiésemos tirado por E, sólo hay dos opciones más: ABCADCFEBFDEA y ABCADCFEDFBEA. Desde ABCAD, podíamos haber pasado a E como segunda opción, y nos habríamos encontrado con las 4 rutas siguientes: ABCADEBFCDFEA, ABCADEBFDCFEA, ABCADEFCDFBEA y ABCADEFDCFBEA. Por último, desde ABCAD, pasando a F, tenemos 6 rutas más, ABCADFBEDCFEA, ABCADFBEFCDEA, ABCADFCDEBFEA, ABCADFCDEFBEA, ABCADFEBFCDEA y ABCADFEDCFBEA. Por tanto, son 16 para el comienzo ABCAD. Si consideramos ABCAE, podemos contar otras 16, ABCAEBFCDEFDA, ABCAEBFCDFEDA, ABCAEBFDCFEDA, ABCAEBFDEFCDA, ABCAEBFEDCFDA, ABCAEBFEDFCDA, ABCAEDCFBEFDA, ABCAEDCFEBFDA, ABCAEDFBEFCDA, ABCAEDFEBFCDA, ABCAEFBEDCFDA, ABCAEFBEDFCDA, ABCAEFCDEBFDA, ABCAEFCDFBEDA, ABCAEFDCFBEDA y ABCAEFDEBFCDA. De momento, hemos analizado al completo ABCA, con un total de 32 rutas.

Si pasamos a D (ABCD), tenemos tres opciones: A, E y F. Desde ABCDA hay 12 posibilidades: ABCDACFBEDFEA, ABCDACFBEFDEA, ABCDACFDEBFEA, ABCDACFDEFBEA, ABCDACFEBFDEA, ABCDACFEDFBEA, ABCDAEBFDEFCA, ABCDAEBFEDFCA, ABCDAEDFBEFCA, ABCDAEDFEBFCA, ABCDAEFBEDFCA y ABCDAEFDEBFCA. Desde ABCDE, hay 16 posibilidades: ABCDEACFBEFDA, ABCDEACFEBFDA, ABCDEADFBEFCA, ABCDEADFEBFCA, ABCDEBFCADFEA, ABCDEBFCAEFDA, ABCDEBFDACFEA, ABCDEBFDAEFCA, ABCDEBFEACFDA, ABCDEBFEADFCA, ABCDEFCADFBEA, ABCDEFCAEBFDA, ABCDEFDACFBEA, ABCDEFDAEBFCA, ABCDEFBEACFDA y ABCDEFBEADFCA. Desde ABCDF, hay otras 16 posibilidades: ABCDFBEACFEDA, ABCDFBEADEFCA, ABCDFBEDACFEA, ABCDFBEDAEFCA, ABCDFBEFCADEA, ABCDFBEFCAEDA, ABCDFCADEBFEA, ABCDFCADEFBEA, ABCDFCAEBFEDA, ABCDFCAEFBEDA, ABCDFEACFBEDA, ABCDFEADEBFCA, ABCDFEBFCADEA, ABCDFEBFCAEDA, ABCDFEDACFBEA y ABCDFEDAEBFCA. Por tanto, hemos analizado por completo ABCD, con un total de 44 posibilidades.

Por último en la opción ABC, si pasamos a F (ABCF), tenemos otras tres opciones, B, D y E. Desde ABCFB hay 16 posibilidades, ABCFBEACDEFDA, ABCFBEACDFEDA, ABCFBEADEFDCA, ABCFBEADFEDCA, ABCFBEDACDFEA, ABCFBEDAEFDCA, ABCFBEDCADFEA, ABCFBEDCAEFDA, ABCFBEDFEACDA, ABCFBEDFEADCA, ABCFBEFDACDEA, ABCFBEFDAEDCA, ABCFBEFDCADEA, ABCFBEFDCAEDA, ABCFBEFDEACDA y ABCFBEFDEADCA. Desde ABCFD, hay 12 posibilidades, ABCFDACDEBFEA, ABCFDACDEFBEA, ABCFDAEBFEDCA, ABCFDAEFBEDCA, ABCFDCADEBFEA, ABCFDCADEFBEA, ABCFDCAEBFEDA, ABCFDCAEFBEDA, ABCFDEBFEACDA, ABCFDEBFEADCA, ABCFDEFBEACDA y ABCFDEFBEADCA. Desde ABCFE, hay otras 16 posibilidades: ABCFEACDEBFDA, ABCFEACDFBEDA, ABCFEADEBFDCA, ABCFEADFBEDCA, ABCFEBFDACDEA, ABCFEBFDAEDCA, ABCFEBFDCADEA, ABCFEBFDCAEDA, ABCFEBFDEACDA, ABCFEBFDEADCA, ABCFEDACDFBEA, ABCFEDAEBFDCA, ABCFEDCADFBEA, ABCFEDCAEBFDA, ABCFEDFBEACDA y ABCFEDFBEADCA. Así, la opción ABCF también tiene 44 posibilidades.

En conclusión parcial, ABC tendría 44 + 44 + 32 = 120 posibilidades, más otras 120 simétricas si tomamos ABE, como hemos dicho antes. Queda analizar ABF. De nuevo nos planteamos tres posibilidades, C, D y E. En este caso, de nuevo por simetría, ABFC y ABFE tendrán exactamente el mismo tipo de ramificaciones.

Si pasamos a C (ABFC), tenemos tres posibilidades, desde ABFCA hay 12 posibilidades, desde ABFCB 16, y 16 más desde AFCD (no creo que sea conveniente detallarlas todas, pero si alguien siente curiosidad, que pregunte). En total, 44 rutas (y las mismas en ABFE).

Si pasamos a D (ABFD), tenemos otras tres posibilidades, A, C y E. De nuevo, 12, 16 y 16 caminos se abren ante nosotros. Otras 44 rutas.

Por tanto, ABF tiene un total de 44*3 = 132 rutas. Después de este cálculo, el número de rutas que empiezan por AB es 120 + 120 + 132 = 372. Como la figura es simétrica, comenzar por otra arista cualquiera daría el mismo resultado, luego hay exactamente 372*4 = 1488 rutas distintas que empiezan (y acaban) en A.

Las otras preguntas son mucho menos difíciles de contestar. Si una arista queda intransitable, dos vértices quedan con un número impar de aristas. Si queremos saber cuántas no podremos recorrer en un circuito, habrá que elegir un vértice intermedio, y quitar dos, una a cada vértice, y recuperaremos la paridad de aristas en los vértices. En total, habremos perdido tres aristas, la intransitable y dos más. Necesariamente estas tres aristas comparten dos vértices, luego forman un triángulo (una cara completa).

Si se pretende solucionar el problema pasando más veces por aristas, sería como añadir caminos, pero sucede algo similar, debemos añadir dos aristas más que alteren la paridad de dos vértices, ya que la que los une está intransitable. Por tanto, deberemos recorrer dos aristas dos veces cada una (forman un triángulo con la arista prohibida) como mínimo para restaurar la ruta.