LX OM - III - Zadanie 2

Let $ S $ be the set of all points in the plane with both coordinates being integers. Find
the smallest positive integer $ k $ for which there exists a 60-element subset of the set $ S $
with the following property: For any two distinct elements $ A $ and $ B $ of this subset, there exists a point
$ C \in S $ such that the area of triangle $ ABC $ is equal to $ k $.
Let $ K $ be a subset of the set $ S $ having for a given number $ k $ the property given in the problem statement.
Let us fix any two different points $ (a, b), (c, d) \in K $. Then for some integers
$ x, y $ the area of the triangle with vertices $ (a, b) $, $ (c, d) $, $ (x, y) $ is $ k $, i.e., the equality
$ \frac{1}{2}|(a - c)(y - d) - (b - d)(x - c)| = k $ holds. From this, we obtain the condition that the equation



has for any fixed and different $ (a, b), (c, d) \in K $ a solution in integers $ x, y $. 
We will prove that if the number $ m $ does not divide $ 2k $, then the set $ K $ has no more than $ m^2 $ elements.
To this end, consider pairs $ (a \mod m, b \mod m) $ of residues of the coordinates of the points of the set $ K $ modulo $ m $.
There are $ m^2 $ of them, so if $ |K| > m^2 $, then by the pigeonhole principle, we will find two different points
$ (a, b) \in K $ and $ (c, d) \in K $ such that $ a \equiv c \mod m $ and $ b \equiv d \mod m $. For such points,
the equation (1) has no solution, since the left side of the equation for any $ x $ and $ y $ is divisible by $ m $,
while the right side is not. Therefore, $ |K| \leqslant m^2 $ for any $ m $ that is not a divisor of $ 2k $. 
From the above considerations, it follows that if $ |K| = 60 $, then $ 2k $ must be divisible by all numbers
$ m \leqslant 7 $, since $ 60 > 7^2 $. It is easy to check that the smallest natural number divisible by
2, 3, 4, 5, 6, 7 is $ 2^2 \cdot 3 \cdot 5 \cdot 7 = 420 $, so $ 210|k $. 
We will show that for every $ k $ such that $ 210|k $, a 60-element set $ K $ having the property given in the problem statement can be constructed. Let $ K $ be the set of all elements of the set $ S $,
whose both coordinates are in the set $ \{0, 1,..., 7\} $. Fix any two different points
$ A =(a, b) $ and $ B=(c, d) $ from the set $ K $. Then $ a - c, b - d \in \{-7, -6,..., 6, 7\} $, so if
$ a \neq c $, then $ a-c|420 $ and if $ b = d $, then $ b-d|420 $. Without loss of generality, we can assume that $ b = d $.
Then $ b - d|2k $, since $ 420|2k $. The point $ C =(c + \frac{2k}{d-b} ,d) $ is therefore an element of the set $ S $,
and the area of the triangle $ ABC $ is



Moreover, $ |K| = 60 $. As the set $ K $, we can take any 60-element subset of the set $ K $.
Thus, we have shown that a 60-element set having the desired property exists only for positive integers $ k $
that are multiples of 210. The smallest such number is 210.