Question

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).$

答案

Solution:

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 $\binom{8}{4} = 70, \quad \frac{7!}{4!\,2!} = 105 \text{ (twice)}, \quad \frac{6!}{4!\,2!} = 15 \text{ (twice)},$ $\frac{6!}{2!\,2!} = 180, \quad \frac{5!}{2!\,2!} = 30 \text{ (twice)}, \quad \binom{4}{2} = 6.$

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

2018 AIME II Problem 8

Solution:

Problem 8 in Other Years