[sxemi]

Sean \( a \) y \( b \) dos vértices colgantes (o sea vértices de grado \( 1 \)) cualesquiera del bipartito completo \( K_{(1,4)} \). Hallar la cantidad de caminos de largo \( 100 \) que inician en \( a \) y terminan en \( b \).

A) \( 2^{96} \).
B) \( 2^{97} \).
C) \( 2^{98} \).
D) \( 2^{99} \).
E) \( 2^{100} \).

El grafo lo visualizo y entiendo lo que me pide la letra, pero no logro hacer una sucesión o ecuación general para llegar a la respuesta correcta (opción C).
Mensaje corregido desde la administración.

Gracias manooooh.

[manooooh]

Hola sxemi, bienvenido al foro!!

Recuerda leer y seguir las reglas del mismo así como el tutorial del \( \mathrm\LaTeX \) para escribir las fórmulas matemáticas correctamente.

Está prohibido subir imágenes que reemplacen expresiones matemáticas, y las que se puedan deben insertarse explícitamente en el mensaje. Más información aquí.

https://imgur.com/8vurcCS

Transcribo el enunciado:

Sean \( a \) y \( b \) dos vértices colgantes (o sea vértices de grado \( 1 \)) cualesquiera del bipartito completo \( K_{(1,4)} \). Hallar la cantidad de caminos de largo \( 100 \) que inician en \( a \) y terminan en \( b \).

A) \( 2^{96} \).
B) \( 2^{97} \).
C) \( 2^{98} \).
D) \( 2^{99} \).
E) \( 2^{100} \).

Saludos

[Luis Fuentes]

Hola

Sean \( a \) y \( b \) dos vértices colgantes (o sea vértices de grado \( 1 \)) cualesquiera del bipartito completo \( K_{(1,4)} \). Hallar la cantidad de caminos de largo \( 100 \) que inician en \( a \) y terminan en \( b \).

A) \( 2^{96} \).
B) \( 2^{97} \).
C) \( 2^{98} \).
D) \( 2^{99} \).
E) \( 2^{100} \).

El grafo lo visualizo y entiendo lo que me pide la letra, pero no logro hacer una sucesión o ecuación general para llegar a la respuesta correcta (opción C).

El grafo es este.



Está claro que un camino de \( A \) a \( B \) comienza con la arista \( A\to P \) y termina con la \( P\to B \). Para las \( 98 \) intermedias siempre vamos de \( P \) a uno de los cuatro puntos de abajo y después de vuelta de ese mismo punto a \( P \); por tanto en cada uno de esos \( 98/2 \) pares de aristas (la misma en direcciones opuestas), podemos elegir \( 4 \) opciones (una por cada uno de los cuatro vértices inferiores):

\( 4^{98/2}=2^{98} \)

Saludos.

[sxemi]

Está claro que un camino de \( A \) a \( B \) comienza con la arista \( A\to P \) y termina con la \( P\to B \). Para las \( 98 \) intermedias siempre vamos de \( P \) a uno de los cuatro puntos de abajo y después de vuelta de ese mismo punto a \( P \); por tanto en cada uno de esos \( 98/2 \) pares de aristas (la misma en direcciones opuestas), podemos elegir \( 4 \) opciones (una por cada uno de los cuatro vértices inferiores):

\( 4^{98/2}=2^{98} \)

Buenas, no entiendo cómo hago para llegar a que son \( 98 \) las intermedias (obviando que lo sé porque la solución lo dice).

[Luis Fuentes]

Hola

Buenas, no entiendo cómo hago para llegar a que son \( 98 \) las intermedias (obviando que lo sé porque la solución lo dice).

No acabo de entender tu duda. Enumero ciertas afirmaciones; indica cuál no ves clara:

1) Si el camino va de \( A \) a \( B \), necesariamente la primera arista es \( AP \) y la última \( PB \).

2) Por tanto entre la primera y la última quedan \( 100-2=98 \) aristas, ya  que en total el camino tiene que tener longitud \( 100 \).

3) Una vez que estamos en \( P \) para continuar el camino podemos hacer \( PA,PB,PC \) ó \( PD \) pero después necesariamente hay que regresar en el siguiente tramo a \( P \).

4) En otras palabras siempre hacemos uno de los siguientes pares de tramos seguidos:

\( PA,AP \) ó \( PB,BP \) ó \( PC,CP \) ó \( PD,DP \)

5) Por tanto los \( 98 \) pasos intermedios se dividen en \( 98/2 \) parejas, cada una de las cuales pueden ser una de la cuatro indicadas en (4). Por eso el número de posibles caminos es:

\( 4^{98/2} \)

Saludos.   

[sxemi]

Ahhh ahí lo entendí, gracias.