2024 AIME I Problems/Problem 6

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, as in the examples shown below.

$[asy] size(10cm); usepackage("tikz");label("\begin{tikzpicture}[scale=.5]\draw(0,0)grid(8,8);\draw[line width=2,red](0,0)--(2,0)--(2,3)--(5,3)--(5,8)--(8,8);\end{tikzpicture}",origin); label("\begin{tikzpicture}[scale=.5]\draw(0,0)grid(8,8);\draw[line width=2,red](0,0)--(0,3)--(3,3)--(3,5)--(8,5)--(8,8);\end{tikzpicture}",E); [/asy]$

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

Solution 4

Starting at the origin, you can either first go up or to the right. If you go up first, you will end on the side opposite to it (the right side) and if you go right first, you will end up on the top. It can then be observed that if you choose the turning points in the middle $7$ x $7$ grid, that will automatically determine your start and ending points. For example, in the diagram if you choose the point $(3,2)$ and $(5,3)$ , you must first move three up or two right, determining your first point, and move 5 up or 3 right, determining your final point. Knowing this is helpful because if we first move anywhere horizontally, we have $7$ points on each column to choose from and starting from left to right, we have $6,5,4,3,2,1$ points on that row to choose from. This gives us $7(6)+7(5)+7(4)+7(3)+7(2)+7(1)$ which simplifies to $7\cdot21$ . The vertical case is symmetrical so we have $7\cdot21\cdot2 = \boxed{294}$

~KEVIN_LIU

2024 AIME I (Problems • Answer Key • Resources)
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

Page

Toolbox

Search