Let $n,a,b,c$ be natural numbers. Every point on the coordinate plane with integer coordinates is colored in one of $n$ colors. Prove there exists $c$ triangles whose vertices are colored in the same color, which are pairwise congruent, and which have a side whose lenght is divisible by $a$ and a side whose lenght is divisible by $b$.
Problem
Source: Balkan BMO Shortlist 2017 C2
Tags: lattice points, combinatorics, number theory, congruent triangles, Coloring, IMO Shortlist
31.07.2019 20:48
Consider $c$ triangles each with one side length $a$ and another $b$. By Gallai's theorem, there is a monochromatic homothetic copy.
15.08.2021 20:19
I will prove that there exist infinitely many pairwise congruent triangles, all with the same color and with sides parallel to the $x$-axis and the $y$-axis, so we can drop the divisibility condition by considering segment of length $ab$ as unit segments. Consider a ${n} \times {n}$ square. Since there are only $n$ colors and its leftmost side parallel to the $y$-axis contains $n+1$ lattice points, there is at least $1$ pair of point of the same color lying on this side. Now, consider a row of ${(n+1) \cdot \binom {n+1}2}$ of the previous ${n} \times {n}$ squares attached together. Since there are only $\binom {n+1}2$ pairs of points on the leftmost side of each square, there exist two lines parallel to the $x$-axis that contain at least $n+1$ pairs of points of the same color. There are only $n$ colors, so this means that there exists a monochromatic rectangle. Considering infinitely many of the former rectangles (with the ${n} \times {n}$ squares), there is a color such that there are infinitely many monochromatic rectangles of that color. Also, the dimensions of these rectangles can take finitely many values (they are integral and the rectangles lie inside or on the boundaries of each $ {n} \times {(n+1) \cdot \binom {n+1}2}$ rectangle). Thus, we obtain that there are infinitely many congruent rectangles, all of the same color. The result follows.