Maths Olympiad Prep

Library / /12 of 24

Combinatorics Difficulty 5.7 AIME, harder Prove it Croatia

Twenty points with integer coordinates are given in the coordinate plane so that no three of them are collinear. Prove that there exists a triangle with vertices chosen among the given points whose centroid is also a point with integer coordinates.

Solution

Let the given points be A1,A2,,A20A_1, A_2, \ldots, A_{20}, with Ai=(xi,yi)A_i = (x_i, y_i), where xi,yix_i, y_i are integers.

The centroid of a triangle with vertices Ai=(xi,yi)A_i = (x_i, y_i), Aj=(xj,yj)A_j = (x_j, y_j), Ak=(xk,yk)A_k = (x_k, y_k) is
(xi+xj+xk3,yi+yj+yk3). \left(\frac{x_i + x_j + x_k}{3}, \frac{y_i + y_j + y_k}{3}\right).

We want to find three points among the 2020 such that both xi+xj+xkx_i + x_j + x_k and yi+yj+yky_i + y_j + y_k are divisible by 33.

Consider the residues modulo 33 of the xx- and yy-coordinates of each point. Each point can be assigned a pair (a,b)(a, b), where axi(mod3)a \equiv x_i \pmod{3}, byi(mod3)b \equiv y_i \pmod{3}.

There are 3×3=93 \times 3 = 9 possible residue pairs modulo 33.

By the pigeonhole principle, among 2020 points, at least 209=3\left\lceil \frac{20}{9} \right\rceil = 3 points must have the same residue pair (a,b)(a, b). That is, there exist three points Ai,Aj,AkA_i, A_j, A_k such that xixjxk(mod3)x_i \equiv x_j \equiv x_k \pmod{3} and yiyjyk(mod3)y_i \equiv y_j \equiv y_k \pmod{3}.

Therefore, xi+xj+xk0(mod3)x_i + x_j + x_k \equiv 0 \pmod{3} and yi+yj+yk0(mod3)y_i + y_j + y_k \equiv 0 \pmod{3}, so the centroid has integer coordinates.

It remains to check that these three points are not collinear. But the problem states that no three of the 2020 points are collinear, so any three points form a triangle.

Thus, there exists a triangle with vertices among the given points whose centroid is also a point with integer coordinates.

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.