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
Best Answer
$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.