Difference between revisions of "2021 AMC 12B Problems/Problem 25"
(→Solution 4) |
Isabelchen (talk | contribs) m (→Solution 5) |
||
(16 intermediate revisions by 4 users not shown) | |||
Line 6: | Line 6: | ||
<math>\textbf{(A)} ~31 \qquad \textbf{(B)} ~47 \qquad \textbf{(C)} ~62\qquad \textbf{(D)} ~72 \qquad \textbf{(E)} ~85</math> | <math>\textbf{(A)} ~31 \qquad \textbf{(B)} ~47 \qquad \textbf{(C)} ~62\qquad \textbf{(D)} ~72 \qquad \textbf{(E)} ~85</math> | ||
− | == | + | ==Solution 1== |
− | |||
− | |||
− | |||
− | <math> | + | 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=\frac{2}{3}x</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 | |
− | + | 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. | |
==Solution 2== | ==Solution 2== | ||
Line 74: | Line 70: | ||
An alternative approach with the same methodology as Solution 1 can be done using Pick's Theorem. Wikipedia page: https://en.wikipedia.org/wiki/Pick%27s_theorem It's a formula to find the amount of lattice points strictly inside a polygon. Approximation of the lower bound is still necessary. | An alternative approach with the same methodology as Solution 1 can be done using Pick's Theorem. Wikipedia page: https://en.wikipedia.org/wiki/Pick%27s_theorem It's a formula to find the amount of lattice points strictly inside a polygon. Approximation of the lower bound is still necessary. | ||
− | ==Video Solution | + | ==Solution 4== |
+ | 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 N=<math>\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 5== | ||
+ | |||
+ | 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] | ||
+ | |||
+ | ==Video Solution== | ||
https://youtu.be/PC8fIZzICFg | https://youtu.be/PC8fIZzICFg | ||
~hippopotamus1 | ~hippopotamus1 | ||
− | |||
==Video Solution by Interstigation (In-Depth, Straight-forward)== | ==Video Solution by Interstigation (In-Depth, Straight-forward)== | ||
https://youtu.be/aAogEAOcL2Y | https://youtu.be/aAogEAOcL2Y |
Latest revision as of 10:20, 4 January 2022
- 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
An alternative would be using Farey fractions and the mediant theorem to find the upper bound. and gives and so on using Farey addition.
Solution 2
I know that I want about of the box of integer coordinates above my line. There are a total of 30 integer coordinates in the desired range for each axis which gives a total of 900 lattice points. I estimate that the slope, m, is . Now, although there is probably an easier solution, I would try to count the number of points above the line to see if there are 600 points above the line. The line separates the area inside the box so that of the are is above the line.
I find that the number of coordinates with above the line is 30, and the number of coordinates with above the line is 29. Every time the line hits a y-value with an integer coordinate, the number of points above the line decreases by one. I wrote out the sum of 30 terms in hopes of finding a pattern. I graphed the first couple positive integer x-coordinates, and found that the sum of the integers above the line is . The even integer repeats itself every third term in the sum. I found that the average of each of the terms is 20, and there are 30 of them which means that exactly 600 above the line as desired. This give a lower bound because if the slope decreases a little bit, then the points that the line goes through will be above the line.
To find the upper bound, notice that each point with an integer-valued x-coordinate is either or above the line. 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. We turn our attention to which the line intersects at . The point (30,20) is already counted below the line, and we can clearly see that if we slowly increase the slope of the line, we will hit the point (28,19) since (28, ) is closer to the lattice point. The slope of the line which goes through both the origin and (28,19) is . This gives an upper bound of .
Taking the upper bound of m and subtracting the lower bound yields . This is answer .
~theAJL
Diagram
Solution 3
An alternative approach with the same methodology as Solution 1 can be done using Pick's Theorem. Wikipedia page: https://en.wikipedia.org/wiki/Pick%27s_theorem It's a formula to find the amount of lattice points strictly inside a polygon. Approximation of the lower bound is still necessary.
Solution 4
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 N= 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 5
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 .
, .
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.