# Minimum number of points chosen from an $N$ by $N$ grid to guarantee a rectangle?

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?