Consider $P\geq 3$ points in the plane. We count exactly $n$ different pairwise distances between distinct points. Prove that $P \leq (n+1)^2$ With the usual euclidean distance, i can't figure out how to solve this...
I tried to draw the equality case, and then adding another point at one of the distances already in but of course couldn't find any correct placement
 A: It is enough to apply the Erdos-Szekeres theorem.
The lines joining two points are finite, so up to rotations we may assume that our points have distinct abscissas.
Assume that we have $M=(n+1)^2+1$ points in the plane $P_1,P_2,\ldots,P_M$, labeled in such a way that $i<j$ implies that the abscissa of $P_i$ is less than the abscissa of $P_j$.
Let $y_1,y_2,\ldots,y_M$ the sequence of the ordinates of $P_1,P_2,\ldots,P_M$. By Erdos-Szekeres this sequence admits a weakly monotonic subsequence $y_{\sigma(1)},y_{\sigma(2)},\ldots,y_{\sigma(n+2)}$, so by considering the distances between $P_{\sigma(1)}$ and $P_{\sigma(2)},\ldots,P_{\sigma(n+2)}$ we have at least $n+1$ different pairwise distances.
A: Let $g(N)$ denote the minimal number of distinct distances between $N$ points in the plane. In his 1946 paper, Erdős proved the estimates
$$\sqrt{N-3/4}-1/2\leq g(N)\leq c N/\sqrt{\log N}.$$
The lower bound is essentially the question of the OP.
After a long string of improvements, Larry Guth and Nets Katz proved in 2015 the lower bound $$  g(N) \ge cN/ {\log N} $$  that almost matches Erdos' upper bound. See [1] for more details and references.
[1] https://en.wikipedia.org/wiki/Erd%C5%91s_distinct_distances_problem
