Difference between revisions of "2024 AMC 8 Problems/Problem 23"
Countmath1 (talk | contribs) (→Solution 1) |
Countmath1 (talk | contribs) m (→Proof of This Claim) |
||
Line 47: | Line 47: | ||
==Proof of This Claim== | ==Proof of This Claim== | ||
− | \textbf{Lemma 1 for Problem 23:}\\ | + | <math>\textbf{Lemma 1 for Problem 23:}</math>\\ |
Let <math>p</math> and <math>q</math> be relatively prime positive integers. When a <math>p\times q</math> rectangle is split up into <math>pq</math> unit squares, exactly <math>p + q - 1</math> unit squares are crossed by the diagonal of this rectangle. | Let <math>p</math> and <math>q</math> be relatively prime positive integers. When a <math>p\times q</math> rectangle is split up into <math>pq</math> unit squares, exactly <math>p + q - 1</math> unit squares are crossed by the diagonal of this rectangle. | ||
Line 56: | Line 56: | ||
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 <math>p-1</math> horizontal lines and <math>q-1</math> vertical lines, so there are <math>p + q - 2</math> total lines crossed by the diagonal. This doesn't include the square in the bottom left corner, crossed initially. Therefore, there are <math>p + q-2 + 1 = p + q - 1</math> unit squares crossed by the diagonal and our claim is proven. | 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 <math>p-1</math> horizontal lines and <math>q-1</math> vertical lines, so there are <math>p + q - 2</math> total lines crossed by the diagonal. This doesn't include the square in the bottom left corner, crossed initially. Therefore, there are <math>p + q-2 + 1 = p + q - 1</math> unit squares crossed by the diagonal and our claim is proven. | ||
− | \textbf{Lemma 2 for Problem 23:}\\ | + | <math>\textbf{Lemma 2 for Problem 23:}</math>\\ |
Let <math>p</math> and <math>q</math> be positive integers. When a <math>p\times q</math> rectangle is split up into <math>pq</math> units squares, exactly <math>p + q - \gcd(p, q)</math> unit squares are crossed by the diagonal of this rectangle. | Let <math>p</math> and <math>q</math> be positive integers. When a <math>p\times q</math> rectangle is split up into <math>pq</math> units squares, exactly <math>p + q - \gcd(p, q)</math> unit squares are crossed by the diagonal of this rectangle. | ||
Revision as of 22:45, 26 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.