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.
Problem
Source: Bulgaria 2000
Tags: combinatorics unsolved, combinatorics
20.11.2016 12:09
odnerpmocon wrote: ...$0\leq y_i \leq 83$ ... There is a typo here. It should be $0\leq y_i \leq 1$. Here is the official translation: In an orthogonal coordinate system $xOy$, a set consisting of $2000$ points $M_i(x_i, y_i)$ is called "good" if $0\leq x_i \leq 83;\, 0\leq y_i \leq 1\,,\, i = 1,2,\dots,2000$ and $x_i \neq x_j$ for $i \neq j$. Find the largest integer $n$ with the following property: (i) For any "good" set, some $n$ of its points lie in a square of side length $1$. (A point on a side of a square lies in the square).
06.07.2018 23:07
.........
07.07.2018 19:37
I don't remember the source of that translation I used in #2, but I've found the Bulgarian text, and here is the exact translation. It was from the final round of Bulgarian NOM 2000, problem 1. A plane with orthogonal coordinate system $xOy$ is given. A set consisting of $2000$ points $M_i(x_i, y_i)$ is called "good" if $0\leq x_i \leq 83;\, 0\leq y_i \leq 1\,,\, i = 1,2,\dots,2000$ and $x_i \neq x_j$ for $i \neq j$. Find all natural numbers $n$ with the following two properties: a) For any "good" set there exists a unit square(a square with side length $1$) containing exactly $n$ points of the set. b) There exists a "good" set for which no unit square contains exactly $n+1$ points of that set.