Numeremos los puntos como
[tex]x_1[/tex]
hasta
[tex]x_n[/tex]
. Sea
[tex]k_i[/tex]
, para
[tex]i\in\{1,\dots,n\}[/tex]
, la cantidad de rectas distintas que pasan por el punto
[tex]i[/tex]
.
Por otra parte, llamemos
[tex]m[/tex]
a la cantidad de rectas distintas que se forman al unir los pares de puntos y numerémolas desde
[tex]L_1[/tex]
hasta
[tex]L_m[/tex]
:
[tex]L_1, \dots, L_m[/tex]
. Si llamamos $s_j = {i: x_i\in L_j}$, para
[tex]j\in\{1,\dots,n\}[/tex]
, entonces
[dtex]\sum_{i=1}^ n k_i = \sum_{j=1}^m s_j\ \ (1)[/dtex]
Notemos también que si
[tex]x_i\ni L_j[/tex]
, entonces
[tex]k_j\geq s_j\ \ (2)[/tex]
, pues al menos hay una recta que pasa por
[tex]x_i[/tex]
y por cada punto de
[tex]x_j[/tex]
.
Supongamos sin pérdida de generalidad que
[tex]k_n[/tex]
es el menor de los
[tex]k_i[/tex]
y que las rectas
[tex]L_1, L_2,\dots,L_{k_n}[/tex]
son las que pasan por
[tex]x_n[/tex]
. Como cada recta contiene al menos dos puntos de los
[tex]n[/tex]
, entonces podemos elegir por cada
[tex]L_i[/tex]
un punto
[tex]x_i[/tex]
tal que
[tex]x_i\neq x_n[/tex]
, para
[tex]i\in\{1,\dots,k_n\}[/tex]
. Además, como las rectas son distintas, tenemos que
[tex]x_i\ni L_j[/tex]
para
[tex]i\neq j, i,j\in\{1,\dots,n\}[/tex]
.
Usando la propiedad
[tex] (2)[/tex]
y el hecho de que
[tex]k_n > 1[/tex]
(pues si no, todos los puntos serían colineales), tenemos la siguiente lista de desigualdades:
[dtex]
\begin{aligned}
k_1 &\geq s_2 \\
k_2 &\geq s_3 \\
&\vdots \\
k_{k_n-1} &\geq s_{k_n} \\
k_n &\geq s_j,\ j>k_n
\end{aligned}
[/dtex]
Como
[tex]k_n[/tex]
es el mínimo, entonces tenemos que
[tex]s_j\geq k_n[/tex]
para
[tex]j\in\{1,\dots,m\}[/tex]
. Volviendo a la igualdad
[tex] (1)[/tex]
, tenemos que
[dtex]n k_n \leq \sum_{i=1}^ n k_i = \sum_{j=1}^m s_j \leq m k_n,[/dtex]
de lo que se concluye lo pedido.
Como dato extra, este resultado se llama Teorema de De Bruijin-Erdős y es válido en casos más generales que el plano euclidiano. En el caso del plano euclidiano, hay una demostración que usa el Teorema de Sylvester-Gallai e inducción.
