Maths Olympiad Prep

Library / /79 of 94

Combinatorics Difficulty 6.8 National Olympiad Prove it Hong Kong

Some of the lattice points (x,y)(x, y), with 1x1011 \le x \le 101 and 1y1011 \le y \le 101 are marked so that no 4 marked points form the vertices of an isosceles trapezoid with bases parallel to the xx-axis or the yy-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 251251.

Consider pairs of marked points with the same yy-coordinates. If there exist two pairs of marked points with the same sum of xx-coordinates and different yy-coordinates, then the 4 points in these pairs are the vertices of an isosceles trapezoid.

Suppose there are a1,a2,,a101a_1, a_2, \dots, a_{101} marked points in the 101101 horizontal lines respectively (this means there are a1a_1 marked points with yy-coordinates equal to 11, etc.). For the horizontal line y=1y = 1, suppose the marked points are (x1,1),(x2,1),,(xa1,1)(x_1, 1), (x_2, 1), \dots, (x_{a_1}, 1) where x1<x2<<xa1x_1 < x_2 < \dots < x_{a_1}. Since
x1+x2<x1+x3<<x1+xa1<x2+xa1<<xa11+xa1, x_1 + x_2 < x_1 + x_3 < \dots < x_1 + x_{a_1} < x_2 + x_{a_1} < \dots < x_{a_1-1} + x_{a_1},
there are at least 2a132a_1 - 3 distinct sums formed by the xx-coordinates. This only holds for a12a_1 \ge 2. For a1=0a_1 = 0 or a1=1a_1 = 1, clearly, no sum can be formed. Therefore, there are at least
f(a1)+f(a2)++f(a101)(1) f(a_1) + f(a_2) + \dots + f(a_{101}) \quad (1)
where f(n)=max{2n3,0}f(n) = \max\{2n-3, 0\}.

Each of these sums lies between 1+2=31+2=3 and 100+101=201100+101=201. There are 199199 possibilities. If (1) exceeds 199199, 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 199199. Then
199f(a1)+f(a2)++f(a101)(2a13)+(2a23)++(2a1013). 199 \ge f(a_1) + f(a_2) + \dots + f(a_{101}) \ge (2a_1 - 3) + (2a_2 - 3) + \dots + (2a_{101} - 3).
This implies a1+a2++a101251a_1+a_2+\dots+a_{101} \le 251. In other words, the number of marked points is at most 251251. This can be attained, for example, in the following construction.

Figure 1

It is not hard to see that there is no isosceles trapezoid (a rigorous proof is to show that the sums of xx-coordinates of pairs of points in the same horizontal line are all different, and the same holds for yy-coordinates by symmetry). There are
3+5×49+3=251 3 + 5 \times 49 + 3 = 251
points in total.

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.