This question is from a Japanese contest:
Let $S$ be a set of 2002 points in the coordinate plane, no two of which have the same $x$- or $y$- coordinate. For any two points $P,Q$ in $S$ consider the rectangle with one diagonal $PQ$ and sides parallel to the axes. Let $W_{PQ}$ be the number of points of $S$ lying in the interior of this rectangle. Find the maximum $N$ such that, no matter how the points of $S$ are distributed, there always exist points $A,B$ in $S$ with $W_{AB}\geq N$.
I think the answer is 43 (but I'm not so sure). Actually consider a set $S$ with $f(n)$ points. Let be $f(n)$ the minimum number of points such that there always exist points $A,B$ in $S$ with $W_{AB}\geq n$. I believe $f(n)=(n+1)^2+1$. The fact that $f(n)\leq (n+1)^2+1$ follows from Erdos-Szekeres theorem. The hard part is to find an example of $S$ with $(n+1)^2$ points such that $W_{AB}\leq n-1$ for all points $A,B$ in $S$ (I'm also not sure this is true for all $n$).
For $n=1$ take $S= \{(1,3),(2,1),(3,4),(4,2) \}.$
For $n=2$ take $S= \{(1,6),(2,7),(3,2),(4,1),(5,5),(6,9),(7,8),(8,3),(9,4)\}.$
For $n=3$ I don't know an example.
Does anyone know how to solve this problem?