Some of the lattice points , with and are marked so that no 4 marked points form the vertices of an isosceles trapezoid with bases parallel to the -axis or the -axis (a rectangle is counted as an isosceles trapezoid). Determine the maximum number of marked points. (A lattice point is a point with integral coordinates.)
Solution
The answer is .
Consider pairs of marked points with the same -coordinates. If there exist two pairs of marked points with the same sum of -coordinates and different -coordinates, then the 4 points in these pairs are the vertices of an isosceles trapezoid.
Suppose there are marked points in the horizontal lines respectively (this means there are marked points with -coordinates equal to , etc.). For the horizontal line , suppose the marked points are where . Since
there are at least distinct sums formed by the -coordinates. This only holds for . For or , clearly, no sum can be formed. Therefore, there are at least
where .
Each of these sums lies between and . There are possibilities. If (1) exceeds , then two of the sums are equal by the pigeonhole principle. Since the equal sums must correspond to distinct horizontal lines from the construction, we can find an isosceles trapezoid as suggested. Therefore, we may assume (1) is at most . Then
This implies . In other words, the number of marked points is at most . This can be attained, for example, in the following construction.

It is not hard to see that there is no isosceles trapezoid (a rigorous proof is to show that the sums of -coordinates of pairs of points in the same horizontal line are all different, and the same holds for -coordinates by symmetry). There are
points in total.