Difference between revisions of "2024 AIME I Problems/Problem 6"
m |
|||
| Line 2: | Line 2: | ||
Consider the paths of length <math>16</math> that follow the lines from the lower left corner to the upper right corner on an <math>8 \times 8</math> grid. Find the number of such paths that change direction exactly four times. | Consider the paths of length <math>16</math> that follow the lines from the lower left corner to the upper right corner on an <math>8 \times 8</math> grid. Find the number of such paths that change direction exactly four times. | ||
| − | ==Solution== | + | ==Solution 1== |
We divide the path into eight “<math>R</math>” movements and eight “<math>U</math>” movements. Five sections of alternative <math>RURUR</math> or <math>URURU</math> are necessary in order to make four “turns.” We use the first case and multiply by <math>2</math>. | We divide the path into eight “<math>R</math>” movements and eight “<math>U</math>” movements. Five sections of alternative <math>RURUR</math> or <math>URURU</math> are necessary in order to make four “turns.” We use the first case and multiply by <math>2</math>. | ||
| Line 15: | Line 15: | ||
~eevee9406 | ~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 <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> | ||
| + | |||
| + | ~alexanderruan | ||
==See also== | ==See also== | ||
{{AIME box|year=2024|n=I|num-b=5|num-a=7}} | {{AIME box|year=2024|n=I|num-b=5|num-a=7}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Revision as of 19:43, 2 February 2024
Contents
Problem
Consider the paths of length 
that follow the lines from the lower left corner to the upper right corner on an 
grid. Find the number of such paths that change direction exactly four times.
Solution 1
We divide the path into eight “
” movements and eight “
” movements. Five sections of alternative 
or 
are necessary in order to make four “turns.” We use the first case and multiply by 
.
For , we have seven ordered pairs of positive integers 
such that 
.
For , we subtract 
from each section (to make the minimum stars of each section 
) and we use Stars and Bars to get 
.
Thus our answer is 
.
~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 
ways to choose when it will go up in the middle of the path and there are 
to choose the two places it will go right. Thus, there are 
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 
~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. 
