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

Question

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

Answer 1

$4$ squares on a $n \times n$ would create a parallelogram with their centers if the squares are at coordinates of the form $(i_1, j_1), (i_1, j_1+k), (i_2, j_2), (i_2, j_2+k)$ ($i_1\neq i_2$) or of the form $(i_1,j_1),(i_1+k,j_1),(i_2,j_2),(i_2+k,j_2)$ ($j_1\neq j_2$). [it's not a necessary condition - only a sufficient one]
Denote by $m$ the minimal number of squares such that every subset of $m$ squares contain a parallelogram. It is easy to see that $m \ge 2n$ because there isn't a parallelogram among $(1,1),...,(1,n), (2,1), (3,2),..., (n,n-1)$.
I will prove that $m=2n$:
Consider a subset of $2n$ squares from the $n^2$ squares, and let $a_1,...,a_n$ denote the number of squares in rows $1,...,n$ respectively.
Notice that in the $i$'th row, there are at least $a_i-1$ unique distances between chosen squares in that row (the leftmost with each of the others). If we would repeat the same distance in $2$ distinct rows, it would create a parallelogram, so all of those distances are unique.
So we got $\sum_{i=1}^{n} {a_i-1} = n$ unique distances, but each distance is in $\{1,...,n-1\}$ - a contradiction.

Answer 2

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.