Erdős y el método probabilístico: demostrar que las cosas existen por azar
Paul Erdős no tenía hogar, ni trabajo en el sentido corriente, ni casi posesiones. Pasó su vida viajando entre universidades con una maleta, llegando a la puerta de un colega con la frase "mi mente está abierta", y dejando tras de sí un torrente de teoremas y problemas sin resolver que los matemáticos siguen trabajando hoy. Entre todo lo que creó, una idea destaca por cambiar la forma misma en que se hacen las demostraciones. Se llama el método probabilístico, y en su corazón hay un movimiento que casi suena a trampa: demostrar que algo existe negándose a construirlo.
La pregunta: ¿cuándo es inevitable el orden?
Empieza con un acertijo de apariencia sencilla. En una fiesta de seis personas, dos cualesquiera son amigas o desconocidas. Resulta que entre seis personas cualesquiera siempre puedes encontrar tres que son todas mutuamente amigas, o tres que son todas mutuamente desconocidas. El orden se impone por sí solo. La rama de las matemáticas que estudia cuándo debe ocurrir esto es la teoría de Ramsey, y le adjunta un número a la pregunta.
El teorema de Ramsey garantiza que estos números existen, pero no dice cuán grandes son. La continuación natural es: ¿cuánto puede crecer un grupo evitando aún cualquier conglomerado monocromático de tamaño k? Responder a eso significa demostrar que existe una coloración tan ingeniosa. Y aquí es exactamente donde construir una a mano se vuelve imposible, porque el número de coloraciones posibles es astronómico.
El movimiento de Erdős: no lo construyas, cuéntalo
La intuición de Erdős, en 1947, fue dejar de intentar diseñar una buena coloración y, en cambio, colorear completamente al azar, y luego dejar que la aritmética haga el trabajo. El argumento es lo bastante corto como para seguirlo entero.
Colorea cada conexión lanzando una moneda
Toma n personas y considera la red completa donde cada par está unido por una arista. Colorea cada arista de forma independiente al azar, roja o azul, cada una con probabilidad un medio. Nada de astucia, nada de diseño. Solo una moneda justa para cada arista individual.
Mide qué probabilidad tiene un grupo de ser monocromático
Fija cualquier conjunto particular de k personas. Entre ellas hay C(k,2) aristas, es decir k(k-1)/2 conexiones. Que todas esas aristas compartan un solo color es improbable: la probabilidad es 2 × (1/2)^C(k,2), ya que hay dos colores y cada uno de los C(k,2) lanzamientos de moneda tiene que coincidir. Llama p a este número pequeño.
Suma el número esperado de grupos malos
Hay C(n,k) grupos distintos de k personas de los que preocuparse. Por la linealidad de la esperanza, el número esperado de grupos completamente monocromáticos es simplemente el recuento de grupos por la probabilidad de cada uno: C(n,k) × 2 × (1/2)^C(k,2). Esta única expresión captura, en promedio, cuántos conglomerados de un solo color contendrá una coloración aleatoria.
Si el promedio es menor que 1, debe existir una coloración impecable
Ahora elige n para que sea aproximadamente 2^(k/2). Con esa elección, el número esperado de arriba resulta menor que 1. Pero un recuento de grupos monocromáticos reales es un número entero, y si el promedio sobre todas las coloraciones es menor que 1, entonces al menos una coloración debe puntuar 0. Esa coloración no tiene ningún grupo monocromático de tamaño k. Por lo tanto R(k,k) es mayor que n, que es aproximadamente 2^(k/2).
Lee ese último paso otra vez, porque es toda la magia. Nunca produjimos una buena coloración. Nunca describimos una. Mostramos que la coloración promedio está tan cerca de ser impecable que una perfecta se ve forzada a existir en algún lugar del montón. La demostración te entrega certeza sobre un objeto concreto sin señalar ningún objeto en particular.
Por qué esto fue revolucionario
Antes de Erdős, demostrar que algo existía casi siempre significaba construirlo, o al menos describir un procedimiento que lo hiciera. El método probabilístico rompió esa expectativa. Estableció que la aleatoriedad misma podía servir como demostración: si un intento aleatorio tiene éxito con cualquier probabilidad por encima de cero, el éxito es posible, sin más.
Este sabor no constructivo coloca al argumento en la misma familia que algunos de los resultados más elegantes de las matemáticas. El argumento diagonal de Cantor también demuestra la existencia de algo, un número que falta en cualquier lista, mediante pura fuerza lógica en lugar de construcción explícita. Ambos comparten ese poder callado, casi inquietante: la conclusión es hermética aunque nunca te muestre la cosa que promete. La aleatoriedad de aquí se apoya en los mismos fundamentos que se tratan en entender la probabilidad de forma intuitiva, donde la idea de un valor esperado, el motor del paso tres, se construye desde cero.
Los problemas de Erdős y su momento de IA
Erdős no solo demostró teoremas. Planteó problemas, cientos de ellos, a menudo adjuntando pequeños premios en efectivo que iban desde unos pocos dólares por un ejercicio engañoso hasta miles por una pregunta que él creía genuinamente profunda. Muchos de esos problemas siguen abiertos, y han sido cuidadosamente catalogados y mantenidos en erdosproblems.com.
El zen del asunto
El método probabilístico es bello por la misma razón que lo es un buen truco de magia: ves cada paso, no logras encontrar el lugar donde te engañaron, y sin embargo el resultado sigue pareciendo imposible. No hay juego de manos. El valor esperado realmente es menor que uno, y un número entero por debajo de su propio promedio realmente tiene que bajar a cero en algún sitio. La certeza es total, la construcción está ausente, y ambas cosas son ciertas a la vez.
Esa es la lección perdurable que Erdős dejó atrás. Existencia y construcción no son lo mismo. A veces la forma más limpia de saber que un objeto perfecto está ahí fuera es demostrar que el objeto promedio es casi perfecto, y dejar que la diferencia haga el resto. Para otro resultado donde una sola línea ata ideas que parecen no relacionadas, la identidad de Euler ofrece la clase opuesta de belleza: donde Erdős conjura la existencia a partir del conteo, Euler fija un número exacto e inevitable.
Preguntas comunes
- ¿Qué es el método probabilístico?
- Es una forma de demostrar que existe un objeto con cierta propiedad, sin construir el objeto directamente. Construyes una versión aleatoria de la cosa, muestras que la probabilidad de que tenga la propiedad que buscas es mayor que cero, y concluyes que al menos uno de esos objetos debe existir. Paul Erdős fue pionero de la técnica, y hoy es una herramienta central en combinatoria y ciencias de la computación.
- ¿Qué demostró Erdős con él?
- Su resultado emblemático de 1947 dio una cota inferior de los números de Ramsey: demostró que el número de Ramsey diagonal R(k,k) es mayor que 2^(k/2). En palabras llanas, existen maneras de colorear las conexiones de una red grande con dos colores de modo que ningún grupo grande quede conectado por completo en un solo color. Demostró que esas coloraciones existen sin exhibir ninguna, solo mediante conteo.
- ¿Cómo se puede demostrar que algo existe sin construirlo?
- Usando promedios. Si eliges un objeto al azar y calculas el número esperado de defectos que tiene, y ese número esperado resulta menor que 1, entonces al menos un objeto del conjunto debe tener cero defectos. Una elección aleatoria cuyo recuento medio de defectos es menor que uno garantiza que un ejemplo perfecto está en algún lugar de la colección, aunque el argumento nunca señale cuál es.
- ¿Qué es un número de Ramsey?
- El número de Ramsey R(k,k) es el tamaño de grupo más pequeño que obliga a que aparezca orden sin importar cómo dispongas las cosas. En concreto, R(k,k) es el menor número de personas tal que, comoquiera que dividas cada par en amigos o desconocidos, tienes garantizado un grupo de k personas que son todas mutuamente amigas o todas mutuamente desconocidas. El teorema de Ramsey dice que estos números existen; el método de Erdős muestra que crecen muy rápido.
- ¿Por qué es importante hoy el método probabilístico?
- Convirtió la aleatoriedad en una técnica de demostración, y esa idea recorre ahora la combinatoria, el diseño de algoritmos, la teoría de códigos y la informática teórica. Muchos resultados sobre redes y algoritmos aún se demuestran mostrando que una construcción aleatoria funciona con probabilidad positiva. El método es también la razón por la que una gran parte de los propios problemas de Erdős siguen siendo objetivos activos de investigación.
¿Te gustó razonarlo paso a paso?
Math Zen convierte esta intuición en práctica diaria, con problemas adaptativos en 24 temas de matemáticas.
