MathDB

Let

S

be a set of 2002 points in the coordinate plane, no two of which have the same x\minus{} or y\minus{}coordinate. For any two points

P,Q \in S

, consider the rectangle with one diagonal

PQ

and the sides parallel to the axes. Denote by

W_{PQ}

the number of points of

S

lying in the interior of this rectangle. Determine the maximum

N

such that, no matter how the points of

S

are distributed, there always exist points

P,Q

S

with

W_{PQ}\ge N

Problem Statement