Question 46
Let $n \gt 2$ be an integer and let $S$ be a set of $k$ points in the plane whose coordinates both lie in $\{1, 2, \dots, n\}$. Find the minimal number of $k$ for which one can choose four points from $S$ that are the vertices of a nondegenerate parallelogram.