Difference between revisions of "2024 AMC 8 Problems/Problem 23"
Mihikamishra (talk | contribs) m (→Solution 2 (The simplify version of Solution 1)) |
|||
(9 intermediate revisions by 5 users not shown) | |||
Line 42: | Line 42: | ||
==Solution 1== | ==Solution 1== | ||
− | Let <math>f(x, y)</math> be the number of cells the line segment from <math>(0, 0)</math> to <math>(x, y)</math> passes through. The problem is then equivalent to finding <cmath>f(5000-2000, 8000-3000)=f(3000, 5000).</cmath> Sometimes the segment passes through lattice points in between the endpoints, which happens <math>\text{gcd}(3000, 5000)-1=999</math> times. This partitions the segment into <math>1000</math> congruent pieces that each pass through <math>f(3, 5)</math> cells, which means the answer is <cmath>1000f(3, 5).</cmath> Note that a new square is entered when the lines pass through one of the lines in the coordinate grid, which for <math>f(3, 5)</math> happens <math>3-1+5-1=6</math> times. Because <math>3</math> and <math>5</math> are relatively prime, no lattice point except for the endpoints intersects the line segment from <math>(0, 0)</math> to <math>(3, 5).</math> This means that including the first cell closest to <math>(0, 0),</math> The segment passes through <math>f(3, 5)=6+1=7</math> cells. Thus, the answer is <math>\boxed{7000}.</math> Alternatively, <math>f(3, 5)</math> can be found by drawing an accurate diagram, leaving you with the same answer. | + | Let <math>f(x, y)</math> be the number of cells the line segment from <math>(0, 0)</math> to <math>(x, y)</math> passes through. The problem is then equivalent to finding <cmath>f(5000-2000, 8000-3000)=f(3000, 5000).</cmath> Sometimes the segment passes through lattice points in between the endpoints, which happens <math>\text{gcd}(3000, 5000)-1=999</math> times. This partitions the segment into <math>1000</math> congruent pieces that each pass through <math>f(3, 5)</math> cells, which means the answer is <cmath>1000f(3, 5).</cmath> Note that a new square is entered when the lines pass through one of the lines in the coordinate grid, which for <math>f(3, 5)</math> happens <math>3-1+5-1=6</math> times. Because <math>3</math> and <math>5</math> are relatively prime, no lattice point except for the endpoints intersects the line segment from <math>(0, 0)</math> to <math>(3, 5).</math> This means that including the first cell closest to <math>(0, 0),</math> The segment passes through <math>f(3, 5)=6+1=7</math> cells. Thus, the answer is <math>\boxed{\textbf{(C)}7000}.</math> Alternatively, <math>f(3, 5)</math> can be found by drawing an accurate diagram, leaving you with the same answer. |
~BS2012 | ~BS2012 | ||
Line 100: | Line 100: | ||
} | } | ||
</asy> | </asy> | ||
− | + | ||
After the diagonal crosses the corner point of a square, the pattern repeats itself with the next one. By Lemma 1, there are <math>\frac{p}{k}+ \frac{q}{k} - 1</math> diagonals crossed in each rectangle. There are <math>k = \gcd (p, q)</math> rectangles, so the number of crossed diagonals in total is | After the diagonal crosses the corner point of a square, the pattern repeats itself with the next one. By Lemma 1, there are <math>\frac{p}{k}+ \frac{q}{k} - 1</math> diagonals crossed in each rectangle. There are <math>k = \gcd (p, q)</math> rectangles, so the number of crossed diagonals in total is | ||
<cmath>k\left( \frac{p}{k}+ \frac{q}{k} - 1 \right) = p + q - \gcd(p,q).</cmath> | <cmath>k\left( \frac{p}{k}+ \frac{q}{k} - 1 \right) = p + q - \gcd(p,q).</cmath> | ||
-Benedict T (countmath1) | -Benedict T (countmath1) | ||
+ | |||
+ | ==Solution 2 (The simplified version of Solution 1)== | ||
+ | Draw a line in the lattice (rulers are allowed on the AMC 8) from <math>(2,3)</math> to <math>(5,8)</math>, and notice that the line crossed 7 blocks in this pattern. Such a pattern is repeated 1000 times between <math>(2000,3000)</math> and <math>(5000,8000)</math>, so the answer is <math>\boxed{\textbf{(C)}7000}</math>. | ||
+ | |||
+ | |||
+ | ~minor edits by mihikamishra | ||
==Video Solution by Power Solve (crystal clear!)== | ==Video Solution by Power Solve (crystal clear!)== | ||
Line 131: | Line 137: | ||
==Fast Solution (2 minutes) AND generalized formula by MegaMath== | ==Fast Solution (2 minutes) AND generalized formula by MegaMath== | ||
https://www.youtube.com/watch?v=L2m5U6x-_-8 | https://www.youtube.com/watch?v=L2m5U6x-_-8 | ||
+ | ==Video Solution by Interstigation== | ||
+ | https://youtu.be/ktzijuZtDas&t=2847 | ||
==See Also== | ==See Also== | ||
{{AMC8 box|year=2024|num-b=22|num-a=24}} | {{AMC8 box|year=2024|num-b=22|num-a=24}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 00:07, 19 August 2024
Contents
- 1 Problem
- 2 Solution 1
- 3 Solution 2 (The simplified version of Solution 1)
- 4 Video Solution by Power Solve (crystal clear!)
- 5 Video Solution 1 by Math-X (First fully understand the problem!!!)
- 6 Video Solution 2 by OmegaLearn.org
- 7 Video Solution by SpreadTheMathLove
- 8 Video Solution by NiuniuMaths (Easy to understand!)
- 9 Video Solution by CosineMethod [🔥Fast and Easy🔥]
- 10 Fast Solution (2 minutes) AND generalized formula by MegaMath
- 11 Video Solution by Interstigation
- 12 See Also
Problem
Rodrigo has a very large sheet of graph paper. First he draws a line segment connecting point to point
and colors the
cells whose interiors intersect the segment, as shown below. Next Rodrigo draws a line segment connecting point
to point
. How many cells will he color this time?
Solution 1
Let be the number of cells the line segment from
to
passes through. The problem is then equivalent to finding
Sometimes the segment passes through lattice points in between the endpoints, which happens
times. This partitions the segment into
congruent pieces that each pass through
cells, which means the answer is
Note that a new square is entered when the lines pass through one of the lines in the coordinate grid, which for
happens
times. Because
and
are relatively prime, no lattice point except for the endpoints intersects the line segment from
to
This means that including the first cell closest to
The segment passes through
cells. Thus, the answer is
Alternatively,
can be found by drawing an accurate diagram, leaving you with the same answer.
~BS2012
Note: A general form for finding is
We subtract
to account for overlapping, when the line segment goes through a lattice point.
~mathkiddus
Proof of This Claim
Let and
be relatively prime positive integers. When a
rectangle is split up into
unit squares, exactly
unit squares are crossed by the diagonal of this rectangle.
First, we claim that the diagonal does not cross the corner of a unit square. \\\\
To prove this claim we proceed by way of contradiction. Plot the rectangle on the Cartesian plane at the vertices The diagonal has endpoints at
, so its slope is
Now, suppose the diagonal goes through the corner point
, where
and
. The slope of this line is
, which must be equal to
implying that
can be reduced, contradicting the fact that
and
are relatively prime. We conclude that no corner points of a grid entry (unit square) are crossed. \\\\
Since no corner points are crossed, each time the diagonal crosses either a horizontal or vertical grid line, exactly one more unit square is touched by the diagonal. There are
horizontal lines and
vertical lines, so there are
total lines crossed by the diagonal. This doesn't include the square in the bottom left corner, crossed initially. Therefore, there are
unit squares crossed by the diagonal and our claim is proven.
Let and
be positive integers. When a
rectangle is split up into
units squares, exactly
unit squares are crossed by the diagonal of this rectangle.
If , then we are done by Lemma 1.
Suppose , i.e
and
, for positive integers
and
. We can then split the
rectangle up into
rectangles, strung together at the diagonal. An example for
is shown below, where two
rectangles are strung together:
After the diagonal crosses the corner point of a square, the pattern repeats itself with the next one. By Lemma 1, there are diagonals crossed in each rectangle. There are
rectangles, so the number of crossed diagonals in total is
-Benedict T (countmath1)
Solution 2 (The simplified version of Solution 1)
Draw a line in the lattice (rulers are allowed on the AMC 8) from to
, and notice that the line crossed 7 blocks in this pattern. Such a pattern is repeated 1000 times between
and
, so the answer is
.
~minor edits by mihikamishra
Video Solution by Power Solve (crystal clear!)
https://www.youtube.com/watch?v=fzgWcEz4K_A
Video Solution 1 by Math-X (First fully understand the problem!!!)
https://youtu.be/BaE00H2SHQM?si=WqyvRC1PRp2FZIL9&t=7181
~Math-X
Video Solution 2 by OmegaLearn.org
Video Solution by SpreadTheMathLove
https://www.youtube.com/watch?v=x8Zo7QOB-us
Video Solution by NiuniuMaths (Easy to understand!)
https://www.youtube.com/watch?v=8XipREuWIHE&t=2s
~NiuniuMaths
Video Solution by CosineMethod [🔥Fast and Easy🔥]
https://www.youtube.com/watch?v=w8zha2ijVQQ
Fast Solution (2 minutes) AND generalized formula by MegaMath
https://www.youtube.com/watch?v=L2m5U6x-_-8
Video Solution by Interstigation
https://youtu.be/ktzijuZtDas&t=2847
See Also
2024 AMC 8 (Problems • Answer Key • Resources) | ||
Preceded by Problem 22 |
Followed by Problem 24 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AJHSME/AMC 8 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.