Question

Una rana está situada en el origen del plano de coordenadas. Desde el punto $(x, y),$ la rana puede saltar a cualquiera de los puntos $(x + 1, y),$ $(x + 2, y),$ $(x, y + 1),$ o $(x, y + 2).$ Halla el número de sucesiones distintas de saltos en las que la rana comienza en $(0, 0)$ y termina en $(4, 4).$

A frog is positioned at the origin in the coordinate plane. From the point $(x, y),$ the frog can jump to any of the points $(x + 1, y),$ $(x + 2, y),$ $(x, y + 1),$ or $(x, y + 2).$ Find the number of distinct sequences of jumps in which the frog begins at $(0, 0)$ and ends at $(4, 4).$

Respuesta

Respuesta: 556

Conceptos:particiones y composiciones permutaciones de multiconjuntos análisis por casos

Nivel de dificultad: 2920

Solución:

Los saltos horizontales son pasos de $1$ o $2$ que suman $4,$ así que como multiconjunto son $\{1,1,1,1\},$ $\{1,1,2\},$ o $\{2,2\},$ y lo mismo ocurre con los saltos verticales. Para cualquier elección de los dos multiconjuntos, todo ordenamiento de los saltos es una sucesión válida, y el número de ordenamientos es el coeficiente multinomial del multiconjunto combinado.

Los nueve casos dan $\begin{aligned} &\binom{8}{4} = 70, \\ &\quad \frac{7!}{4!\,2!} = 105 \text{ (twice)}, \\ &\quad \frac{6!}{4!\,2!} = 15 \text{ (twice)}, \end{aligned}$ $\begin{aligned} &\frac{6!}{2!\,2!} = 180, \\ &\quad \frac{5!}{2!\,2!} = 30 \text{ (twice)}, \\ &\quad \binom{4}{2} = 6. \end{aligned}$

El total es $70 + 2 \cdot 105 + 2 \cdot 15$ $+ 180 + 2 \cdot 30 + 6$ $= 556.$

The horizontal jumps are steps of $1$ or $2$ summing to $4,$ so as a multiset they are $\{1,1,1,1\},$ $\{1,1,2\},$ or $\{2,2\},$ and the same holds for the vertical jumps. For any choice of the two multisets, every ordering of all the jumps is a valid sequence, and the number of orderings is the multinomial coefficient of the combined multiset.

The nine cases give $\begin{aligned} &\binom{8}{4} = 70, \\ &\quad \frac{7!}{4!\,2!} = 105 \text{ (twice)}, \\ &\quad \frac{6!}{4!\,2!} = 15 \text{ (twice)}, \end{aligned}$ $\begin{aligned} &\frac{6!}{2!\,2!} = 180, \\ &\quad \frac{5!}{2!\,2!} = 30 \text{ (twice)}, \\ &\quad \binom{4}{2} = 6. \end{aligned}$

The total is $70 + 2 \cdot 105 + 2 \cdot 15$ $+ 180 + 2 \cdot 30 + 6$ $= 556.$

2018 AIME II Problema 8

Respuesta: 556

Nivel de dificultad: 2920

Solución:

El Problema 8 en otros años