$n$ puntos en el plano: demuestre que hay al menos $\lceil \frac{n}{3} \rceil $ diferentes distancias entre pares de puntos

Question

¿Cómo puedo demostrar que en cada grupo de $n$ puntos en el plano, tales que no hay $3$ puntos en la misma línea, hay al menos $\left\lceil \frac{n}{3} \right\rceil $ ¿diferentes distancias entre pares de puntos?

Answer 1

Demostramos mediante un argumento combinatorio que el número de distancias distintas entre pares de puntos es al menos $\displaystyle \left\lceil\frac{n-1}{3}\right\rceil$ .

Denotemos por $\mathscr{P} = \{p_i: 1 \le i \le n\}$ el conjunto de $n$ puntos en un plano sin $3$ puntos colineales y para cada $p \in \mathscr{P}$ , dejemos que $v_p$ sea el número de distancias distintas de $p$ al resto de la $n-1$ puntos.

Di, $\displaystyle \max_{p \in \mathscr{P}} v_p = v$ .

Sea, las distintas distancias forman un punto $p_i$ a los puntos restantes sea $\{d_j(p_i): 1\le j \le v_p \le v\}$ .

Déjalo, $\delta_{i,j}$ denotan el número de puntos en $\mathscr{P}\setminus \{p_i\}$ que están a una distancia de $d_j(p_i)$ de $p_i$ , para $1 \le j \le v_{p_i}$ .

Entonces, $$\sum\limits_{j=1}^{v_{p_i}} \delta_{i,j} = n-1 \tag{1}$$

para cada $i = 1,2\cdots,n$ .

Entonces, el número de pares de puntos $(p_j,p_k)$ ( $j \neq k$ ) de $\mathscr{P} \times \mathscr{P}$ de tal manera que sean equidistantes de al menos una $p_i \in \mathscr{P}\setminus \{p_j,p_k\}$ es:

$$N = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{v_{p_i}} \binom{\delta_{i,j}}{2} \tag {2}$$

(Interpretación combinatoria alternativa de $N$ es el número de triángulos isósceles que abarcan los triples de puntos de $\mathscr{P}^3$ donde los triángulos equiláteros se cuentan con multiplicidad $3$ ).

Claramente, $N$ alcanza el mínimo para una configuración $\mathscr{P}$ cuando para cada punto $p_i \in \mathscr{P}$ los valores de $\displaystyle \binom{\delta_{i,j}}{2}$ , para $1 \le j \le v_{p_i}$ son lo más parecidas posibles entre sí (debido a la restricción $(1)$ ).

Así, $$N \ge n\times v \times \binom{\frac{n-1}{v}}{2}\tag{3}$$

La otra forma de conseguir $(3)$ es por una aplicación de la desigualdad de Cauchy-Schwarz:

$$\begin{align} N = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{v_{p_i}} \binom{\delta_{i,j}}{2} &= \frac{1}{2}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{v_{p_i}} (\delta_{i,j}^2 - \delta_{i,j}) \\&= \frac{1}{2}\sum\limits_{i=1}^{n}\left(\sum\limits_{j=1}^{v_{p_i}} \delta_{i,j}^2 - (n-1)\right) \\&\ge_{C.S.} \frac{1}{2}\sum\limits_{i=1}^{n}\left(\frac{1}{v_{p_i}}\left(\sum\limits_{j=1}^{v_{p_i}} \delta_{i,j}\right)^2 - (n-1)\right) \\&= \frac{1}{2}\sum\limits_{i=1}^{n}\left(\frac{1}{v_{p_i}}\left(n-1\right)^2 - (n-1)\right) \\& \ge \binom{n}{2}\left(\frac{n-1}{v} - 1\right)\end{align}$$

Por otro lado, como no hay $3$ puntos de $\mathscr{P}$ son colineales, cada par de puntos $(p_j,p_k)$ puede ser equidistante de como máximo $2$ otros puntos.

Así, $$N \le 2\binom{n}{2}$$

Es decir, $$nv\binom{\frac{n-1}{v}}{2} \le N \le 2\binom{n}{2} \implies \frac{n-1}{v} < 3$$

Así, $v$ el número máximo de distancias distintas de un punto $p \in \mathscr{P}$ a sus vecinos es al menos $\displaystyle \left\lceil\frac{n-1}{3}\right\rceil$ .

Nota: El límite inferior $\displaystyle \left\lceil \frac{n}{3}\right\rceil$ sobre el número máximo de distancias distintas de un punto a sus vecinos (y por tanto al número de distancias distintas entre pares de puntos) para $n$ en un plano pueden darse si están en posición convexa (es decir, si forman vértices de un polígono convexo). Esto es sólo un caso particular del anterior no $3$ caso colineal.