Foro de Práctico

Buenas Nicolás,
Te recomiendo que llames de alguna manera a los vértices inicial y final, pongamos $a$ y $b$ respectivamente.

Estoy de acuerdo contigo que hay precisamente $2^{98}$ caminos cualesquiera de longitud $98$ que inician en $a$. Pero hay muchos de ellos que, luego del paso $98$, ya están en el vértice $b$ y por lo tanto no van a poder terminar en el vértice $b$ tras agregar un paso. Es por eso que no funciona tu conteo (ese "paso" que agregas a cada uno de los $2^{98}$ caminos no es siempre posible, y esto te lleva a contar en exceso).

Hay diversas maneras para resolver este ejercicio. Comento en lo que sigue una posibilidad, que es mediante recurrencias.

Si llamas $a_n$, $b_n$ y $c_n$ a la cantidad de caminos que inician en el vértice $a$, tienen longitud $n$ y terminan respectivamente en los vértices
$a$, $b$, o $c$ entonces como todos los caminos de longitud $n$ que empiezan en $a$ son $2^n$, la regla de la suma nos dice que $a_n+b_n+c_n=2^n$.

Por simetría tenemos que $b_n=c_n$. Reemplazando en la primera igualdad tenemos que $a_n + 2b_n = 2^n$.

Además todo camino de longitud $n+1$ que termina en $a$ viene de $b$ o bien de $c$, por lo que
$a_{n+1}=b_n+c_n$, y como $b_n=c_n$ tenemos que $a_{n+1}=2b_n$. Reemplazando nuevamente tenemos que $2b_n+2b_{n+1}=2^{n+1}$, y cancelando un factor común $2$ obtenemos que $b_{n+1}+b_n = 2^n$ con dato inicial $b_1=1$.

Hemos obtenido una recurrencia lineal de orden 1 no homogénea. Su solución homogénea es $c(-1)^n$ y al buscar una particular de la forma $k2^n$ encontramos $k=1/3$. Luego $b_n = c(-1)^n + 2^n/3$ y como $b_1=-c+2/3=1$ resulta que $c=-1/3$. Esto significa que $b_n = (2^n-(-1)^n)/3$ y que $b_{99}=(2^{99}+1)/3$. De esta manera obtenemos la respuesta $D$.

En la última clase de consultas hubo un estudiante que ha planteado una manera alternativa, que consiste en lleva a palabras binarias poniendo $+1$ si nos movemos en un sentido o $-1$ si nos movemos en sentido contrario. Hay que contar las palabras de largo cuya suma es de la forma $3k+1$ para algún entero $k$. Es un modo alternativo.

En términos probabilísticos, si te tomas paseos al azar en el triángulo vas a notar que, a medida que la longitud de los caminos crecen al infinito, un tercio de los caminos van a terminar en cada vértice. Entonces sabemos que asintóticamente la sucesión $b_n$ crece como $2^n/3$. El largo impar "favorece" a terminar en $b$ y el par "desfavorece"; de ahí que tenemos los $+1/3$ y $-1/3$ sumando y restando en la solución de la recurrencia. Esto es un enfoque "intuitivo" hacia la solución.

Cordiales saludos,
Pablo.