2018 AIME II Problem 8

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

Answer

Answer: 556

Concepts:partitions and compositions multiset permutations casework

Difficulty rating: 2920

Small hint:

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

Big hint:

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

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

\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.