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 (→‎Proof of This Claim)
 
(29 intermediate revisions by 18 users not shown)
Line 4: Line 4:
 
<asy>
 
<asy>
  
−
draw((-1,5)--(-1,-1),gray(.8));
+
filldraw((0,4)--(1,4)--(1,3)--(0,3)--cycle, gray(.75), gray(.5)+linewidth(1));
−
draw((0,5)--(0,-1),gray(.8));
+
filldraw((0,3)--(1,3)--(1,2)--(0,2)--cycle, gray(.75), gray(.5)+linewidth(1));
−
draw((1,5)--(1,-1),gray(.8));
+
filldraw((1,2)--(2,2)--(2,1)--(1,1)--cycle, gray(.75), gray(.5)+linewidth(1));
−
draw((2,5)--(2,-1),gray(.8));
+
filldraw((1,1)--(2,1)--(2,0)--(1,0)--cycle, gray(.75), gray(.5)+linewidth(1));
−
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,5)--(-1,-1),gray(.9));
−
draw((-1,4)--(5,4),gray(.8));
+
draw((0,5)--(0,-1),gray(.9));
−
draw((-1,3)--(5,3),gray(.8));
+
draw((1,5)--(1,-1),gray(.9));
−
draw((-1,2)--(5,2),gray(.8));
+
draw((2,5)--(2,-1),gray(.9));
−
draw((-1,1)--(5,1),gray(.8));
+
draw((3,5)--(3,-1),gray(.9));
−
draw((-1,0)--(5,0),gray(.8));
+
draw((4,5)--(4,-1),gray(.9));
−
draw((-1,-1)--(5,-1),gray(.8));
+
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));
  
  
Line 32: Line 37:
 
draw((0,-1) -- (0,5), arrow=Arrow);
 
draw((0,-1) -- (0,5), arrow=Arrow);
  
−
filldraw((0,4)--(1,4)--(1,3)--(0,3)--cycle, gray(.8), gray(.8)+linewidth(1));
+
</asy>
  
−
</asy>
+
<math>\textbf{(A) } 6000\qquad\textbf{(B) } 6500\qquad\textbf{(C) } 7000\qquad\textbf{(D) } 7500\qquad\textbf{(E) } 8000</math>
  
 
==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 each 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> Alternatively, <math>f(3, 5)</math> can be found by drawing an accurate diagram, leaving you with the same answer.
+
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 each 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{\textbf{(C)}7000}.</math> Alternatively, <math>f(3, 5)</math> can be found by drawing an accurate diagram, leaving you with the same answer.
  
 
~BS2012
 
~BS2012
Line 45: Line 50:
 
~mathkiddus
 
~mathkiddus
  
−
==Proof of This Claim==
+
===Proof of This Claim===
 +
 
 +
<math>\textbf{Lemma 1 for Problem 23:}</math>
  
−
<math>\textbf{Lemma 1 for Problem 23:}</math>\\
 
 
Let <math>p</math> and <math>q</math> be relatively prime positive integers. When a <math>p\times q</math> rectangle is split up into <math>pq</math> unit squares, exactly <math>p + q - 1</math> unit squares are crossed by the diagonal of this rectangle.  
 
Let <math>p</math> and <math>q</math> be relatively prime positive integers. When a <math>p\times q</math> rectangle is split up into <math>pq</math> unit squares, exactly <math>p + q - 1</math> unit squares are crossed by the diagonal of this rectangle.  
  
  
−
\textbf{Proof:}\\
+
<math>\textbf{Proof:}</math>
 +
 
 +
 
 
First, we claim that the diagonal does not cross the corner of a unit square. \\\\
 
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 <math>(0,0),(p,0),(q,p),(0,q).</math> The diagonal has endpoints at <math>(0,0),(q,p)</math>, so its slope is <math>\frac{p}{q}.</math>  Now, suppose the diagonal goes through the corner point <math>(a,b)</math>, where <math>a<q</math> and <math>b<p</math>. The slope of this line is <math>\frac{b}{a}</math>, which must be equal to <math>\frac{p}{q},</math> implying that <math>\frac{p}{q}</math> can be reduced, contradicting the fact that <math>p</math> and <math>q</math> are relatively prime. We conclude that no corner points of a grid entry (unit square) are crossed. \\\\
 
To prove this claim we proceed by way of contradiction. Plot the rectangle on the Cartesian plane at the vertices <math>(0,0),(p,0),(q,p),(0,q).</math> The diagonal has endpoints at <math>(0,0),(q,p)</math>, so its slope is <math>\frac{p}{q}.</math>  Now, suppose the diagonal goes through the corner point <math>(a,b)</math>, where <math>a<q</math> and <math>b<p</math>. The slope of this line is <math>\frac{b}{a}</math>, which must be equal to <math>\frac{p}{q},</math> implying that <math>\frac{p}{q}</math> can be reduced, contradicting the fact that <math>p</math> and <math>q</math> 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 <math>p-1</math> horizontal lines and <math>q-1</math> vertical lines, so there are <math>p + q - 2</math> total lines crossed by the diagonal. This doesn't include the square in the bottom left corner, crossed initially. Therefore, there are <math>p + q-2 + 1 = p + q - 1</math> unit squares crossed by the diagonal and our claim is proven.
 
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 <math>p-1</math> horizontal lines and <math>q-1</math> vertical lines, so there are <math>p + q - 2</math> total lines crossed by the diagonal. This doesn't include the square in the bottom left corner, crossed initially. Therefore, there are <math>p + q-2 + 1 = p + q - 1</math> unit squares crossed by the diagonal and our claim is proven.
  
−
<math>\textbf{Lemma 2 for Problem 23:}</math>\\
+
<math>\textbf{Lemma 2 for Problem 23:}</math>
 +
 
 +
 
 
Let <math>p</math> and <math>q</math> be positive integers. When a <math>p\times q</math> rectangle is split up into <math>pq</math> units squares, exactly <math>p + q - \gcd(p, q)</math> unit squares are crossed by the diagonal of this rectangle.
 
Let <math>p</math> and <math>q</math> be positive integers. When a <math>p\times q</math> rectangle is split up into <math>pq</math> units squares, exactly <math>p + q - \gcd(p, q)</math> unit squares are crossed by the diagonal of this rectangle.
  
  
−
If <math>\gcd (p,q) = 1</math>, then we are done by Lemma 1. \\\\
+
If <math>\gcd (p,q) = 1</math>, then we are done by Lemma 1.
 +
 
 
Suppose <math>\gcd(p,q) = k>1</math>, i.e <math>p = ak</math> and <math>q = bk</math>, for positive integers <math>a</math> and <math>b</math>. We can then split the <math>p\times q</math> rectangle up into <math>k</math> <math>\frac{p}{k} \times \frac{q}{k}</math> rectangles, strung together at the diagonal. An example for <math>(p,q)=(4,6)</math> is shown below, where two <math>2\times 3</math> rectangles are strung together:  
 
Suppose <math>\gcd(p,q) = k>1</math>, i.e <math>p = ak</math> and <math>q = bk</math>, for positive integers <math>a</math> and <math>b</math>. We can then split the <math>p\times q</math> rectangle up into <math>k</math> <math>\frac{p}{k} \times \frac{q}{k}</math> rectangles, strung together at the diagonal. An example for <math>(p,q)=(4,6)</math> is shown below, where two <math>2\times 3</math> rectangles are strung together:  
  
Line 89: Line 100:
 
}
 
}
 
</asy>
 
</asy>
−
\\\\
+
 
 
After the diagonal crosses the corner point of a square, the pattern repeats itself with the next one. By Lemma 1, there are <math>\frac{p}{k}+ \frac{q}{k} - 1</math> diagonals crossed in each rectangle. There are <math>k = \gcd (p, q)</math> rectangles, so the number of crossed diagonals in total is
 
After the diagonal crosses the corner point of a square, the pattern repeats itself with the next one. By Lemma 1, there are <math>\frac{p}{k}+ \frac{q}{k} - 1</math> diagonals crossed in each rectangle. There are <math>k = \gcd (p, q)</math> rectangles, so the number of crossed diagonals in total is
 
<cmath>k\left( \frac{p}{k}+ \frac{q}{k} - 1 \right) = p + q - \gcd(p,q).</cmath>
 
<cmath>k\left( \frac{p}{k}+ \frac{q}{k} - 1 \right) = p + q - \gcd(p,q).</cmath>
Line 95: Line 106:
 
-Benedict T (countmath1)
 
-Benedict T (countmath1)
  
−
==Video Solution by Power Solve (crystal clear!)==
+
==Solution 2 (The simplified version of Solution 1)==
−
https://www.youtube.com/watch?v=fzgWcEz4K_A
+
Draw a line in the lattice (rulers are allowed on the AMC 8) from <math>(2,3)</math> to <math>(5,8)</math>, and notice that the line crossed 7 blocks in this pattern. Such a pattern is repeated 1000 times between <math>(2000,3000)</math> and <math>(5000,8000)</math>, so the answer is <math>\boxed{\textbf{(C)}7000}</math>.
 +
 
 +
 
 +
~minor edits by mihikamishra
  
 
==Video Solution 1 by Math-X (First fully understand the problem!!!)==
 
==Video Solution 1 by Math-X (First fully understand the problem!!!)==
−
https://www.youtube.com/watch?v=dqqAk-Cd_5M
+
https://youtu.be/BaE00H2SHQM?si=WqyvRC1PRp2FZIL9&t=7181
  
 
~Math-X
 
~Math-X
 +
 +
==Video Solution (A Clever Explanation You’ll Get Instantly)==
 +
https://youtu.be/5ZIFnqymdDQ?si=LEqWH6Q7azylK6do&t=3409
 +
 +
~hsnacademy
 +
 +
==Video Solution by Power Solve (crystal clear!)==
 +
https://www.youtube.com/watch?v=fzgWcEz4K_A
 +
  
 
==Video Solution 2 by OmegaLearn.org==
 
==Video Solution 2 by OmegaLearn.org==
Line 108: Line 131:
 
==Video Solution by SpreadTheMathLove==
 
==Video Solution by SpreadTheMathLove==
 
https://www.youtube.com/watch?v=x8Zo7QOB-us
 
https://www.youtube.com/watch?v=x8Zo7QOB-us
 +
 +
== Video Solution by NiuniuMaths (Easy to understand!) ==
 +
https://www.youtube.com/watch?v=8XipREuWIHE&t=2s
 +
 +
~NiuniuMaths
  
 
== Video Solution by CosineMethod [🔥Fast and Easy🔥]==
 
== Video Solution by CosineMethod [🔥Fast and Easy🔥]==
  
 
https://www.youtube.com/watch?v=w8zha2ijVQQ
 
https://www.youtube.com/watch?v=w8zha2ijVQQ
 +
 +
==Fast Solution (2 minutes) AND generalized formula by MegaMath==
 +
https://www.youtube.com/watch?v=L2m5U6x-_-8
 +
==Video Solution by Interstigation==
 +
https://youtu.be/ktzijuZtDas&t=2847
 +
 +
==Video Solution by Dr. David==
 +
https://youtu.be/cJpYYEh9m3k
 +
 +
==Video Solution by WhyMath==
 +
https://youtu.be/a7rUlwfO5wA
  
 
==See Also==
 
==See Also==
 
{{AMC8 box|year=2024|num-b=22|num-a=24}}
 
{{AMC8 box|year=2024|num-b=22|num-a=24}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 15:05, 9 November 2024

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?

[asy] 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); [/asy]

$\textbf{(A) } 6000\qquad\textbf{(B) } 6500\qquad\textbf{(C) } 7000\qquad\textbf{(D) } 7500\qquad\textbf{(E) } 8000$

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

~BS2012

Note: A general form for finding $f(x, y)$ is $x+y-\text{gcd}(x, y).$ We subtract $\text{gcd}(x, y)$ to account for overlapping, when the line segment goes through a lattice point.

~mathkiddus

Proof of This Claim

$\textbf{Lemma 1 for Problem 23:}$

Let $p$ and $q$ be relatively prime positive integers. When a $p\times q$ rectangle is split up into $pq$ unit squares, exactly $p + q - 1$ unit squares are crossed by the diagonal of this rectangle.


$\textbf{Proof:}$


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 $(0,0),(p,0),(q,p),(0,q).$ The diagonal has endpoints at $(0,0),(q,p)$, so its slope is $\frac{p}{q}.$ Now, suppose the diagonal goes through the corner point $(a,b)$, where $a<q$ and $b<p$. The slope of this line is $\frac{b}{a}$, which must be equal to $\frac{p}{q},$ implying that $\frac{p}{q}$ can be reduced, contradicting the fact that $p$ and $q$ 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 $p-1$ horizontal lines and $q-1$ vertical lines, so there are $p + q - 2$ total lines crossed by the diagonal. This doesn't include the square in the bottom left corner, crossed initially. Therefore, there are $p + q-2 + 1 = p + q - 1$ unit squares crossed by the diagonal and our claim is proven.

$\textbf{Lemma 2 for Problem 23:}$


Let $p$ and $q$ be positive integers. When a $p\times q$ rectangle is split up into $pq$ units squares, exactly $p + q - \gcd(p, q)$ unit squares are crossed by the diagonal of this rectangle.


If $\gcd (p,q) = 1$, then we are done by Lemma 1.

Suppose $\gcd(p,q) = k>1$, i.e $p = ak$ and $q = bk$, for positive integers $a$ and $b$. We can then split the $p\times q$ rectangle up into $k$ $\frac{p}{k} \times \frac{q}{k}$ rectangles, strung together at the diagonal. An example for $(p,q)=(4,6)$ is shown below, where two $2\times 3$ rectangles are strung together:

[asy] unitsize(1cm); draw((0,0)--(6,4),linewidth(1)); currentpen = linewidth(.5); for (real i = 0; i <= 6; ++i) { draw((i, 0)--(i, 4)); } for (real i = 0; i < 5; ++i) { draw((0, i)--(6, i)); } currentpen = linewidth(1.5); for (real i = 0; i <= 3; ++i) { draw((i, 0)--(i, 2)); } for (real i = 0; i <= 2; ++i) { draw((0, i)--(3, i)); } for (real i = 3; i <= 6; ++i) { draw((i, 2)--(i, 4)); } for (real i = 3; i <= 5; ++i) { draw((3, i-1)--(6, i-1)); } [/asy]

After the diagonal crosses the corner point of a square, the pattern repeats itself with the next one. By Lemma 1, there are $\frac{p}{k}+ \frac{q}{k} - 1$ diagonals crossed in each rectangle. There are $k = \gcd (p, q)$ rectangles, so the number of crossed diagonals in total is \[k\left( \frac{p}{k}+ \frac{q}{k} - 1 \right) = p + q - \gcd(p,q).\]

-Benedict T (countmath1)

Solution 2 (The simplified version of Solution 1)

Draw a line in the lattice (rulers are allowed on the AMC 8) from $(2,3)$ to $(5,8)$, and notice that the line crossed 7 blocks in this pattern. Such a pattern is repeated 1000 times between $(2000,3000)$ and $(5000,8000)$, so the answer is $\boxed{\textbf{(C)}7000}$.


~minor edits by mihikamishra

Video Solution 1 by Math-X (First fully understand the problem!!!)

https://youtu.be/BaE00H2SHQM?si=WqyvRC1PRp2FZIL9&t=7181

~Math-X

Video Solution (A Clever Explanation You’ll Get Instantly)

https://youtu.be/5ZIFnqymdDQ?si=LEqWH6Q7azylK6do&t=3409

~hsnacademy

Video Solution by Power Solve (crystal clear!)

https://www.youtube.com/watch?v=fzgWcEz4K_A


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 NiuniuMaths (Easy to understand!)

https://www.youtube.com/watch?v=8XipREuWIHE&t=2s

~NiuniuMaths

Video Solution by CosineMethod [🔥Fast and Easy🔥]

https://www.youtube.com/watch?v=w8zha2ijVQQ

Fast Solution (2 minutes) AND generalized formula by MegaMath

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

Video Solution by Interstigation

https://youtu.be/ktzijuZtDas&t=2847

Video Solution by Dr. David

https://youtu.be/cJpYYEh9m3k

Video Solution by WhyMath

https://youtu.be/a7rUlwfO5wA

See Also

2024 AMC 8 (Problems • Answer Key • Resources)
Preceded by
Problem 22 		Followed by
Problem 24
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AJHSME/AMC 8 Problems and Solutions

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

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