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

Pista pequeña:

Los saltos hacia la derecha son $+1$ y $+2$ que suman $4,$ así que como multiconjunto son $\{1,1,1,1\},$ $\{1,1,2\},$ o $\{2,2\},$ y lo mismo para los saltos hacia arriba

The rightward jumps are $+1$ s and $+2$ s summing to $4,$ so as a multiset they are $\{1,1,1,1\},$ $\{1,1,2\},$ or $\{2,2\},$ and likewise for the upward jumps

Pista grande:

Para cada par de multiconjuntos, el número de maneras de ordenar todos los saltos es un coeficiente multinomial; suma los nueve casos

For each pair of multisets, the number of ways to order all the jumps is a multinomial coefficient; add up the nine cases

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, \\ &\quad \frac{6!}{4!\,2!} = 15, \end{aligned}$ $\begin{aligned} &\frac{6!}{2!\,2!} = 180, \\ &\quad \frac{5!}{2!\,2!} = 30, \\ &\quad \binom{4}{2} = 6. \end{aligned}$ Los valores $105,$ $15,$ y $30$ aparecen dos veces cada uno.

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, \\ &\quad \frac{6!}{4!\,2!} = 15, \end{aligned}$ $\begin{aligned} &\frac{6!}{2!\,2!} = 180, \\ &\quad \frac{5!}{2!\,2!} = 30, \\ &\quad \binom{4}{2} = 6. \end{aligned}$ The values $105,$ $15,$ and $30$ each occur twice.

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

Pista pequeña:

Pista grande:

Solución:

El Problema 8 en otros años