Any proof for this problem?

Any ideas? I think the answer might be $\frac{(n+1)(n+2)}{2}$ (achieved when the points are arranged in a triangular array), but I don't seem to be getting at a proof. @below oops, fixed; thanks!

Ankoganit wrote: Any ideas? I think the answer might be $\frac{n(n+1)}{2}$ (achieved when the points are arranged in a triangular array), but I don't seem to be getting at a proof. Actually, it's $ \frac{(n+1)(n+2)}{2} $.

toto1234567890 wrote: Ankoganit wrote: Any ideas? I think the answer might be $\frac{n(n+1)}{2}$ (achieved when the points are arranged in a triangular array), but I don't seem to be getting at a proof. Actually, it's $ \frac{(n+1)(n+2)}{2} $. Do you have any proof ?

Let $(x_i,y_i),\ 1\le i\le |S|$ be the points in $S$. For a point $X_i=(x_i,y_i)$, consider the $n$ lines that cover $S-X$, say $a_j x+b_j y+c_j=0,\ 1\le j\le n$. By i), $X_i$ is not on any of these $n$ lines, so the polynomial $$f_i(x,y)=\displaystyle\prod\limits_{j=1}^{n} (a_jx+b_jy+c_j) $$is nonzero for $X_i$ and is zero for any other point in $S$. We have that $f_i\in \mathbb{R}[X.Y]$ and has degree at most $n$. The $2$-variable polynomials of degree at most $n$ form a vector space over the real numbers and a basis has cardinality $\dfrac{(n+1)(n+2)}{2}$ (take the standard basis $\mathcal{B}=\{x^ky^{\ell}|\ k+\ell \le n\}$). It is easy to see that the polynomials $f_i$ are linearly independent over the reals. Indeed, if $ \displaystyle\sum\limits_{i=1}^{|S|} \alpha_i f_i (x,y) =0$, by plugging $(x_i,y_i)$ in the previous relation, all polynomials cancel with the exception of $f_i$, hence $\alpha_i=0$. Thereby, $|S|\le \dfrac{(n+1)(n+2)}{2}$ and an example can be given using the aforementioned triangular array.

Is there any solution with "more standard" methods (e.g. without the use of vector spaces)?