Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (Protected "2024 AMC 8 Problems/Problem 23": Excessive spamming ([Edit=Allow only administrators] (expires 17:00, 25 January 2024 (UTC)) [Move=Allow only administrators] (expires 17:00, 25 January 2024 (UTC))))
(→‎Solution 1)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
==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 equivalent to finding <math>f(5000-2000, 8000-3000)=f(3000, 5000)</math> times. 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 <math>1000f(3, 5).</math> 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>7000.</math>

Revision as of 15:51, 25 January 2024

Problem

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 equivalent to finding $f(5000-2000, 8000-3000)=f(3000, 5000)$ times. 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 $7000.$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AMC_8_Problems/Problem_23&oldid=212829"