GeometryDifficulty 7.2National Olympiad, round 2Prove itUnited States
In the following table, each question mark is to be replaced by “Possible” or “Not Possible” to indicate whether a nonvertical line with the given slope can contain the given number of lattice points (points both of whose coordinates are integers). How many of the 12 entries will be “Possible”?
zero
exactly one
exactly two
more than two
zero slope
?
?
?
?
nonzero rational slope
?
?
?
?
irrational slope
?
?
?
?
Solution
If the slope is 0, then the line is horizontal and its equation is y=b for some real number b. If b is an integer, then the line will contain infinitely many lattice points, and if b is not an integer, then it will contain no lattice points. Therefore exactly two of the entries in that row of the table are “Possible”.
Next suppose that the equation of the line is y=mx+b, where the slope m is a nonzero rational number, say m=qp for integers p and q with q=0. If the line contains a lattice point (r,s), then it also contains the lattice points (r+q,s+p), (r+2q,s+2p), (r+3q,s+3p), and so on. Therefore the fourth entry in that row of the table is “Possible” and the second and third entries are “Not Possible”. To see that the line may contain no lattice points, let b be irrational. Then (0,b) is a point on the line, but if (r,s) were a lattice point on the line, then m=r−0s−b would be an irrational number, a contradiction. Thus the first entry in the “nonzero rational slope” row of the table is “Possible”. (This case actually includes the case of zero slope.)
Finally suppose that the equation of the line is y=mx+b, where the slope m is an irrational number. The line could certainly contain exactly one lattice point; for example, the equation of the line could be y=2x and the only lattice point on the line is (0,0). It could also contain no lattice points; for example, its equation could be y=2x+21. But if a nonvertical line contains two or more lattice points, say (r,s) and (t,u) with r=t, then its slope, r−ts−u, is rational. Therefore the first and second entries in the bottom row of the table are “Possible” and the third and fourth entries are “Not Possible”.
In all, 6 of the 12 entries are “Possible” (indicated by P in the table below), and 6 are “Not Possible” (indicated by NP).
zero
exactly one
exactly two
more than two
zero slope
P
NP
NP
P
nonzero rational slope
P
NP
NP
P
irrational slope
P
P
NP
NP
So the answer is 6.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.