Difference between revisions of "2024 AMC 8 Problems/Problem 23"
m (→Solution 1) |
m (→Problem) |
||
| Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
| + | Rodrigo is drawing lines on the coordinate plane, and counting how many unit squares they go through. He draws a line with endpoints <math>(2000,3000)</math> and <math>(5000,8000).</math> How many unit squares does this segment go through? | ||
| + | |||
==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> | 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> | ||
~BS2012 | ~BS2012 | ||
Revision as of 16:21, 25 January 2024
Problem
Rodrigo is drawing lines on the coordinate plane, and counting how many unit squares they go through. He draws a line with endpoints 
and 
How many unit squares does this segment go through?
Solution 1
Let 
be the number of cells the line segment from 
to 
passes through. The problem is then equivalent to finding ![\[f(5000-2000, 8000-3000)=f(3000, 5000).\]](http://latex.artofproblemsolving.com/2/3/3/233aea4231046445b3386df8788ad35801395647.png)
Sometimes the segment passes through lattice points in between the endpoints, which happens 
times. This partitions the segment into 
congruent pieces that pass through 
cells, which means the answer is ![\[1000f(3, 5).\]](http://latex.artofproblemsolving.com/4/a/1/4a1d83d64d185b9c9d6c52569e18986cc39a7b09.png)
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 
~BS2012
