Problem:
Let be the set of lattice points in the coordinate plane, both of whose coordinates are integers between 1 and 30 , inclusive. Exactly 300 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 ?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
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.
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 .
The lower bound is and the upper bound is . Their difference is , so the answer is .
The problems on this page are the property of the MAA's American Mathematics Competitions