Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 AIME I Problems/Problem 6"
Line 16: Line 16:
  
 
==Solution 2==
 
==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 <math>7</math> ways to choose when it will go up in the middle of the path and there are <math>\binom{7}{2}=21</math> to choose the two places it will go right. Thus, there are <math>7\dot21=147</math> 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 <math>147\dot2=\boxed{294}</math>
+
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 <math>7</math> ways to choose when it will go up in the middle of the path and there are <math>\binom{7}{2}=21</math> to choose the two places it will go right. Thus, there are <math>7\cdot21=147</math> 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 <math>147\cdot2=\boxed{294}</math>
  
 
~alexanderruan
 
~alexanderruan

Revision as of 19:43, 2 February 2024

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

See also

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AIME_I_Problems/Problem_6&oldid=214310"