¿Cuántos caminos hay de A a B que no visiten dos veces el mismo vértice?
(A) 8
(B) 16
(C) 20
(D) 24
(E) 32
Respuestas
¿Demasiados anuncios?
Inicialmente, vamos a contar sólo con la mitad superior. Número de caminos entre $AC$ son $4$ es decir, $\implies APC,ApC,ApPC,APpC$ .
Hay un número similar de caminos entre $CB$ . Así, para cada camino entre $AC$ , hay un camino hacia $CB. $ . Por lo tanto, el número total de caminos es $4*4=16$ .
Hay números idénticos en la mitad inferior.
Por lo tanto, el número total de rutas es $16*2=32$
Rohan Shinde
Puntos
8
Ahora bien, aquí el número de caminos para llegar de A al punto 1 son 4, que se pueden contar manualmente. Ahora, desde el punto 1 también hay 4 caminos para llegar al punto B. Pero estos dos casos son independientes entre sí, por lo tanto, por la regla de la multiplicación en la combinatoria tenemos el número de caminos de A a B en la parte superior como $4*4=16$ .
Del mismo modo, en la parte inferior habría 16 de ellos.
Por lo tanto, la respuesta sería $$16+16=32$$
Farrukh Ataev
Puntos
21
Hay dos trayectorias globales: norte y sur. Cada trayectoria global se compone de $4$ triángulos conectados. Para cada triángulo hay dos caminos desde un vértice a cada uno de los otros dos vértices. Así que el número total de caminos: $$2×(2×2×2×2)=32.$$ Eso es, $2$ tiempos de trayectorias globales $4$ caminos locales de $2$ cada uno.
David K
Puntos
19172
Para resolver este tipo de problemas en general, busque restricciones que le permitan dividir el problema en subproblemas más sencillos.
Los puntos $A$ y $B$ y los dos puntos medios de los bordes superior e inferior del gran cuadrado son "cuellos de botella". El camino puede cruzar de una de las grandes regiones triangulares a otra a través de uno de estos puntos, pero no puede regresar a través de ese punto.
Esto significa que si tu primer movimiento es hacia la mitad superior de la figura no puedes llegar a la mitad inferior de la figura a través de $A,$ por lo que la única forma de llegar a $B$ es a través de la mitad superior de la figura. Al llegar a $B$ tienes que parar (no entrar en la mitad inferior de la figura), porque si dejas $B$ no puedes volver (ya que sería una segunda visita a $B$ ).
Así que tienes que usar la mitad superior o la inferior, pero no puedes hacer ningún camino que tenga puntos en ambas mitades.
Además, una vez que llegue al punto medio de la mitad superior (o inferior), no podrá volver a la parte de la figura de la izquierda.
Esto divide el problema en subproblemas discretos:
- Cómo elegir la mitad superior o inferior.
- Cómo llegar desde $A$ hasta el punto medio.
- Cómo llegar desde el punto medio hasta $B.$
- Cómo las soluciones a todos los demás subproblemas se combinan en la solución del problema completo.
Cada uno de estos subproblemas es mucho más fácil que el problema completo. Otras respuestas muestran cómo se aplica este método a este problema concreto.
