Olimpiadas de Matemáticas
Página de preparación y problemas

Vamos a contar los caminos $x_n$ teniendo en cuenta primero las dos primeras aristas recorridas partiendo de $A$ y luego las $2n-2$ restantes para volver a $A$. Cuando hacemos recorremos una distancia 2 partiendo de $A$, tenemos nueve caminos posibles: dos acaban en $B$, dos acaban en $C$, dos acaban en $D$ y tres vuelven a $A$. Si acabamos en $B$, $C$ o $D$, para volver a $A$ en los $2n-2$ pasos restantes, tendremos $y_{n-1}$ posibles caminos ya que se trata de ir de un vértice a otro diagonalmente opuesto de la misma cara. Si estamos en $A$, tendríamos $x_{n-1}$ posibles caminos para quedarnos en $A$ tras estos $2n-2$ pasos. Esto nos da la recurrencia $x_n=3x_{n-1}+6y_{n-1}$. De la misma forma, si tras los dos primeros pasos acabamos en $A$, $C$ o $D$, para acabar en $B$ tras los $2n-2$ restantes tenemos $y_{n-1}$ posibles caminos y si estamos en $B$ tenemos $x_{n-1}$ caminos. Esto nos otra recurrencia $y_n=2x_{n-1}+7y_{n-1}$ y tenemos así el sistema \[\left\{\begin{array}{l}x_n=3x_{n-1}+6y_{n-1},\\y_n=2x_{n-1}+7y_{n-1}.\end{array}\right.\]

Veamos dos formas de terminar el problema:

• Si restamos ambas ecuaciones, obtenemos $x_n-y_n=x_{n-1}-y_{n-1}$ para todo $n$ luego la diferencia entre ambas sucesiones no varía. Como $x_1=3$ e $y_1=2$, deducimos que $x_n=y_n+1$ para todo entero positivo $n$. Para $n=500$, tenemos la respuesta: hay más caminos de longitud $1000$ que que van de $A$ a $A$ que caminos de longitud $1000$ que van de $A$ a $B$.
• La otra alternativa es probar por inducción que $x_n\gt y_n$ para todo número natural $n$, lo que en particular nos dirá que $x_{500}\gt y_{500}$. Para $n=1$, se tiene claramente que $x_1=3$ e $y_1=2$. Supuesto que se cumple que $x_{n-1}\gt y_{n-1}$ para cierto valor de $n$, también se cumple para el siguiente valor ya que \[x_n=3x_{n-1}+6y_{n-1}=2x_{n-1}+x_{n-1}+6y_{n-1}\gt 2x_{n-1}+y_{n-1}+6y_{n-1}=2x_{n-1}+7y_{n-1}=y_n.\] Esto prueba la desigualdad que queríamos y termina la demostración.

Nota. El sistema de ecuaciones en recurrencias anterior se puede resolver, aunque esto es de un nivel bastante superior al que se espera en esta olimpiada, y puede calcularse explícitamente $x_n=\frac{1}{4}(9^n+3)$ e $y_n=\frac{1}{4}(9^n-1)$.