Question

Considera los caminos de longitud $16$ que siguen las líneas desde la esquina inferior izquierda hasta la esquina superior derecha en una cuadrícula $8 \times 8$ . Halla la cantidad de tales caminos que cambian de dirección exactamente cuatro veces, como en los ejemplos que se muestran a continuación.

Consider the paths of length $16$ that follow the lines from the lower left corner to the upper right corner on an $8 \times 8$ grid. Find the number of such paths that change direction exactly four times, as in the examples shown below.

Respuesta

Respuesta: 294

Conceptos:caminos reticulares particiones y composiciones

Nivel de dificultad: 2340

Pista pequeña:

Un camino con exactamente cuatro giros consta de cinco tramos rectos que alternan entre hacia la derecha y hacia arriba

A path with exactly four turns consists of five straight runs that alternate between rightward and upward

Pista grande:

Si el camino empieza hacia la derecha, los tres tramos hacia la derecha y los dos tramos hacia arriba son enteros positivos que suman $8$ cada uno; cuenta las composiciones y luego duplica

If the path starts rightward, the three rightward runs and two upward runs are positive integers summing to $8$ each — count the compositions, then double

Solución:

Un camino que cambia de dirección exactamente cuatro veces consta de cinco tramos rectos máximos, que alternan entre movimientos hacia la derecha y hacia arriba. Si el primer tramo es hacia la derecha, el patrón es $R, U, R, U, R:$ tres tramos hacia la derecha con longitudes positivas que suman $8,$ y dos tramos hacia arriba con longitudes positivas que suman $8.$ Las cantidades de tales composiciones son $\binom{7}{2} = 21$ y $\binom{7}{1} = 7,$ lo que da $21 \cdot 7 = 147$ caminos.

Los caminos que empiezan hacia arriba se cuentan de forma simétrica, otros $147.$ El total es $147 + 147 = 294.$

A path that changes direction exactly four times consists of five maximal straight runs, alternating between rightward and upward moves. If the first run is rightward, the pattern is $R, U, R, U, R:$ three rightward runs with positive lengths summing to $8,$ and two upward runs with positive lengths summing to $8.$ The counts of such compositions are $\binom{7}{2} = 21$ and $\binom{7}{1} = 7,$ giving $21 \cdot 7 = 147$ paths.

Paths starting upward are counted symmetrically, another $147.$ The total is $147 + 147 = 294.$

2024 AIME I Problema 6

Respuesta: 294

Nivel de dificultad: 2340

Pista pequeña:

Pista grande:

Solución:

El Problema 6 en otros años