2024 AMC 8 Problems/Problem 23

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?

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)--(-1,-1),gray(.9));
draw((0,5)--(0,-1),gray(.9));
draw((1,5)--(1,-1),gray(.9));
draw((2,5)--(2,-1),gray(.9));
draw((3,5)--(3,-1),gray(.9));
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));


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, grey(.8));


 (Error making remote request. Unknown error_msg)

Fast Solution (2 minutes) AND generalized formula by MegaMath

https://www.youtube.com/watch?v=L2m5U6x-_-8

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)

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.