Caminando por las aristas de un cubo

Enunciado

Veamos cómo son los caminos de longitud corta, para comprobar que hemos entendido bien el problema.

Vértices de un cubo

Los vértices A y B son opuestos en una cara. Supongamos que los otros dos los nombramos como C y D. Hay un tercer vértice conectado a A, que podemos llamar E. También hay otro conectado a B, que llamamos F. Por último, en esta cara nos quedan por nombrar otros dos vértices, que podemos nombrar como G (conectado a C) y H (conectado a D).

Los caminos de longitud 1 que parten de A son AC, AD y AE. Los de orden dos son ACA, ADA y AEA, que acaban en A, ACB y ADB, que acaban en B (3 a 2), y ACG, ADH, AEG y AEH. el problema es que cada vez que aumentamos la longitud de caminos, su cantidad queda multiplicada por 3, de forma que la cosa se complica para los de orden 3 y los de orden 4 (que son los que, de nuevo, pueden acabar en A o en B).

Si tratamos de prescindir de los demás, y nos fijamos sólo en los que acaban donde interesa, los de longitud 4 que acaban en A serán ACACA, ACADA, ACAEA, ACBCA, ACBDA, ACGCA, ACGEA, ADACA, ADADA, ADAEA, ADBCA, ADBDA, ADHDA, ADHEA, AEACA, AEADA, AEAEA, AEGEA, AEGCA, AEHEA, AEHDA, en total 21 caminos. Los que van de A a B serán ACACB, ACADB, ACBCB, ACBDB, ACBFB, ACGCB, ACGFB, ADACB, ADADB, ADBCB, ADBDB, ADBFB, ADHDB, ADHFB, AEACB, AEADB, AEGCB, AEGFB, AEHDB, AEHFB, es decir, 20 caminos.

Esto nos enseña dos cosas. Hay un camino más de A a A que de A a B en longitud dos y cuatro, y que los caminos que acaban en A proceden de tres direcciones (C, D y E) y los que acaban en B de otras 3 (C, D y F).

Veamos qué pasa en la longitud 6. En estos caminos, el paso 4 antes de llegar a A sólo puede ser A, B, H o G. Los caminos de longitud 4 que llegan a A son 21, y los que llegan a B, 20. Los que llegan a H o G, por la simetría de su posición serán también 20 a cada uno de ellos. En total, tendremos 21*3 + 20*2 + 20*2 + 20*2 = 21*3 + 20*6 = 183. Los que llegan a B, en el paso 4 han llegado a A, B, G o H, por lo que serán un total de 21*2 + 20*3 + 20*2 + 20*2 = 21*2 + 20*3 + 20*4 = 182. De nuevo uno más.

Probemos a demostrarlo por inducción. Supongamos que la cantidad de caminos que llegan en el paso n de A a A es s y la que llega de A a B es s - 1. De la misma forma, por simetría, de A a H o G serán también s - 1. en el paso n + 2, la cantidad de caminos que llegan a A es s*3 + (s - 1)*2*3 = 9s - 6. La cantidad de caminos que llegan a B serán (s -1)*3 + s*2 + (s - 1)*4 = 9s - 7. Es evidente que hay un camino menos de A a B que de A a A (además, podríamos calcular con precisión cuántos habría reiterando la fórmula).