2024 AIME I Problems/Problem 6

Revision as of 19:47, 2 February 2024 by Northstar47 (talk | contribs)

Problem

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.

Solution 1

We divide the path into eight “$R$” movements and eight “$U$” movements. Five sections of alternative $RURUR$ or $URURU$ are necessary in order to make four “turns.” We use the first case and multiply by $2$.


For $U$, we have seven ordered pairs of positive integers $(a,b)$ such that $a+b=8$.

For $R$, we subtract $1$ from each section (to make the minimum stars of each section $0$) and we use Stars and Bars to get ${7 \choose 5}=21$.


Thus our answer is $7\cdot21\cdot2=\boxed{294}$.

~eevee9406

Solution 2

The path can either start by going up or start by going right. Suppose it starts by going up. After a while, it will turn to the right. Then, it will go up. After that, it will go right again. There are $7$ ways to choose when it will go up in the middle of the path and there are $\binom{7}{2}=21$ to choose the two places it will go right. Thus, there are $7\cdot21=147$ ways to create a path that starts by going up. By symmetry, this is the same as the number of paths that start by going right, so the answer is $147\cdot2=\boxed{294}$

~alexanderruan

Solution 3

Notice that the $RURUR$ case and the $URURU$ case is symmetrical. WLOG, let's consider the RURUR case.

Now notice that there is a one-to-one correspondence between this problem and the number of ways to distribute 8 balls into 3 boxes and also 8 other balls into 2 other boxes, such that each box has a nonzero amount of balls.

There are ${8+2-3 \choose 2}$ ways for the first part, and ${8+1-2 \choose 1}$ ways for the second part, by stars and bars.

The answer is $2\cdot {7 \choose 2} \cdot {7 \choose 1} = \boxed{294}$.

~northstar47

Feel free to edit this solution

See also

2024 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 5
Followed by
Problem 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png