2024 AMC 8 Problems/Problem 23

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?


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--black);
filldraw((0,3)--(1,3)--(1,2)--(0,2)--cycle--black);



 (Error making remote request. Unknown error_msg)

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 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.