2024 AMC 8

Complete problem set with solutions and individual problem pages

Problem 23 Hard

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?

  • A.

    6000

  • B.

    6500

  • C.

    7000

  • D.

    7500

  • E.

    8000

Answer:C

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{\textbf{(C)}7000}. Alternatively, f(3, 5) can be found by drawing an accurate diagram, leaving you with the same answer.

Related Problems
Problem 21 2024 AMC 8
Problem 22 2024 AMC 8
Problem 24 2024 AMC 8
Problem 25 2024 AMC 8
Think Academy Powered by ChatGPT