Difference between revisions of "2024 AMC 8 Problems/Problem 23"
Dreamer1297 (talk | contribs) (→Problem) |
|||
(37 intermediate revisions by 20 users not shown) | |||
Line 4: | Line 4: | ||
<asy> | <asy> | ||
− | + | filldraw((0,4)--(1,4)--(1,3)--(0,3)--cycle, gray(.75), gray(.5)+linewidth(1)); | |
− | + | filldraw((0,3)--(1,3)--(1,2)--(0,2)--cycle, gray(.75), gray(.5)+linewidth(1)); | |
− | + | filldraw((1,2)--(2,2)--(2,1)--(1,1)--cycle, gray(.75), gray(.5)+linewidth(1)); | |
− | + | filldraw((1,1)--(2,1)--(2,0)--(1,0)--cycle, gray(.75), gray(.5)+linewidth(1)); | |
− | |||
− | |||
− | |||
− | draw((-1,5)--(5, 5),gray(. | + | draw((-1,5)--(-1,-1),gray(.9)); |
− | draw((-1,4)--(5,4),gray(. | + | draw((0,5)--(0,-1),gray(.9)); |
− | draw((-1,3)--(5,3),gray(. | + | draw((1,5)--(1,-1),gray(.9)); |
− | draw((-1,2)--(5,2),gray(. | + | draw((2,5)--(2,-1),gray(.9)); |
− | draw((-1,1)--(5,1),gray(. | + | draw((3,5)--(3,-1),gray(.9)); |
− | draw((-1,0)--(5,0),gray(. | + | draw((4,5)--(4,-1),gray(.9)); |
− | draw((-1,-1)--(5,-1),gray(. | + | 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 32: | Line 37: | ||
draw((0,-1) -- (0,5), arrow=Arrow); | draw((0,-1) -- (0,5), arrow=Arrow); | ||
− | + | </asy> | |
− | + | ||
+ | <math>\textbf{(A) } 6000\qquad\textbf{(B) } 6500\qquad\textbf{(C) } 7000\qquad\textbf{(D) } 7500\qquad\textbf{(E) } 8000</math> | ||
+ | |||
+ | ==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{\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 | ||
+ | |||
+ | Note: A general form for finding <math>f(x, y)</math> is <math>x+y-\text{gcd}(x, y).</math> We subtract <math>\text{gcd}(x, y)</math> to account for overlapping, when the line segment goes through a lattice point. | ||
+ | |||
+ | ~mathkiddus | ||
+ | |||
+ | ===Proof of This Claim=== | ||
+ | |||
+ | <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. | ||
+ | |||
+ | |||
+ | <math>\textbf{Proof:}</math> | ||
+ | |||
+ | |||
+ | 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 <math>(0,0),(p,0),(q,p),(0,q).</math> The diagonal has endpoints at <math>(0,0),(q,p)</math>, so its slope is <math>\frac{p}{q}.</math> Now, suppose the diagonal goes through the corner point <math>(a,b)</math>, where <math>a<q</math> and <math>b<p</math>. The slope of this line is <math>\frac{b}{a}</math>, which must be equal to <math>\frac{p}{q},</math> implying that <math>\frac{p}{q}</math> can be reduced, contradicting the fact that <math>p</math> and <math>q</math> 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 <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. | ||
+ | |||
+ | <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. | ||
+ | |||
+ | If <math>\gcd (p,q) = 1</math>, then we are done by Lemma 1. | ||
+ | Suppose <math>\gcd(p,q) = k>1</math>, i.e <math>p = ak</math> and <math>q = bk</math>, for positive integers <math>a</math> and <math>b</math>. We can then split the <math>p\times q</math> rectangle up into <math>k</math> <math>\frac{p}{k} \times \frac{q}{k}</math> rectangles, strung together at the diagonal. An example for <math>(p,q)=(4,6)</math> is shown below, where two <math>2\times 3</math> rectangles are strung together: | ||
+ | <asy> | ||
+ | unitsize(1cm); | ||
+ | draw((0,0)--(6,4),linewidth(1)); | ||
+ | currentpen = linewidth(.5); | ||
+ | for (real i = 0; i <= 6; ++i) { | ||
+ | draw((i, 0)--(i, 4)); | ||
+ | } | ||
+ | for (real i = 0; i < 5; ++i) { | ||
+ | draw((0, i)--(6, i)); | ||
+ | } | ||
+ | |||
+ | currentpen = linewidth(1.5); | ||
+ | for (real i = 0; i <= 3; ++i) { | ||
+ | draw((i, 0)--(i, 2)); | ||
+ | } | ||
+ | for (real i = 0; i <= 2; ++i) { | ||
+ | draw((0, i)--(3, i)); | ||
+ | } | ||
+ | |||
+ | for (real i = 3; i <= 6; ++i) { | ||
+ | draw((i, 2)--(i, 4)); | ||
+ | } | ||
+ | for (real i = 3; i <= 5; ++i) { | ||
+ | draw((3, i-1)--(6, i-1)); | ||
+ | } | ||
</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 | |
− | + | <cmath>k\left( \frac{p}{k}+ \frac{q}{k} - 1 \right) = p + q - \gcd(p,q).</cmath> | |
+ | |||
+ | -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 1 by Math-X (First fully understand the problem!!!)== | ==Video Solution 1 by Math-X (First fully understand the problem!!!)== | ||
− | https:// | + | https://youtu.be/BaE00H2SHQM?si=WqyvRC1PRp2FZIL9&t=7181 |
~Math-X | ~Math-X | ||
+ | |||
+ | ==Video Solution (A Clever Explanation You’ll Get Instantly)== | ||
+ | https://youtu.be/5ZIFnqymdDQ?si=LEqWH6Q7azylK6do&t=3409 | ||
+ | |||
+ | ~hsnacademy | ||
+ | |||
+ | ==Video Solution by Power Solve (crystal clear!)== | ||
+ | https://www.youtube.com/watch?v=fzgWcEz4K_A | ||
+ | |||
==Video Solution 2 by OmegaLearn.org== | ==Video Solution 2 by OmegaLearn.org== | ||
Line 54: | Line 131: | ||
==Video Solution by SpreadTheMathLove== | ==Video Solution by SpreadTheMathLove== | ||
https://www.youtube.com/watch?v=x8Zo7QOB-us | 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 | ||
+ | |||
+ | ==Video Solution by Dr. David== | ||
+ | https://youtu.be/cJpYYEh9m3k | ||
+ | |||
+ | ==See Also== | ||
+ | {{AMC8 box|year=2024|num-b=22|num-a=24}} | ||
+ | {{MAA Notice}} |
Latest revision as of 10:11, 5 October 2024
Contents
- 1 Problem
- 2 Solution 1
- 3 Solution 2 (The simplified version of Solution 1)
- 4 Video Solution 1 by Math-X (First fully understand the problem!!!)
- 5 Video Solution (A Clever Explanation You’ll Get Instantly)
- 6 Video Solution by Power Solve (crystal clear!)
- 7 Video Solution 2 by OmegaLearn.org
- 8 Video Solution by SpreadTheMathLove
- 9 Video Solution by NiuniuMaths (Easy to understand!)
- 10 Video Solution by CosineMethod [🔥Fast and Easy🔥]
- 11 Fast Solution (2 minutes) AND generalized formula by MegaMath
- 12 Video Solution by Interstigation
- 13 Video Solution by Dr. David
- 14 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 1 by Math-X (First fully understand the problem!!!)
https://youtu.be/BaE00H2SHQM?si=WqyvRC1PRp2FZIL9&t=7181
~Math-X
Video Solution (A Clever Explanation You’ll Get Instantly)
https://youtu.be/5ZIFnqymdDQ?si=LEqWH6Q7azylK6do&t=3409
~hsnacademy
Video Solution by Power Solve (crystal clear!)
https://www.youtube.com/watch?v=fzgWcEz4K_A
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
Video Solution by Dr. David
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.