9. let $n$ be a natural number and $G$ 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 contain four non-collinear points that are the vertices of a parallelogram. What is the maximum number of elements a parallelogram-free subset of $G$ can contain?
Solution (Cyril): The maximum number of elements is $2 n-1$.

- $\geq 2 n-1$ : We take all points of the form $(0, y)$ and $(x, 0)$. If we now choose 4 points, at least three of them are collinear and therefore cannot form a parallelogram.
- $\leq 2 n-1$ : We prove that if we choose $2 n$ points, we can then find a parallelogram in which 2 points have the same $x$-coordinate. (so we prove something slightly stronger).

Assume that we can choose $2 n$ points without forming such a parallelogram. We now add these points to our set one after the other, in order of increasing $y$-coordinate.

For each point that we add to the set, we consider the distance to the point with the smallest $y$-coordinate and the same $x$-coordinate. As soon as we encounter the same strictly positive distance twice, the corresponding points must form a parallelogram (as they cannot all have the same $x$-coordinate, as we take the distance to the smallest $y$-coordinate in each case).

We can now almost finish with the drawer. We just have to see that the possible distances go from 0 to $n-1$ (0 if it is the point with the smallest $y$ coordinate) and we have a maximum of $n$ points with distance 0. Therefore, we must have twice the same distance that is not 0.