Problem

Source: Bulgaria 2000

Tags: combinatorics unsolved, combinatorics



In the coordinate plane, a set of $2000$ points $\{(x_1, y_1), (x_2, y_2), . . . , (x_{2000}, y_{2000})\}$ is called good if $0\leq x_i \leq 83$, $0\leq y_i \leq 83$ for $i = 1, 2, \dots, 2000$ and $x_i \not= x_j$ when $i\not=j$. Find the largest positive integer $n$ such that, for any good set, the interior and boundary of some unit square contains exactly $n$ of the points in the set on its interior or its boundary.