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

Solución:

Un camino que cambia de dirección exactamente cuatro veces consta de cinco tramos rectos maximales, 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

Solución:

El Problema 6 en otros años