Maths Olympiad Prep

Library / /51 of 86

Geometry Difficulty 6.9 National Olympiad Prove it United States

Problem:

A lattice point in the plane is a point with integer coordinates. Let TT be a triangle in the plane whose vertices are lattice points, but with no other lattice points on its sides. Furthermore, suppose TT contains exactly four lattice points in its interior. Prove that these four points lie on a straight line.

Solutions — 2

Solution 1

Solution:

Let us begin with some preliminaries. In the solution to follow, we treat points freely as vectors, e.g. writing nAn A to mean the point whose coordinates are nn times the coordinates of AA, or A+BA+B to mean the point which is the coordinate-wise sum of AA and BB.
A basic result from vector geometry, which we will assume, states that given any three noncollinear points A,B,CA, B, C in the plane, every point QQ may be represented in the form rA+sB+tCr A+s B+t C for unique r,s,tr, s, t satisfying r+s+t=1r+s+t=1. Moreover, QQ is in the interior of ABC\triangle A B C if and only if such r,s,tr, s, t are all positive. In similar fashion, any point on the line through AA and BB can be expressed as rA+sBr A+s B with r+s=1r+s=1, and lies between AA and BB if and only if r,s>0r, s>0.
We will also make repeated use of Pick's Theorem, which we now state without proof. This theorem asserts that a lattice polygon (a polygon whose vertices are lattice points) has area equal to
i+12b1 i+\frac{1}{2} b-1
where ii and bb are the number of lattice points on the polygon's interior and boundary, respectively. Thus (for instance), the triangle TT described in the problem must have area 4+12(3)1=924+\frac{1}{2}(3)-1=\frac{9}{2}.
Now we are ready to begin the solution. With no loss of generality, let us assume TT has one vertex at the origin OO, which we identify with the zero vector. Call the other two vertices AA and BB.
Of the four lattice points in the interior of TT, let PP be the point closest to line OAO A. It follows that there are no lattice points lying inside OPA\triangle O P A or on its boundary, other than O,P,AO, P, A themselves, since any such point would be closer than PP to line OAO A. Therefore, by Pick's Theorem, OPA\triangle O P A has area 12\frac{1}{2}.

Lemma: Every lattice point QQ can be expressed in the form nP+kAn P+k A for some pair of integers (n,k)(n, k). Moreover, when QQ is expressed in such form, we have n=2[OQA]n=2[O Q A]. (The brackets represent area.)

Proof. Let QQ be a lattice point. By Pick's Theorem, [OQA]=n2[O Q A]=\frac{n}{2} for some integer nn. Thus [OQA]=n[OPA][O Q A]=n \cdot[O P A]. By the base-height formula for triangle area, it follows that QQ is on the line parallel to line OAO A that passes through the point nPn P. Thus Q=nP+kAQ=n P+k A for some real kk, where kAk A is a lattice point.
We assert that kk is an integer. Indeed, if {k}\{k\} denotes the fractional part of kk, then {k}A=kAkA\{k\} A=k A-\lfloor k\rfloor A is a lattice point which lies on segment OAO A, part of the boundary of TT. Since TT has no lattice points on its boundary other than its vertices, we must have {k}=0\{k\}=0. This completes the proof of the lemma.

Let us return to the main problem. As already noted, [T]=[OBA]=92[T]=[O B A]=\frac{9}{2}. Thus by the lemma, B=9PkAB=9 P- k A for some integer kk (the minus sign in the expression is not a typo, but a deliberate convenience for what follows). Rearranging, and using the fact that OO is the zero vector, we have P=k9A+19B+8k9OP=\frac{k}{9} A+\frac{1}{9} B+\frac{8-k}{9} O. Since PP is in the interior of TT, we have 0<k<80<k<8. We will consider the possible values of kk in turn.

If k0(mod3)k \equiv 0(\bmod 3), then 13B=3Pk3A\frac{1}{3} B=3 P-\frac{k}{3} A is a lattice point lying on segment OBO B. This contradicts the specification of TT as having no lattice points on its sides.
If k2(mod3)k \equiv 2(\bmod 3), then 13B+23A=3Pk23A\frac{1}{3} B+\frac{2}{3} A=3 P-\frac{k-2}{3} A is a lattice point lying on ABA B, similarly yielding a contradiction.
The remaining possibilities are k=1,4,7k=1,4,7.

If k=1k=1, then the interior of TT contains in its interior the four collinear lattice points
P=19A+19B+79O,2P=29A+29B+59O,3P=39A+39B+39O,4P=49A+49B+19O P=\frac{1}{9} A+\frac{1}{9} B+\frac{7}{9} O, \quad 2 P=\frac{2}{9} A+\frac{2}{9} B+\frac{5}{9} O, \quad 3 P=\frac{3}{9} A+\frac{3}{9} B+\frac{3}{9} O, \quad 4 P=\frac{4}{9} A+\frac{4}{9} B+\frac{1}{9} O
If k=4k=4, then the interior of TT contains in its interior the four collinear lattice points
P=49A+19B+49O,3PA=39A+39B+39O,5P2A=29A+59B+29O,7P3A=19A+79B+19O. P=\frac{4}{9} A+\frac{1}{9} B+\frac{4}{9} O, \quad 3 P-A=\frac{3}{9} A+\frac{3}{9} B+\frac{3}{9} O, \quad 5 P-2 A=\frac{2}{9} A+\frac{5}{9} B+\frac{2}{9} O, \quad 7 P-3 A=\frac{1}{9} A+\frac{7}{9} B+\frac{1}{9} O .
If k=7k=7, then the interior of TT contains in its interior the four collinear lattice points
P=79A+19B+19O,2PA=59A+29B+29O,3P2A=39A+39B+39O,4P3A=19A+49B+49O P=\frac{7}{9} A+\frac{1}{9} B+\frac{1}{9} O, \quad 2 P-A=\frac{5}{9} A+\frac{2}{9} B+\frac{2}{9} O, \quad 3 P-2 A=\frac{3}{9} A+\frac{3}{9} B+\frac{3}{9} O, \quad 4 P-3 A=\frac{1}{9} A+\frac{4}{9} B+\frac{4}{9} O
Thus, the four lattice points inside TT are collinear in every case, as desired.

Solution 2

Solution:

We assume the same basic facts about vectors as in the previous solution, as well as Pick's Theorem and the determinant formula for the area of a parallelogram.
Let TT have vertices A=(x1,y1),B=(x2,y2)A=(x_{1}, y_{1}), B=(x_{2}, y_{2}), and C=(x3,y3)C=(x_{3}, y_{3}). We know that
x2x1x3x1y2y1y3y1=2[ABC]=9 \left|\begin{array}{ll} x_{2}-x_{1} & x_{3}-x_{1} \\ y_{2}-y_{1} & y_{3}-y_{1} \end{array}\right|=2[A B C]=9
Consider equation (1) modulo 33, that is, over the field Z/3Z\mathbb{Z} / 3 \mathbb{Z}. In this setting, the determinant is zero, so the vectors u=(x2x1,y2y1)\mathbf{u}=(x_{2}-x_{1}, y_{2}-y_{1}) and v=(x3x1,y3y1)\mathbf{v}=(x_{3}-x_{1}, y_{3}-y_{1}) are linearly dependent. If either of these vectors is zero (mod3)(\bmod 3), that is, or if they are equal, then the trisection points of a side of TT are lattice points, which contradicts the problem statement. Thus u,v0\mathbf{u}, \mathbf{v} \neq \mathbf{0} and u=v\mathbf{u}=-\mathbf{v}.
An immediate consequence is that (x1+x2+x3,y1+y2+y3)=u+v+3(x3,y3)=0(x_{1}+x_{2}+x_{3}, y_{1}+y_{2}+y_{3})=\mathbf{u}+\mathbf{v}+3(x_{3}, y_{3})=\mathbf{0} over Z/3Z\mathbb{Z} / 3 \mathbb{Z}, with the result that the centroid, G=13(A+B+C)G=\frac{1}{3}(A+B+C), is a lattice point.
Now consider ABG\triangle A B G, whose area is 13[ABC]=32\frac{1}{3}[A B C]=\frac{3}{2}. By Pick's Theorem, ABG\triangle A B G has either
- one lattice point in its interior and none on its boundary (besides vertices), or
- two lattice points on its boundary.

Case 1: ABG\triangle A B G has a lattice point in its interior and none on its boundary. In this case, a repetition of the preceding (mod3)(\bmod 3) argument shows that the centroid G1G_{1} of ABG\triangle A B G is a lattice point. In this case, G1+k(GG1)G_{1}+k(G-G_{1}) for k=0,1,2,3k=0,1,2,3 are four collinear lattice points inside TT.

Case 2: ABG\triangle A B G has two lattice points on its boundary. Note that if at least two lattice points occur on a line, then the lattice points on that line occur at regular intervals. Thus the two lattice points on the boundary of ABG\triangle A B G are either the midpoints of AGA G and BGB G or the trisection points of one of these sides (say, AGA G). In the two cases, if we extend side AGA G beyond GG, the next lattice point occurring on the extension is respectively either on TT (at the midpoint of side BCB C), which is a contradiction, or inside TT, being then the fourth collinear lattice point inside TT. So we are finished.

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.