75th Romanian Mathematical Olympiad

Let $M=\{A_1,A_2,\dots ,A_m\}$ be a set of $m$ points with the given property and $A_1\in M$. Since $A_1$ is connected to other points, there is a line $d_0$ that contains exactly $n$ other points $A_2,\dots ,A_{n+1}$ from the set $M$. Since each of the points $A_1,A_2,\dots ,A_{n+1}$ is already connected to $n$ different points (other than him), we deduce that through each $A_i$ there passes exactly one more line $d_i$ that contains the other $2n-n=n$ points in $M$ connected to $A_i$.

Thus, $d_0$ contains $n+1$ points in $M$, $d_1$ contains $n$ new points in $M$ (the others except $A_1$), $d_2$ contains at least another $n-1$ points in $M$ (the others except $A_2$ and, possibly, the intersection of $d_2$ with $d_1$), etc. In general, the line $d_k$ contains at least another $n+1-k$ points in $M$ (the others except $A_k$ and, possibly, the intersections of $d_k$ with $d_1,d_2,\dots ,d_{k-1}$). So, $$m\ge (n+1)+n+(n-1)+\cdots +2+1=\frac{(n+1)(n+2)}{2}.$$

To prove that $\frac{1}{2}(n+1)(n+2)$ is the minimum, we consider a configuration of $n+2$ lines in general position (i.e. any two are concurrent and there are no three concurrent lines) and $M$ the set of $\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)$ points of intersection of them. Each line will then contain $n+1$ points from $M$ and, since each point from $M$ will be located on two of these lines, it will be connected by exactly $2\cdot (n+1-1)=2n$ points.

---

Alternative solution.

Let $M=\{A_1,A_2,\dots ,A_m\}$ be a set of $m$ points with the given property, $D_M=\{A_i{A}_j\mid 1\le i<j\le m\}$ and $D=\{a\in D_M\mid |a\cap M|=n+1\}$. We denote $d=|D|$ and $I=\{d_1\cap d_2\mid d_1,d_2\in D,d_1\ne d_2\}$.

If the points $A,B\in M$ are connected, then $A$ is connected to any of the other $n$ points in $M\setminus \{A\}$ that lie on the line $AB$. Since any point $A\in M$ is connected to exactly $2n$ other points in $M$, then $A$ lies at the intersection of exactly two lines in $D$ and thus $m=\frac{d(n+1)}{2}$. It follows that $M\subseteq I$ and the number of points in $I$ is at most equal to the number of pairs of two lines in $D$, so $|I|\le \left(\genfrac{}{}{0ex}{}{d}{2}\right)=\frac{d(d-1)}{2}$. Since $d=\frac{2m}{n+1}$, we have $$|I|\le \frac{1}{2}\cdot \frac{2m}{n+1}\left(\frac{2m}{n+1}-1\right)=\frac{m(2m-n-1)}{(n+1{)}^2}.$$ We obtain that $m\le |I|\le \frac{m(2m-n-1)}{(n+1{)}^2}$, so $m\ge \frac{1}{2}(n+1)(n+2)$.

To prove that $\frac{1}{2}(n+1)(n+2)$ is the minimum, we consider a configuration of $n+2$ lines in general position (i.e. any two are concurrent and there are no three concurrent lines) and $M$ the set of $\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)$ points of intersection of them. Each line will then contain $n+1$ points from $M$ and, since each point from $M$ will be located on two of these lines, it will be connected by exactly $2\cdot (n+1-1)=2n$ points.