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?
Problem
Source: Switzerland Mathematical Olympiad 2018, Final Round, Day 2, Problem 4
Tags: geometry, parallelogram, inequalities
23.12.2018 17:46
Can someone solve this problem please?
24.12.2018 00:26
Answer : There are at most $2n-1$ points . To prove that $2n-1$ works just take the points $(1,i)$ and $(i,1) $ for all $i \in \{1,2,3,\dots ,n \}$ , clearly there are $2n-1$ points and no $4$ of them form a parallelogram. Assume that there exist a parallelogram-free set of $2n$ points. We will consider only the horizontal segments , that is, the distances of points which belong to the same horizontal line. We can clearly see that a horizontal line has $n-1$ different distances. First we let $2$ points in each horizontal line and since there are $n$ horizontal lines , there are $n$ distances , and by Pigeon-Hole Principile $2$ of these distances are the same. Any movement of a point from a horizontal line to another will increase or will let the same number of different horizontal distances , so again by Pigeon Hole we have 2 horizontal distances of the same length in different lines , but these 4 points form a parallelogram .Contradiction . So , we showed that $2n-1$ is reachable and $2n$ is impossible . $\blacksquare$
24.12.2018 14:17
Why the 2 horizontal distances of the same length can't be in the same horizontal line?
24.12.2018 15:16
Let $A_i$ be the number of points with $y=i$. Then considering the first point on this line and the distances to subsequent points we see there are at least $A_i-1$ distinct distances between points on this line. There are only $n-1$ possible distances in total ($1,2, \cdots,n-1$) hence we get (as no two on different lines can be the same else they form a parallelogram): $$n-1 \geq \sum_{i=1}^{n} A_i-1= \left (\sum_{i=1}^{n} A_i \right)-n \Rightarrow \sum_{i=1}^{n} A_i \leq 2n-1$$So there are at most $2n-1$ points and we can use the same construction as above.