Problem

Source: Switzerland Mathematical Olympiad 2018, Final Round, Day 2, Problem 4

Tags: geometry, parallelogram, inequalities



Let $n$ be a positive integer and let $G$ be the set of points $(x, y)$ in the plane such that $x$ and $y$ are integers with $1 \leq x, y \leq n$. A subset of $G$ is called parallelogram-free if it does not contains four non-collinear points, which are the vertices of a parallelogram. What is the largest number of elements a parallelogram-free subset of $G$ can have?