Smallest $m$ such that, for any $m$ unit squares in an $n\times n$ grid, the centers of some four of them are vertices of a parallelogram 
Consider an $n\times n$ grid formed by $n^2$ unit squares. We define the center of a unit square as the intersection of its diagonals.
Find the smallest integer $m$ such that, choosing and $m$ unit squares in the grid, we always get four unit squares among them whose centers are vertices of a parallelogram

I was trying to derive a formula that represented the number of squares that can’t be selected after $k$ squares have already been chosen but I couldn’t because it doesn’t take into account straight lines and point outside the grid
Solutions would be appreciated
Taken from the 2016 Pan African Maths Olympiad
http://pamo-official.org/problemes/PAMO_2016_Problems_En.pdf

A partial solution
First note that if we choose the $2n-1$ squares along two adjacent edges of the grid then no parallelograms are formed and so $m$ has to be at least $2n$.
Note also that there are precisely $(2n-1)^2$ different vectors between centres of squares. One of these is the zero vector and the other vectors occur in pairs as v and -v.
For any set of $2n$ squares there are $\begin{pmatrix}2n\\2\\\end{pmatrix}$ choices of pairs of squares. Comparing this with the number of vectors given above we see that there have to be two pairs where the centres differ by the same vector. However, this does not complete the proof because the two vectors might be in the same straight line and therefore not form opposite edges of a parallelogram.
I hope these ideas help you get a full proof.
