Difference between revisions of "2021 AMC 12B Problems/Problem 25"
(→Solution 2) |
|||
(66 intermediate revisions by 22 users not shown) | |||
Line 1: | Line 1: | ||
+ | {{duplicate|[[2021 AMC 10B Problems#Problem 25|2021 AMC 10B #25]] and [[2021 AMC 12B Problems#Problem 25|2021 AMC 12B #25]]}} | ||
+ | |||
==Problem== | ==Problem== | ||
− | Let <math>S</math> be the set of lattice points in the coordinate plane, both of whose coordinates are integers between <math>1</math> and <math>30</math> | + | Let <math>S</math> be the set of lattice points in the coordinate plane, both of whose coordinates are integers between <math>1</math> and <math>30,</math> inclusive. Exactly <math>300</math> points in <math>S</math> lie on or below a line with equation <math>y=mx.</math> The possible values of <math>m</math> lie in an interval of length <math>\frac ab,</math> where <math>a</math> and <math>b</math> are relatively prime positive integers. What is <math>a+b?</math> |
+ | |||
+ | <math>\textbf{(A)} ~31 \qquad \textbf{(B)} ~47 \qquad \textbf{(C)} ~62\qquad \textbf{(D)} ~72 \qquad \textbf{(E)} ~85</math> | ||
+ | |||
+ | ==Solution 1== | ||
+ | |||
+ | First, we find a numerical representation for the number of lattice points in <math>S</math> that are under the line <math>y=mx. </math> For any value of <math>x,</math> the highest lattice point under <math>y=mx</math> is <math>\lfloor mx \rfloor. </math> Because every lattice point from <math>(x, 1)</math> to <math>(x, \lfloor mx \rfloor)</math> is under the line, the total number of lattice points under the line is <math>\sum_{x=1}^{30}(\lfloor mx \rfloor). </math> | ||
+ | |||
+ | |||
+ | Now, we proceed by finding lower and upper bounds for <math>m. </math> To find the lower bound, we start with an approximation. If <math>300</math> lattice points are below the line, then around <math>\frac{1}{3}</math> of the area formed by <math>S</math> is under the line. By using the formula for a triangle's area, we find that when <math>x=30, y \approx 20. </math> Solving for <math>m</math> assuming that <math>(30, 20)</math> is a point on the line, we get <math>m = \frac{2}{3}. </math> Plugging in <math>m</math> to <math>\sum_{x=1}^{30}(\lfloor mx \rfloor), </math> we get: | ||
+ | |||
+ | <cmath>\sum_{x=1}^{30}(\lfloor \frac{2}{3}x \rfloor) = 0 + 1 + 2 + 2 + 3 + \cdots + 18 + 18 + 19 + 20</cmath> | ||
+ | |||
+ | We have a repeat every <math>3</math> values (every time <math>y=\frac{2}{3}x</math> goes through a lattice point). Thus, we can use arithmetic sequences to calculate the value above: | ||
+ | |||
+ | <cmath>\sum_{x=1}^{30}(\lfloor \frac{2}{3}x \rfloor) = 0 + 1 + 2 + 2 + 3 + \cdots + 18 + 18 + 19 + 20</cmath><cmath>=\frac{20(21)}{2} + 2 + 4 + 6 + \cdots + 18 </cmath><cmath>=210 + \frac{20}{2}\cdot 9</cmath><cmath>=300</cmath> | ||
+ | |||
+ | This means that <math>\frac{2}{3}</math> is a possible value of <math>m. </math> Furthermore, it is the lower bound for <math>m. </math> This is because <math>y=\frac{2}{3}x</math> goes through many points (such as <math>(21, 14)</math>). If <math>m</math> was lower, <math>y=mx</math> would no longer go through some of these points, and there would be less than <math>300</math> lattice points under it. | ||
+ | |||
+ | Now, we find an upper bound for <math>m. </math> Imagine increasing <math>m</math> slowly and rotating the line <math>y=mx, </math> starting from the lower bound of <math>m=\frac{2}{3}. </math>The upper bound for <math>m</math> occurs when <math>y=mx</math> intersects a lattice point again (look at this problem to get a better idea of what's happening: https://artofproblemsolving.com/wiki/index.php/2011_AMC_10B_Problems/Problem_24). | ||
+ | |||
+ | In other words, we are looking for the first <math>m > \frac{2}{3}</math> that is expressible as a ratio of positive integers <math>\frac{p}{q}</math> with <math>q \le 30. </math> For each <math>q=1,\dots,30</math>, the smallest multiple of <math>\frac{1}{q}</math> which exceeds <math>\frac{2}{3}</math> is <math>1, \frac{2}{2}, \frac{3}{3}, \frac{3}{4}, \frac{4}{5}, \cdots , \frac{19}{27}, \frac{19}{28}, \frac{20}{29}, \frac{21}{30}</math> respectively, and the smallest of these is <math>\frac{19}{28}. </math> | ||
+ | |||
+ | Alternatively, see the method of finding upper bounds in solution 2. | ||
+ | |||
+ | The lower bound is <math>\frac{2}{3}</math> and the upper bound is <math>\frac{19}{28}. </math> Their difference is <math>\frac{1}{84}, </math> so the answer is <math>1 + 84 = \boxed{85}. </math> | ||
+ | |||
+ | ~JimY | ||
+ | ~Minor edits by sl_hc | ||
+ | |||
+ | An alternative would be using Farey fractions and the mediant theorem to find the upper bound. <math>\frac{2}{3}</math> and <math>\frac{7}{10}</math> gives <math>\frac{9}{13},</math> and so on using Farey addition. | ||
+ | |||
+ | An alternative approach with the same methodology can be done using Pick's Theorem. Wikipedia page: https://en.wikipedia.org/wiki/Pick%27s_theorem. It's a formula to find the number of lattice points strictly inside a polygon. Approximation of the lower bound is still necessary. | ||
+ | |||
+ | ==Solution 2== | ||
+ | Based on area ratios between a square of side length <math>30</math> and a triangle with base <math>30</math>, we estimate that the slope <math>m</math> of the line we want is around <math>\frac{2}{3}</math>. There are a total of <math>30</math> integer coordinates in the desired range for each axis, giving a total of <math>900</math> lattice points, so we see if there are <math>900 \cdot \frac{2}{3} = 600</math> points above the line, <math>y=\frac{2}{3}x</math>. | ||
+ | |||
+ | Counting the number of lattice points with <math>x=1</math> above the line, the number of lattice points with <math>x=2</math> above the line, and so on, we find that the total number of lattice points above the line is <math>30+29+28+28+27+26+26 \ldots+ 10</math>, with the even integers repeating every third term. We see that the average of the <math>30</math> terms is <math>20</math>, which means that exactly <math>20 \cdot 30 = 600</math> lattice points above the line as desired. This gives a lower bound because any decrease in the slope of the line would cause points that were already on the line to shift to being above it. | ||
+ | |||
+ | To find the upper bound, notice that each lattice point less than <math>1</math> unit above the line is either <math>\frac{1}{3}</math> or <math>\frac{2}{3}</math> above. Since the slope through a point is the y-coordinate divided by the x-coordinate, a shift in the slope will increase the y-value of the higher x-coordinates more than the y-value of the lower x-coordinates. So, we turn our attention to <math>x=28, 29, 30</math> for which the line <math>y=\frac{2}{3}x</math> intersects at <math>y= \frac{56}{3}, \frac{58}{3}, 20</math>. The point <math>(30,20)</math> is already counted, and we can clearly see that if we slowly increase the slope of the line, we will first hit the point <math>(28,19)</math> since <math>(28, \frac{56}{3})</math> is the closest to it. The equation of the line which goes through both the origin and <math>(28,19)</math> is <math>y=\frac{19}{28}x</math>. This gives an upper bound of <math>m=\frac{19}{28}</math>. | ||
+ | |||
+ | Taking the upper bound of <math>m</math> and subtracting the lower bound yields <math>\frac{19}{28}-\frac{2}{3}=\frac{1}{84}</math>. The answer is therefore <math>1+84=</math> <math>\boxed{\textbf{(E)} ~85}</math>. | ||
+ | |||
+ | ~theAJL ~Minor edits by Eric_Zang | ||
+ | ===Diagram=== | ||
+ | <asy> | ||
+ | /* Created by Brendanb4321 */ | ||
+ | import graph; | ||
+ | size(16cm); | ||
+ | defaultpen(fontsize(9pt)); | ||
+ | xaxis(0,30,Ticks(1.0)); | ||
+ | yaxis(0,25,Ticks(1.0)); | ||
+ | |||
+ | draw((0,0)--(30,20)); | ||
+ | draw((0,0)--(30,30/28*19), dotted); | ||
+ | for (int i = 1; i<=30; ++i) | ||
+ | { | ||
+ | for (int j = 1; j<=2/3*i+1; ++j) | ||
+ | { | ||
+ | dot((i,j)); | ||
+ | } | ||
+ | } | ||
+ | dot((28,19), red); | ||
+ | label("$m=2/3$", (32,20)); | ||
+ | label("$m=19/28$", (32.3,20.8)); | ||
+ | </asy> | ||
+ | |||
+ | ==Solution 3== | ||
+ | As the procedure shown in the Solution 1, the lower bound of <math>m </math> is <math> \frac{2}{3}. </math> | ||
+ | Here I give a more logic way to show how to find the upper bound of <math>m. </math> | ||
+ | Denote <math>N=\sum_{x=1}^{30}(\lfloor mx \rfloor) </math> as the number of lattice points in <math>S</math>. | ||
+ | |||
+ | <math>N = \lfloor m \rfloor+\lfloor 2m \rfloor+\lfloor 3m \rfloor+\cdots+\lfloor 30m \rfloor = 300 .</math> | ||
+ | |||
+ | Let <math>m = \frac{2}{3}+k </math>. for <math>\forall x_{i}\le 30, x\in N^{*}, \lfloor mx_{i} \rfloor = \lfloor \frac{2}{3}x+xk \rfloor. </math> | ||
+ | |||
+ | Our target is finding the minimum value of <math>k</math> which can increase one unit of <math>\lfloor mx_{i} \rfloor .</math> | ||
+ | |||
+ | Notice that: | ||
+ | |||
+ | When <math> x_{i} = 3n, \lfloor mx_{i} \rfloor = \lfloor 2n+(3n)k \rfloor </math> We don't have to discuss this case. | ||
+ | |||
+ | When <math> x_{i} = 3n+1, \lfloor mx_{i} \rfloor = \lfloor 2n+\frac{2}{3}+(3n+1)k \rfloor, k_{min1}=\frac{1}{3(3n+1)}. </math> | ||
+ | |||
+ | When <math> x_{i} = 3n+2, \lfloor mx_{i} \rfloor = \lfloor 2n+1+\frac{1}{3}+(3n+2)k \rfloor, k_{min2}=\frac{2}{3(3n+2)}. </math> | ||
+ | |||
+ | Here <math>n\in N^{*}, n \le 9.</math> | ||
+ | |||
+ | Denote <math> k_{min}=min\left \{k_{min1},k_{min2} \right \}. </math> | ||
+ | |||
+ | Obviously <math>k_{min1} </math> and <math>k_{min2}</math> are decreasing. Let's considering the situation when <math>n=9.</math> | ||
+ | |||
+ | <math>k_{min}=min\left\{\frac{1}{84},\frac{2}{87}\right\}=\frac{1}{84}.</math> | ||
+ | |||
+ | This means that the answer is just <math>\frac{1}{84}</math>, so <math>a+b=85</math>. Choose <math>\boxed{E}.</math> | ||
+ | |||
+ | ~PythZhou. | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | It's easier to calculate the number of lattice points inside a rectangle with vertices <math>(0,0)</math>, <math>(p,0)</math>, <math>(p,q)</math>, <math>(0,q)</math>. Those lattice points are divided by the diagonal <math>y = \frac{p}{q} \cdot x</math> into <math>2</math> halves. In this problem the number of lattice points on or below the diagonal and <math>x \ge 1</math> is | ||
+ | <math>\frac{1}{2} [(p+1)(q+1) - d] + d - (p+1)</math>, <math>d</math> is the number of lattice points on the diagonal, <math>d \ge 2</math> | ||
+ | |||
+ | <math>(p+1)(q+1)</math> is the total number of lattice points inside the rectangle. Subtract the number of lattice points on the diagonal, divided by 2 is the number of lattice points below the diagonal, add the number of lattice points on the diagonal, and subtract the lattice points on the <math>x</math> axis, then we get the total number of lattice points on or below the diagonal and <math>x \ge 1</math>. | ||
+ | |||
+ | There are <math>900</math> lattice points in total. <math>300</math> is <math>\frac{1}{3}</math> of <math>900</math>. The <math>x</math> coordinate of the top-right vertex of the rectangle is <math>30</math>, <math>\frac{1}{2} \cdot 30 \cdot 20 = 300</math>. I guess the <math>y</math> coordinate of the top-right vertex of the rectangle is <math>20</math>. Now I am going to verify that. The slope of the diagonal is <math>\frac{20}{30} = \frac{2}{3}</math>, there are <math>11</math> lattice points on the diagonal. Substitute <math>(p,q)=(30, 20)</math>, <math>d=11</math> to the above formula: | ||
+ | |||
+ | <math>\frac{1}{2} [(30+1)(10+1) - 11] + 11 - (30+1) = 300</math> | ||
+ | |||
+ | Because there are <math>11</math> lattice points on line <math>y = \frac{2}{3}x</math>, if <math>m < \frac{2}{3}</math>, then the number of lattice points on or below the line is less than <math>300</math>. So <math>m = \frac{2}{3}</math> is the lower bound. | ||
+ | |||
+ | Now I am going to calculate the upper bound. From <math>\frac{b}{a} < \frac{b+1}{a+1}</math>, | ||
+ | |||
+ | <math>\frac{2}{3} = \frac{18}{27} < \frac{19}{28}</math> | ||
+ | |||
+ | <math>\frac{2}{3} = \frac{20}{30} < \frac{21}{31} < \frac{19}{28}</math> | ||
+ | |||
+ | <asy> | ||
+ | /* Created by Brendanb4321, modified by isabelchen */ | ||
+ | import graph; | ||
+ | size(18cm); | ||
+ | defaultpen(fontsize(9pt)); | ||
+ | xaxis(0,31,Ticks(1.0)); | ||
+ | yaxis(0,22,Ticks(1.0)); | ||
+ | |||
+ | draw((0,0)--(30,20)); | ||
+ | draw((0,0)--(30,30*19/28), dotted); | ||
+ | draw((0,0)--(31,31*21/31), dotted); | ||
+ | |||
+ | for (int i = 1; i<=31; ++i) { | ||
+ | for (int j = 1; j<=2/3*i+1; ++j) { | ||
+ | dot((i,j)); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | dot((28,19), red); | ||
+ | dot((31,21), blue); | ||
+ | label("$m=2/3$", (33,20)); | ||
+ | label("$m=21/31$", (33,21)); | ||
+ | label("$m=19/28$", (33,22)); | ||
+ | |||
+ | </asy> | ||
+ | |||
+ | If <math>m = \frac{21}{31}</math>, I will calculate by using the rectangle with blue vertex <math>(p,q) = (31, 21)</math>, then subtract lattice points on line <math>x = 31</math>, which is <math>21</math>. There are 2 lattice points on the diagonal, <math>d=2</math>. | ||
+ | |||
+ | <math>\frac{1}{2} [(31+1)(21+1) - 2] + 2 - (31+1) - 21 = 300</math>, same as that of <math>m = \frac{2}{3}</math> | ||
+ | |||
+ | If <math>m = \frac{19}{28}</math>, I will calculate by using the rectangle with red vertex <math>(p,q) = (28, 19)</math>, then add lattice points on line <math>x = 29</math> and <math>x = 30</math>, which is <math>19 + 20 = 39</math>. There are 2 lattice points on the diagonal, <math>d=2</math>. | ||
+ | |||
+ | <math>\frac{1}{2} [(28+1)(19+1) - 2] + 2 - (28+1) + 39 = 301</math>, <math>1</math> more than that of <math>m = \frac{2}{3}</math> | ||
+ | |||
+ | When <math>m</math> increases, more lattice points falls below the line <math>y = mx</math>. Any value larger than <math>\frac{19}{28}</math> has more than <math>301</math> lattice points on or below <math>y = \frac{19}{28} x</math>. So the upper bound is <math>\frac{19}{28}</math>. | ||
+ | |||
+ | <math>\frac{19}{28}-\frac{2}{3}=\frac{1}{84}</math>, <math>\boxed{\textbf{(E)} ~85}</math>. | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | ==Solution 5== | ||
+ | |||
+ | The lower bound of <math>m</math> is <math>\frac23 = \frac{20}{30}</math>. Inside the rectangle with vertices <math>(0,0)</math>, <math>(30,0)</math>, <math>(30,20)</math>, <math>(0, 20)</math> and diagonal <math>y = \frac23 x</math>, there are <math>(30-1)(20-1) = 551</math> lattice points inside, not including the edges. There are <math>9</math> lattice points on diagonal <math>y = \frac23 x</math> inside the rectangle, <math>551 + 9 = 560</math>. Half of the <math>560</math> lattice points are below diagonal <math>y = \frac23 x</math>, <math>560 \cdot \frac12 = 280</math>. There are <math>20</math> lattice points on edge <math>x = 30</math>, <math>280 + 20 = 300</math>. Once <math>m < \frac23</math>, the <math>9</math> lattice points on diagonal <math>y = \frac23 x</math> will be above the new diagonal, making the number of lattice points on and below the diagonal less than <math>300</math>. | ||
+ | |||
+ | Now we are going to calculate the upper bound by the following formula: | ||
+ | The number of lattice points inside rectangle <math>(0,0)</math>, <math>(a,0)</math>, <math>(a, b)</math>, <math>(0, b)</math> and below diagonal <math>y = \frac{b}{a}x</math> is <math>\frac{(a-1)(b-1)}{2}</math>, where <math>a</math> and <math>b</math> are relatively prime. | ||
+ | There are <math>(a-1)(b-1)</math> lattice points inside the rectangle. Because <math>a</math> and <math>b</math> are relatively prime, the only lattice points on the diagonal are <math>(0,0)</math> and <math>(a,b)</math>. By symmetry, half of the lattice points are below the diagonal. | ||
+ | |||
+ | <asy> | ||
+ | /* Created by isabelchen */ | ||
+ | import graph; | ||
+ | size(8cm); | ||
+ | defaultpen(fontsize(9pt)); | ||
+ | xaxis(0,8); | ||
+ | yaxis(0,6); | ||
+ | |||
+ | draw((0,0)--(7,5)); | ||
+ | draw((7,0)--(7,5)); | ||
+ | draw((0,5)--(7,5)); | ||
− | + | dot((0,0)); dot((1,0)); dot((2,0)); dot((3,0)); dot((4,0)); dot((5,0)); dot((6,0)); dot((7,0)); dot((8,0)); dot((0,1)); dot((1,1)); dot((2,1)); dot((3,1)); dot((4,1)); dot((5,1)); dot((6,1)); dot((7,1)); dot((8,1)); dot((0,2)); dot((1,2)); dot((2,2)); dot((3,2)); dot((4,2)); dot((5,2)); dot((6,2)); dot((7,2)); dot((8,2)); dot((0,3)); dot((1,3)); dot((2,3)); dot((3,3)); dot((4,3)); dot((5,3)); dot((6,3)); dot((7,3)); dot((8,3)); dot((0,4)); dot((1,4)); dot((2,4)); dot((3,4)); dot((4,4)); dot((5,4)); dot((6,4)); dot((7,4)); dot((8,4)); dot((0,5)); dot((1,5)); dot((2,5)); dot((3,5)); dot((4,5)); dot((5,5)); dot((6,5)); dot((7,5)); dot((8,5)); dot((0,6)); dot((1,6)); dot((2,6)); dot((3,6)); dot((4,6)); dot((5,6)); dot((6,6)); dot((7,6)); dot((8,6)); | |
− | == | + | label("$(0,0)$", (0,0), SW); |
− | {{solution}} | + | label("$(a, b)$", (7,5), NE); |
+ | dot((7,0)); | ||
+ | label("$a$", (7,0), S); | ||
+ | dot((0,5)); | ||
+ | label("$b$", (0,5), W); | ||
+ | </asy> | ||
+ | |||
+ | <math>\frac{2}{3} = \frac{20}{30} < \frac{21}{31} < \frac{19}{28}</math> | ||
+ | |||
+ | When <math>a = 31</math>, <math>b = 21</math>, <math>\frac{(31-1)(21-1)}{2} = 300</math>. | ||
+ | |||
+ | When <math>a = 28</math>, <math>b = 19</math>, <math>\frac{(28-1)(19-1)}{2} = 243</math>. Below the line <math>y = \frac{19}{28} x</math>, there are <math>19</math> lattice points on line <math>x = 28</math>, <math>19</math> lattice points on line <math>x = 29</math>, <math>20</math> lattice points on line <math>x = 30</math>, <math>243 + 19 + 19 + 20 = 301</math>. | ||
+ | |||
+ | More lattice points fall below the line <math>y = mx</math> as <math>m</math> increases. There are more than <math>301</math> lattice points on and below the line for any <math>m</math> greater than <math>\frac{19}{28}</math>. Therefore, the upper bound is <math>\frac{19}{28}</math>. | ||
+ | |||
+ | <math>\frac{19}{28}-\frac{2}{3}=\frac{1}{84}</math>, so <math>1+84=\boxed{\textbf{(E)} ~85}</math>. | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | ==Remark== | ||
+ | |||
+ | <math>\lfloor \frac{b}{a} k \rfloor</math> is the number of lattice points on line <math>x = k</math>, below line <math>y = \frac{b}{a} x</math> and above the <math>x</math> axis, where <math>k</math> is an integer and <math>0<k<a</math>. Therefore, <math>\sum_{k=1}^{a-1} \lfloor \frac{b}{a} k \rfloor</math> is the number of lattice points inside the rectangle <math>(0,0)</math>, <math>(a,0)</math>, <math>(a, b)</math>, <math>(0, b)</math>, below diagonal <math>y = \frac{b}{a} x</math>. If <math>a</math> and <math>b</math> are relatively prime, <math>\sum_{k=1}^{a-1} \lfloor \frac{b}{a} k \rfloor = \frac{(a-1)(b-1)}{2}</math>, as explained in solution 6. This problem is about finding the upper and lower bound of <math>\frac{b}{a}</math>, given <math>\sum_{k=1}^{30} \lfloor \frac{b}{a} k \rfloor = 300</math>. The same problem can have geometric representation as stated in the original problem, or algebraic representation as stated here. | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/PC8fIZzICFg | ||
+ | ~hippopotamus1 | ||
+ | |||
+ | ==Video Solution by Interstigation (In-Depth, Straight-forward)== | ||
+ | https://youtu.be/aAogEAOcL2Y | ||
+ | |||
+ | ~Interstigation | ||
==See Also== | ==See Also== | ||
− | {{AMC12 box|year=2021|ab=B|num-b=24|after=Last | + | {{AMC12 box|year=2021|ab=B|num-b=24|after=Last problem}} |
+ | |||
+ | [[Category:Intermediate Geometry Problems]] | ||
+ | {{AMC10 box|year=2021|ab=B|num-b=24|after=Last problem}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 21:58, 16 July 2024
- The following problem is from both the 2021 AMC 10B #25 and 2021 AMC 12B #25, so both problems redirect to this page.
Contents
Problem
Let be the set of lattice points in the coordinate plane, both of whose coordinates are integers between
and
inclusive. Exactly
points in
lie on or below a line with equation
The possible values of
lie in an interval of length
where
and
are relatively prime positive integers. What is
Solution 1
First, we find a numerical representation for the number of lattice points in that are under the line
For any value of
the highest lattice point under
is
Because every lattice point from
to
is under the line, the total number of lattice points under the line is
Now, we proceed by finding lower and upper bounds for To find the lower bound, we start with an approximation. If
lattice points are below the line, then around
of the area formed by
is under the line. By using the formula for a triangle's area, we find that when
Solving for
assuming that
is a point on the line, we get
Plugging in
to
we get:
We have a repeat every values (every time
goes through a lattice point). Thus, we can use arithmetic sequences to calculate the value above:
This means that is a possible value of
Furthermore, it is the lower bound for
This is because
goes through many points (such as
). If
was lower,
would no longer go through some of these points, and there would be less than
lattice points under it.
Now, we find an upper bound for Imagine increasing
slowly and rotating the line
starting from the lower bound of
The upper bound for
occurs when
intersects a lattice point again (look at this problem to get a better idea of what's happening: https://artofproblemsolving.com/wiki/index.php/2011_AMC_10B_Problems/Problem_24).
In other words, we are looking for the first that is expressible as a ratio of positive integers
with
For each
, the smallest multiple of
which exceeds
is
respectively, and the smallest of these is
Alternatively, see the method of finding upper bounds in solution 2.
The lower bound is and the upper bound is
Their difference is
so the answer is
~JimY ~Minor edits by sl_hc
An alternative would be using Farey fractions and the mediant theorem to find the upper bound. and
gives
and so on using Farey addition.
An alternative approach with the same methodology can be done using Pick's Theorem. Wikipedia page: https://en.wikipedia.org/wiki/Pick%27s_theorem. It's a formula to find the number of lattice points strictly inside a polygon. Approximation of the lower bound is still necessary.
Solution 2
Based on area ratios between a square of side length and a triangle with base
, we estimate that the slope
of the line we want is around
. There are a total of
integer coordinates in the desired range for each axis, giving a total of
lattice points, so we see if there are
points above the line,
.
Counting the number of lattice points with above the line, the number of lattice points with
above the line, and so on, we find that the total number of lattice points above the line is
, with the even integers repeating every third term. We see that the average of the
terms is
, which means that exactly
lattice points above the line as desired. This gives a lower bound because any decrease in the slope of the line would cause points that were already on the line to shift to being above it.
To find the upper bound, notice that each lattice point less than unit above the line is either
or
above. Since the slope through a point is the y-coordinate divided by the x-coordinate, a shift in the slope will increase the y-value of the higher x-coordinates more than the y-value of the lower x-coordinates. So, we turn our attention to
for which the line
intersects at
. The point
is already counted, and we can clearly see that if we slowly increase the slope of the line, we will first hit the point
since
is the closest to it. The equation of the line which goes through both the origin and
is
. This gives an upper bound of
.
Taking the upper bound of and subtracting the lower bound yields
. The answer is therefore
.
~theAJL ~Minor edits by Eric_Zang
Diagram
Solution 3
As the procedure shown in the Solution 1, the lower bound of is
Here I give a more logic way to show how to find the upper bound of
Denote
as the number of lattice points in
.
Let . for
Our target is finding the minimum value of which can increase one unit of
Notice that:
When We don't have to discuss this case.
When
When
Here
Denote
Obviously and
are decreasing. Let's considering the situation when
This means that the answer is just , so
. Choose
~PythZhou.
Solution 4
It's easier to calculate the number of lattice points inside a rectangle with vertices ,
,
,
. Those lattice points are divided by the diagonal
into
halves. In this problem the number of lattice points on or below the diagonal and
is
,
is the number of lattice points on the diagonal,
![]()
is the total number of lattice points inside the rectangle. Subtract the number of lattice points on the diagonal, divided by 2 is the number of lattice points below the diagonal, add the number of lattice points on the diagonal, and subtract the lattice points on the
axis, then we get the total number of lattice points on or below the diagonal and
.
There are lattice points in total.
is
of
. The
coordinate of the top-right vertex of the rectangle is
,
. I guess the
coordinate of the top-right vertex of the rectangle is
. Now I am going to verify that. The slope of the diagonal is
, there are
lattice points on the diagonal. Substitute
,
to the above formula:
Because there are lattice points on line
, if
, then the number of lattice points on or below the line is less than
. So
is the lower bound.
Now I am going to calculate the upper bound. From ,
If , I will calculate by using the rectangle with blue vertex
, then subtract lattice points on line
, which is
. There are 2 lattice points on the diagonal,
.
, same as that of
![]()
If , I will calculate by using the rectangle with red vertex
, then add lattice points on line
and
, which is
. There are 2 lattice points on the diagonal,
.
,
more than that of
![]()
When increases, more lattice points falls below the line
. Any value larger than
has more than
lattice points on or below
. So the upper bound is
.
,
.
Solution 5
The lower bound of is
. Inside the rectangle with vertices
,
,
,
and diagonal
, there are
lattice points inside, not including the edges. There are
lattice points on diagonal
inside the rectangle,
. Half of the
lattice points are below diagonal
,
. There are
lattice points on edge
,
. Once
, the
lattice points on diagonal
will be above the new diagonal, making the number of lattice points on and below the diagonal less than
.
Now we are going to calculate the upper bound by the following formula:
The number of lattice points inside rectangle,
,
,
and below diagonal
is
, where
and
are relatively prime. There are
lattice points inside the rectangle. Because
and
are relatively prime, the only lattice points on the diagonal are
and
. By symmetry, half of the lattice points are below the diagonal.
When ,
,
.
When ,
,
. Below the line
, there are
lattice points on line
,
lattice points on line
,
lattice points on line
,
.
More lattice points fall below the line as
increases. There are more than
lattice points on and below the line for any
greater than
. Therefore, the upper bound is
.
, so
.
Remark
is the number of lattice points on line
, below line
and above the
axis, where
is an integer and
. Therefore,
is the number of lattice points inside the rectangle
,
,
,
, below diagonal
. If
and
are relatively prime,
, as explained in solution 6. This problem is about finding the upper and lower bound of
, given
. The same problem can have geometric representation as stated in the original problem, or algebraic representation as stated here.
Video Solution
https://youtu.be/PC8fIZzICFg ~hippopotamus1
Video Solution by Interstigation (In-Depth, Straight-forward)
~Interstigation
See Also
2021 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last problem |
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 AMC 12 Problems and Solutions |
2021 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last problem | |
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 AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.