Combinatoria geométrica en concursos IbAm

Doble conteo con objetos geométricos

El doble conteo (contar de dos maneras) es una de las técnicas más poderosas de la combinatoria, y se aplica con especial elegancia en contextos geométricos donde la misma cantidad puede interpretarse a través de distintos objetos.

**Ejemplo clásico — Segmentos determinados por $n$ puntos:** Dado un conjunto de $n$ puntos en el plano en posición general (sin 3 colineales), ¿cuántos segmentos determinan? La respuesta directa es $\binom{n}{2}$. El doble conteo enriquece el argumento: el número de pares ordenados $(P, Q)$ con $P \neq Q$ es $n(n-1)$, y cada segmento $\overline{PQ}$ corresponde a los pares $(P,Q)$ y $(Q,P)$, así que hay $n(n-1)/2 = \binom{n}{2}$ segmentos.

Intersecciones de diagonales en un polígono convexo: En un polígono convexo de $n$ vértices (en posición general), ¿cuántas intersecciones interiores tienen las diagonales? Cada intersección interior corresponde a exactamente un par de diagonales que se cruzan, y dos diagonales se cruzan si y solo si sus 4 extremos son todos distintos. El número de cuadruples de vértices es $\binom{n}{4}$, y cada cuádruple $\{v_a, v_b, v_c, v_d\}$ con $a < b < c < d$ determina exactamente un par de diagonales que se cruzan: $\overline{v_a v_c}$ y $\overline{v_b v_d}$. Luego el número de intersecciones interiores es $\binom{n}{4}$.

Doble conteo de incidencias: Sea $P$ un conjunto de $n$ puntos y $L$ un conjunto de $m$ rectas en el plano. Sea $I$ el número de pares punto-recta con el punto sobre la recta. Contando desde el lado de los puntos: $I = \sum_{p \in P} (\text{rectas que pasan por } p)$. Contando desde el lado de las rectas: $I = \sum_{\ell \in L} (\text{puntos de } P \text{ en } \ell)$. Esta identidad es el punto de partida del problema de las incidencias de Szemerédi-Trotter, que afirma que $I \leq C \cdot (n^{2/3} m^{2/3} + n + m)$ para alguna constante $C$.

Aplicación olímpica: En problemas donde se da una condición sobre cuántos puntos están en cada recta o cuántas rectas pasan por cada punto, el doble conteo de incidencias convierte esa información en una ecuación que a menudo da el resultado buscado directamente.

Argumentos extremales en configuraciones geométricas

El principio del extremo en geometría combina la intuición geométrica con el razonamiento combinatorio: se considera el objeto "más extremo" de la configuración (el punto más lejano, la recta que cubre más puntos, el triángulo de área mínima) y se analiza qué propiedades estructurales impone.

El punto más lejano: Dado un conjunto finito $S$ de puntos en el plano, consideremos el par de puntos $(A, B)$ a distancia máxima (el "diámetro" de $S$). Cualquier otro punto $P \in S$ satisface $|PA| \leq |AB|$ y $|PB| \leq |AB|$, lo que implica que el ángulo $\angle APB \geq 60°$ (usando que en un triángulo el lado más largo está frente al ángulo mayor). Este argumento es la base de muchos problemas sobre distancias.

El teorema de Sylvester-Gallai: Dado un conjunto finito de $n \geq 3$ puntos en el plano, no todos colineales, existe al menos una recta que pasa por exactamente 2 de los puntos (una recta "ordinaria"). La demostración de Kelly usa el extremo: considera el par (punto, recta) donde la distancia del punto a la recta es mínima y positiva. Si esa recta tuviera 3 o más puntos del conjunto, se puede encontrar un par con menor distancia, contradicción.

El triángulo de área mínima: Si se tienen $n$ puntos en el plano en posición general, el triángulo de área mínima formado por tres de ellos tiene propiedades especiales: no hay ningún punto del conjunto en su interior. Esta observación se usa en problemas donde se quiere demostrar que ningún punto está "atrapado" por los demás.

Señal de argumento extremal: El problema pide "demostrar que existe un objeto con tal propiedad" sin pedir cuántos hay o cómo construirlos. La estrategia es suponer que ninguno tiene esa propiedad y obtener una contradicción usando el extremo.

El principio del palomar en contextos geométricos

El principio del palomar (pigeonhole principle) es omnipresente en combinatoria geométrica: se divide el espacio en regiones (los "palomares") y se argumenta que al menos dos puntos deben caer en la misma región.

Ejemplo fundamental — Puntos en un cuadrado: Si se colocan 5 puntos en un cuadrado de lado 1, al menos dos están a distancia $\leq \frac{\sqrt{2}}{2} \approx 0.707$. Demostración: dividir el cuadrado en 4 cuadrados de lado $1/2$; por palomar, dos puntos caen en el mismo subcuadrado; la diagonal de un cuadrado de lado $1/2$ es $\frac{\sqrt{2}}{2}$.

**Generalización — $n+1$ puntos en un triángulo equilátero:** Si se colocan $n+1$ puntos en un triángulo equilátero de lado $a$, al menos dos están a distancia $\leq a/\lceil \sqrt{n} \rceil$. La demostración divide el triángulo en $n$ subtriángulos equiláteros de lado $a/\lceil \sqrt{n} \rceil$ (o en $n$ regiones de diámetro $a/\sqrt{n}$) y aplica palomar.

Palomar con colores: Si se colorean los puntos de $\mathbb{Z}^2$ con $k$ colores, y se toman $k+1$ puntos, al menos dos tienen el mismo color. En combinatoria geométrica, esto aparece en problemas como "¿cuántos puntos de $\mathbb{Z}^2$ se necesitan para garantizar que dos de ellos sean del mismo color en cierta coloración?".

Palomar fuerte (Erdős-Szekeres): Toda sucesión de $mn + 1$ números distintos contiene una subsucesión creciente de longitud $m+1$ o una decreciente de longitud $n+1$. La demostración geométrica: asigna a cada elemento su par (longitud de la subsucesión creciente máxima hasta ese punto, longitud de la decreciente máxima). Si ninguna de las dos supera $m$ y $n$ respectivamente, hay $mn$ pares posibles para $mn+1$ elementos: palomar da una contradicción.

**El problema de las $n$ puntos y distancias repetidas:** Dado un conjunto de $n$ puntos en el plano, ¿cuántas veces puede repetirse la distancia máxima? Como mucho $n$ veces (el grafo de la distancia máxima es un grafo planar de grado $\leq 2$, pues en un círculo unitario no puede haber más de 2 puntos del conjunto a distancia 1 del centro sin que algún par supere la distancia 1). La respuesta precisa es a lo sumo $n$ veces, y este resultado usa palomar + argumentos geométricos.

Combinando técnicas: doble conteo + palomar + extremo

Los problemas más ricos de combinatoria geométrica combinan varias técnicas. Aquí un ejemplo integrador que ilustra cómo fluye el argumento:

Problema: Se tienen $n$ puntos rojos y $n$ puntos azules en el plano en posición general (sin 3 colineales, sin punto rojo sobre segmento azul-azul ni viceversa). Demuestra que existe una recta que separa todos los puntos rojos de todos los azules si y solo si los cascos convexos de los dos conjuntos son disjuntos.

**Solución (dirección $\Rightarrow$):** Si existe una recta separadora $\ell$, entonces todos los rojos están a un lado y todos los azules al otro. Los cascos convexos también están a cada lado de $\ell$ (el casco convexo es el mínimo conjunto convexo que contiene los puntos), luego son disjuntos.

**Solución (dirección $\Leftarrow$):** Si los cascos convexos $H_R$ y $H_B$ son disjuntos, por el teorema de separación de conjuntos convexos (Hahn-Banach en dimensión finita, demostrable elementalmente en 2D), existe una recta que los separa. Esta recta es la recta separadora buscada.

Argumento elemental en 2D: Considera el par de puntos $(R^*, B^*)$ con $R^* \in H_R$ y $B^* \in H_B$ a distancia mínima (extremo). La mediatriz del segmento $\overline{R^* B^*}$ es la recta separadora: cualquier punto de $H_R$ está más cerca de $R^*$ que de $B^*$ (si no, por convexidad podría encontrarse un punto de $H_R$ más cercano a $H_B$, contradiciendo la minimalidad). Este argumento combina el principio del extremo con la convexidad.

La combinación "extremo + convexidad" es característica de la combinatoria geométrica avanzada y aparece en varios problemas IbAm/Cono Sur de dificultad 3-4.

El problema de Erdős sobre distancias distintas

Uno de los problemas abiertos más famosos de combinatoria geométrica, formulado por Paul Erdős en 1946, es: ¿cuál es el número mínimo de distancias distintas $f(n)$ que puede haber en un conjunto de $n$ puntos en el plano?

El ejemplo de la cuadrícula $\sqrt{n} \times \sqrt{n}$ da $f(n) = O(n / \sqrt{\log n})$ distancias distintas (Erdős conjeturó que esto es también la cota inferior). La cota inferior $f(n) = \Omega(n^{0.8})$ fue demostrada por Guth y Katz en 2015 usando geometría algebraica.

Versión olímpica: Con $n$ puntos en el plano, ¿cuántas distancias repetidas puede haber como máximo? El problema de las distancias repetidas sí tiene soluciones elementales parciales accesibles en olimpiadas.

Resultado básico: En cualquier conjunto de $n$ puntos en el plano, la distancia más frecuente aparece a lo sumo $O(n^{4/3})$ veces (Pach-Sharir, 1992). Para nivel olímpico, la cota $O(n \sqrt{n})$ se demuestra con doble conteo y el teorema de Cauchy-Schwarz:

Sea $d$ la distancia más frecuente, con multiplicidad $t$. Sumando sobre todos los puntos $P$, el número de pares a distancia $d$ es $t$. Por doble conteo, $t = \frac{1}{2} \sum_{P} \deg_d(P)$ donde $\deg_d(P)$ es el número de puntos a distancia $d$ de $P$. Los $n$ círculos de radio $d$ centrados en los $n$ puntos se intersectan en a lo sumo $2\binom{n}{2} = n(n-1)$ puntos (cada par de círculos se intersecta en a lo sumo 2 puntos). Luego $\sum_P \deg_d(P) \leq n(n-1)$ y $t \leq n(n-1)/2 = O(n^2)$. La cota $O(n^{4/3})$ requiere argumentos más delicados.

Problema trabajado: un problema IbAm completo

Problema (Cono Sur 2017, estilo): Sean $n \geq 4$ puntos en el plano en posición general (sin 3 colineales). Para cada punto $P$ del conjunto, sea $d(P)$ el número de puntos del conjunto estrictamente más cercanos a $P$ que todos los demás (es decir, el número de puntos $Q$ tal que $|PQ| < |PQ'|$ para todo $Q' \neq P, Q$ en el conjunto). Demuestra que $\sum_{P} d(P) < 2n$.

Solución: Definimos el grafo dirigido $G$ en el que hay una arista de $P$ a $Q$ si $Q$ es el punto más cercano a $P$ en el conjunto. Cada vértice $P$ tiene a lo sumo 1 arista saliente (el más cercano puede no ser único, pero en posición general, con las distancias todas distintas, hay exactamente 1 punto más cercano a $P$). Luego $G$ tiene exactamente $n$ aristas.

Clave estructural: La relación "más cercano" no es simétrica. Si $Q$ es el vecino más cercano de $P$, puede ser que $P$ no sea el vecino más cercano de $Q$. Sin embargo, en el grafo de vecindad mutua más cercana (donde hay arista sin dirección entre $P$ y $Q$ si cada uno es el más cercano del otro), cada componente conexa es un árbol o contiene exactamente un ciclo, y los ciclos solo pueden tener longitud 2 (pares mutuos).

Cota del grado de entrada: En el grafo dirigido $G$, el grado de entrada de $Q$ es $d(Q)$ (número de puntos que tienen a $Q$ como su más cercano). Queremos demostrar $\sum_Q d(Q) = n < 2n$... espera, la suma de todos los grados de entrada es igual al número total de aristas, que es $n$ (una por vértice de salida). Entonces $\sum_P d(P) = n < 2n$. $\square$

Versión más interesante: Si $d(P)$ cuenta los puntos $Q$ tales que no hay ningún punto del conjunto más cercano a $P$ que $Q$ (es decir, $Q$ está en el conjunto de "vecinos más cercanos" pero no necesariamente el único), la cota $\sum d(P) < 2n$ requiere demostrar que el número total de pares $(P,Q)$ en la relación de vecindad más cercana es $< 2n$.

Argumento definitivo: Cada par $(P,Q)$ en la relación puede verse como una arista del grafo $G$. Demostramos que $G$ tiene a lo sumo $3n - 6$ aristas (pues $G$ es un subgrafo del grafo de Delaunay, que es planar). Para el caso específico del vecino más cercano único, hay exactamente $n$ aristas y la suma es $n < 2n$. $\square$

Síntesis: herramientas de combinatoria geométrica para IbAm

Este capítulo cierra el módulo con un mapa de las herramientas de combinatoria geométrica más útiles para la IbAm y el Cono Sur:

Doble conteo geométrico: Para contar pares (punto, recta), (punto, segmento), (diagonal, intersección), usar $\sum_{\text{puntos}} (\text{rectas por el punto}) = \sum_{\text{rectas}} (\text{puntos en la recta})$. La clave es identificar los dos modos de contar la misma incidencia.

Argumento extremal: Para probar existencia de un objeto con cierta propiedad, considerar el objeto "extremo" (máximo o mínimo bajo alguna medida). Si suponer que ese objeto no tiene la propiedad lleva a una contradicción (porque existe uno más extremo aún), la prueba está completa.

Palomar geométrico: Dividir el espacio en $k$ regiones y colocar $k+1$ o más objetos garantiza que dos caen en la misma región. La habilidad está en elegir la partición correcta del espacio (cuadrados, triángulos, franjas) para que el diámetro de cada región sea la distancia buscada.

Números de Catalan: Para problemas de triangulaciones de polígonos convexos, parentesizaciones, o caminos que no cruzan un umbral, la respuesta es un número de Catalan. Memorizar $C_n = \frac{1}{n+1}\binom{2n}{n}$ y los primeros valores $1, 1, 2, 5, 14, 42$.

Coloración en el plano: Arreglos de rectas son 2-coloreables; mapas planares son 4-coloreables (o 5 con demostración elemental). La coloración de paridad (número par/impar de rectas cruzadas) es la más usada en olimpiadas.

Conexión con herramientas del módulo: Los problemas de combinatoria geométrica en IbAm frecuentemente combinan estas técnicas con invariantes, matchings (Hall para asignaciones geométricas), o PIE (para contar configuraciones que evitan ciertas posiciones geométricas). El capítulo 8 integra el módulo completo.