El desorden completo es imposible

Trivial pero sorprendente: El Principio del Palomar

El principio del palomar o principio de Dirichlet, establece que si n palomas se distribuyen en m palomares, y si n > m, es decir, hay más palomas que palomares, al menos habrá un palomar con más de una paloma. Hasta aquí todo bien, no hemos descubierto la cuadratura del circulo, ya que lo que básicamente dice este principio es que si tenemos un determinado número de huecos (llamemos a este número m) para almacenar un determinado número de objetos (digamos por ejemplo un número n de objetos) si el número de objetos, n, es mayor que el número de huecos, m, necesariamente habrá un hueco con al menos dos objetos.

Este resultado puede parecer trivial (de hecho lo es), ya que tan siquiera necesita demostración debido precisamente a su simplicidad, pero es un principio muy potente con aplicaciones en campos tan diversos como la teoría de grafos, combinatoria, ciencias de la computación, teoría de números, etcétera.

De la mano de este principio podemos demostrar cosas muy interesantes, por ejemplo, la cantidad de pelos en la cabeza va desde cero hasta unos 100.000 ó 150.000 (considerando solo el cuero cabelludo y según lo que dice nuestra querida amiga Wikipedia) y para curarnos en salud vamos a pensar que existe alguien híper-peludo con 1.000.000 de pelos en la cabeza. Aplicando el principio del palomar tenemos que como en España hay unos 46 millones de personas (estas serían las palomas) y que podemos tener gente con cero pelos hasta 1.000.000 (estos son los palomares, es decir, desde el palomar en el que clasificamos a la gente con cero pelos hasta la gente híper-peluda con 1.000.000 de pelos) necesariamente al menos dos personas tienen exactamente el mismo número de pelos, no solo en España, en cualquier país con más de un millón de habitantes.

Sin embargo, no solo podemos garantizar que al menos dos personas tendrán el mismo número de pelos en la cabeza, podemos ir más allá. Dividiendo m/n obtenemos una aproximación más real del número mínimo de personas que deben compartir número de pelos en la cabeza (o palomas que comparten palomar). Entonces dividiendo la población de España (46 millones) entre el número de pelos (1 millón) tenemos que hay al menos 46 personas que comparten palomar, es decir, que tienen exactamente el mismo número de pelos en la cabeza.

Un paso más allá: Teoría de Ramsey

Como ya se podría apreciar en el título de esta entrada, el desorden completo es muy difícil (sino imposible) de conseguir. Por ejemplo, en la siguiente imagen, los puntos que aparecen han sido generados de manera aleatoria (20 puntos con sus coordenadas x e y generadas al azar mediante la función ALEATORIO() de Excel). Sin embargo, es fácil encontrar algunos patrones como cuadrados, cruces, puntos que se hallan por debajo de un nivel, zonas monótonamente crecientes, monótonamente decrecientes, etcétera.

De esto mismo se dio cuenta el matemático Frank P. Ramsey, y estudió las condiciones mínimas bajo las cuales el orden debe aparecer. En su honor, la teoría lleva su nombre. Los problemas de esta teoría son de la forma: ¿Cuántos elementos debe contener una estructura para garantizar la existencia de una propiedad particular?. Dicho de otra manera, cuando un conjunto es lo suficientemente grande, podemos encontrar patrones (orden) dentro de dicho conjunto.

Grafico_Puntos_Aleatorios

Al observar la gráfica anterior la sensación es similar a cuando observamos un cielo estrellado lejos de la gran ciudad para evitar la contaminación lumínica. Si hay suficientes estrellas siempre podremos hacer todo tipo de formas geométricas tales como un triangulo, un cuadrado, etcétera. En este sentido, un resultado es el denominado problema del final feliz nombrado así por Paul Erdös. Este problema representa uno de los primeros resultados de la teoría de Ramsey y dice así:

“Cualquier conjunto de 5 puntos en el plano en posición general (no colineales) tiene un subconjunto de 4 puntos que son los vértices de un cuadrilátero convexo”.

Cabe resaltar que existen otros problemas con resultados sorprendentes de la teoría de Ramsey, como el Teorema de Ramsey Infinito que nos dice que si tenemos un conjunto infinito y distribuimos sus elementos en un número finito de cajas, entonces hay una caja que contiene infinitos elementos.

Otro resultado interesante se deriva del Teorema de Bolzano, en este caso, podríamos afirmar que toda sucesión infinita de números reales contiene una subsucesión infinita creciente o decreciente.

Y mi favorito, el Teorema de la Amistad. Supongamos que en una fiesta hay seis personas. Consideremos a dos personas cualesquiera de estas seis. Puede ser que estas dos personas no se conozcan, en cuyo caso los llamaremos mutuamente extraños. Por otra parte es posible que estas dos personas ya se conocieran, en cuyo caso los llamaremos mutuamente conocidos. Ahora el Teorema de la Amistad dice:

“En cualquier grupo de seis personas existen al menos tres personas que son mutuamente conocidas o tres personas que son mutuamente desconocidas”.

Para demostrar esto vamos a tirar de una vieja conocida en este blog, la teoría de grafos. En nuestro grafo, cada uno de las personas de la fiesta será un vértice, denotaremos si estos son mutuamente conocidos con una línea verde, si por el contrario son mutuamente desconocidos estableceremos la conexión entre esas dos personas mediante una línea roja. El siguiente grafo muestra una de las posibles combinaciones.

Grafo_Teorema_Amistad

Una forma de comprobar el resultado es mediante fuerza bruta (algo muy común en problemas de Teoría Ramsey), en otras palabras, evaluando los 78 grafos posibles. No obstante en este caso disponemos de una alternativa más eficiente gracias a la teoría de grafos.

Sobre cualquier vértice del grafo inciden 5 aristas, que pueden ser de color rojo o de color verde. Según el principio del palomar, al menos tres aristas tienen el mismo color (que es lo que nos dice el teorema), ya que si hay menos de tres aristas de un color, digamos verde, necesariamente habrá al menos tres del color contrario, rojo. Luego con este simple razonamiento hemos terminado.

Para terminar este post, voy a tirar de una de esas frases que muchos (me incluyo) empleamos cuando alguien nos cambia algo de sitio: “Déjalo como está que yo entiendo mi orden”. Ahora la podemos decir con más razón aún.

Un comentario en “El desorden completo es imposible

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s