Difference between revisions of "2024 AMC 8 Problems/Problem 23"
Countmath1 (talk | contribs) m (→Proof of This Claim) |
Dreamer1297 (talk | contribs) (→Problem) |
||
Line 4: | Line 4: | ||
<asy> | <asy> | ||
− | + | filldraw((0,4)--(1,4)--(1,3)--(0,3)--cycle, gray(.75), gray(.8)+linewidth(1)); | |
− | + | filldraw((0,3)--(1,3)--(1,2)--(0,2)--cycle, gray(.75), gray(.8)+linewidth(1)); | |
− | + | filldraw((1,2)--(2,2)--(2,1)--(1,1)--cycle, gray(.75), gray(.8)+linewidth(1)); | |
− | + | filldraw((1,1)--(2,1)--(2,0)--(1,0)--cycle, gray(.75), gray(.8)+linewidth(1)); | |
− | |||
− | |||
− | |||
− | draw((-1,5)--(5, 5),gray(. | + | |
− | draw((-1,4)--(5,4),gray(. | + | draw((-1,5)--(-1,-1),gray(.9)); |
− | draw((-1,3)--(5,3),gray(. | + | draw((0,5)--(0,-1),gray(.9)); |
− | draw((-1,2)--(5,2),gray(. | + | draw((1,5)--(1,-1),gray(.9)); |
− | draw((-1,1)--(5,1),gray(. | + | draw((2,5)--(2,-1),gray(.9)); |
− | draw((-1,0)--(5,0),gray(. | + | draw((3,5)--(3,-1),gray(.9)); |
− | draw((-1,-1)--(5,-1),gray(. | + | draw((4,5)--(4,-1),gray(.9)); |
+ | draw((5,5)--(5,-1),gray(.9)); | ||
+ | |||
+ | draw((-1,5)--(5, 5),gray(.9)); | ||
+ | draw((-1,4)--(5,4),gray(.9)); | ||
+ | draw((-1,3)--(5,3),gray(.9)); | ||
+ | draw((-1,2)--(5,2),gray(.9)); | ||
+ | draw((-1,1)--(5,1),gray(.9)); | ||
+ | draw((-1,0)--(5,0),gray(.9)); | ||
+ | draw((-1,-1)--(5,-1),gray(.9)); | ||
Line 31: | Line 37: | ||
draw((-1,0) -- (5,0), arrow=Arrow); | draw((-1,0) -- (5,0), arrow=Arrow); | ||
draw((0,-1) -- (0,5), arrow=Arrow); | draw((0,-1) -- (0,5), arrow=Arrow); | ||
− | |||
− | |||
</asy> | </asy> |
Revision as of 02:44, 27 January 2024
Contents
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.
\textbf{Proof:}
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)
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://www.youtube.com/watch?v=dqqAk-Cd_5M
~Math-X
Video Solution 2 by OmegaLearn.org
Video Solution by SpreadTheMathLove
https://www.youtube.com/watch?v=x8Zo7QOB-us
Video Solution by CosineMethod [🔥Fast and Easy🔥]
https://www.youtube.com/watch?v=w8zha2ijVQQ
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.