Maths Olympiad Prep

Track / Stage 7 / 102 of 300 #1982 of 2444

Problem 1982

National Olympiad second round; IMO P1/P4
Geometry Difficulty 7.2 Prove it AMC 10 B · United 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”?

zeroexactly oneexactly twomore than two
zero slope????
nonzero rational slope????
irrational slope????

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

If the slope is 00, then the line is horizontal and its equation is y=by = b for some real number bb. If bb is an integer, then the line will contain infinitely many lattice points, and if bb 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+by = mx + b, where the slope mm is a nonzero rational number, say m=pqm = \frac{p}{q} for integers pp and qq with q0q \neq 0. If the line contains a lattice point (r,s)(r, s), then it also contains the lattice points (r+q,s+p)(r+q, s+p), (r+2q,s+2p)(r+2q, s+2p), (r+3q,s+3p)(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 bb be irrational. Then (0,b)(0, b) is a point on the line, but if (r,s)(r, s) were a lattice point on the line, then
m=sbr0 m = \frac{s-b}{r-0}
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+by = mx + b, where the slope mm is an irrational number. The line could certainly contain exactly one lattice point; for example, the equation of the line could be y=2xy = \sqrt{2}x and the only lattice point on the line is (0,0)(0, 0). It could also contain no lattice points; for example, its equation could be y=2x+12y = \sqrt{2}x + \frac{1}{2}. But if a nonvertical line contains two or more lattice points, say (r,s)(r, s) and (t,u)(t, u) with rtr \neq t, then its slope, surt\frac{s-u}{r-t}, 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).

zeroexactly oneexactly twomore than two
zero slopePNPNPP
nonzero rational slopePNPNPP
irrational slopePPNPNP

So the answer is 66.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.