Difference between revisions of "2024 AMC 8 Problems/Problem 23"

m (Solution 1)
Line 37: Line 37:
  
 
==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 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{7000}.</math> Alternatively, <math>f(3, 5)</math> can be found by drawing an accurate diagram, leaving you with the same answer.
  
 
~BS2012
 
~BS2012

Revision as of 21:06, 26 January 2024

Problem

Rodrigo has a very large sheet of graph paper. First he draws a line segment connecting point $(0,4)$ to point $(2,0)$ and colors the $4$ cells whose interiors intersect the segment, as shown below. Next Rodrigo draws a line segment connecting point $(2000,3000)$ to point $(5000,8000)$. How many cells will he color this time?

[asy]  draw((-1,5)--(-1,-1),gray(.8)); draw((0,5)--(0,-1),gray(.8)); draw((1,5)--(1,-1),gray(.8)); draw((2,5)--(2,-1),gray(.8)); draw((3,5)--(3,-1),gray(.8)); draw((4,5)--(4,-1),gray(.8)); draw((5,5)--(5,-1),gray(.8));  draw((-1,5)--(5, 5),gray(.8)); draw((-1,4)--(5,4),gray(.8)); draw((-1,3)--(5,3),gray(.8)); draw((-1,2)--(5,2),gray(.8)); draw((-1,1)--(5,1),gray(.8)); draw((-1,0)--(5,0),gray(.8)); draw((-1,-1)--(5,-1),gray(.8));   dot((0,4)); label("$(0,4)$",(0,4),NW);  dot((2,0)); label("$(2,0)$",(2,0),SE);  draw((0,4)--(2,0));  draw((-1,0) -- (5,0), arrow=Arrow); draw((0,-1) -- (0,5), arrow=Arrow);  filldraw((0,4)--(1,4)--(1,3)--(0,3)--cycle, gray(.8), gray(.8)+linewidth(1));  [/asy]

Solution 1

Let $f(x, y)$ be the number of cells the line segment from $(0, 0)$ to $(x, y)$ passes through. The problem is then equivalent to finding \[f(5000-2000, 8000-3000)=f(3000, 5000).\] Sometimes the segment passes through lattice points in between the endpoints, which happens $\text{gcd}(3000, 5000)-1=999$ times. This partitions the segment into $1000$ congruent pieces that each pass through $f(3, 5)$ cells, which means the answer is \[1000f(3, 5).\] Note that a new square is entered when the lines pass through one of the lines in the coordinate grid, which for $f(3, 5)$ happens $3-1+5-1=6$ times. Because $3$ and $5$ are relatively prime, no lattice point except for the endpoints intersects the line segment from $(0, 0)$ to $(3, 5).$ This means that including the first cell closest to $(0, 0),$ The segment passes through $f(3, 5)=6+1=7$ cells. Thus, the answer is $\boxed{7000}.$ Alternatively, $f(3, 5)$ can be found by drawing an accurate diagram, leaving you with the same answer.

~BS2012

Note: A general form for finding $f(x, y)$ is $x+y-\text{gcd}(x, y).$ We subtract $\text{gcd}(x, y)$ to account for overlapping, when the line segment goes through a lattice point.

~mathkiddus

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

https://youtu.be/wNymnFQfN_k

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 (ProblemsAnswer KeyResources)
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. AMC logo.png