What is the maximum number of points that can be chosen from an $N$ by $N$ grid such that no $4$ of the chosen points form a rectangle with sides parallel to the axes of the grid?
Equivalently, what is the minimum number of points chosen from an $N$ by $N$ grid to guarantee a rectangle?
What if we remove also rule out rectangles with sides not parallel to the axes of the grid?