Principio del extremo

Ejemplo (clásico de Erdős). En un plano hay $n$ puntos, no todos colineales. Demostrar que existe una recta que pasa por exactamente dos de ellos.

Solución. Consideramos todos los pares $(\ell, P)$ con $\ell$ una recta que pase por al menos dos de los puntos y $P$ uno de los puntos no en $\ell$. Como no todos los puntos son colineales, hay al menos un tal par.

Entre todos los pares, escogemos uno con distancia $d(P, \ell)$ mínima (la distancia del punto $P$ a la recta $\ell$). Vamos a probar que $\ell$ contiene exactamente dos puntos del conjunto.

Supongamos por contradicción que $\ell$ contiene tres puntos $A, B, C$ (o más). Sea $Q$ el pie de la perpendicular desde $P$ a $\ell$. Al menos dos de $A, B, C$ están al mismo lado de $Q$ (en $\ell$); sin pérdida de generalidad, sean $A$ y $B$ con $A$ entre $Q$ y $B$ (puede ser $A = Q$).

Consideremos la nueva recta $\ell' = \overleftrightarrow{PB}$. Esta contiene a $B$ y a $P$, así que es una recta válida. La distancia de $A$ a $\ell'$ es la altura del triángulo $\triangle PAB$ desde $A$, que por trigonometría elemental es menor que $d(P, \ell)$ (porque el segmento $QA$ está incluido en $\ell$, y $A$ está más cerca de $\ell'$ que $P$ de $\ell$).

Pero entonces $(\ell', A)$ es un par mejor: $d(A, \ell') < d(P, \ell)$, contradiciendo la minimalidad. $\blacksquare$

Este teorema fue conjeturado por Sylvester en 1893 y permaneció abierto hasta que Gallai lo demostró en 1944, con esta elegantísima prueba.

Ejemplo (combinatoria). En un grupo de $n$ personas, ciertas parejas son amigas. Si toda persona tiene al menos un amigo, existen dos personas con exactamente el mismo número de amigos.

Solución. El número de amigos de cada persona está entre $1$ y $n - 1$ (al menos uno por hipótesis, y como máximo $n - 1$). Son $n - 1$ valores posibles para $n$ personas. Por palomar, dos personas comparten valor. $\blacksquare$

(Este no usa el extremo explícitamente, pero es de la misma familia: argumento por finitud.)

Ejemplo (geometría). En un plano hay $n \geq 3$ puntos, no todos colineales. Demostrar que existe un triángulo formado por tres de ellos cuya área es máxima, y que tiene la siguiente propiedad: ningún otro punto del conjunto está en el interior de los tres triángulos formados al unir un cuarto punto con dos vértices del original.

(La idea: si un punto $D$ estuviera, el triángulo formado con dos vértices de $ABC$ podría ser mayor — contradicción.)