Pero incluso lo más sencillo puede acabar complicándose y si sigues leyendo descubrirás cómo este problema se resiste a los esfuerzos de matemáticos de todo el mundo... desde hace 40 años.
Como ingredientes del problema te voy a dar un número de ciudades y un plano (una hoja de papel, una servilleta, una pantalla, sirve cualquier sitio donde puedas dibujar). El primer objetivo será:
Colocar cada ciudad, dibujada como un punto, donde queramos. Después, unir cada par de ciudades mediante una carretera en línea recta (un sueño para algunos, una pesadilla para otros¿Estás preparado para jugar? ¿Ya tienes con qué dibujar? Pues vamos a empezar por el caso en el que tenemos sólo 2 ciudades.).
Hay que dibujar dos puntos, donde quieras, y unirlos por una carretera recta. Ya lo sé, ya, es muy fácil... pero cada uno lo habrá dibujado de una forma; unos en vertical, otros en horizontal, algunos con otro ángulo. Quizá hayas puesto los puntos muy cerca, o muy lejos, o ni una cosa ni otra.
Pero, independientemente de cómo lo haya dibujado cada uno, todos tendremos esencialmente el mismo dibujo. Esta "esencia" del dibujo es nuestro mapa de carreteras, que será igual para todos y que en este caso es un segmento:
¿Está claro, verdad? Pues ahora vamos con el caso de 3 ciudades. Hay que dibujar tres puntos y después unir cada par de ciudades mediante una carretera recta.
¿Lo tienes? Claro que sí. Otra vez cada uno lo habrá dibujado a su manera, pero todos tendremos un mismo mapa de carreteras, que en este caso es un triángulo:
Para 4 ciudades la cosa se pone interesante. Te dejo un rato para que dibujes. Tic, tac, tic, tac. ¿Está? ¿No has hecho trampas? Me fío de ti.
Lo interesante del caso de 4 ciudades es que hay más de un mapa de carreteras:
- Algunos habréis dibujado un cuadrilátero convexo, como el de la figura de la izquierda.
- Otros habréis dibujado un triángulo con una cuarta ciudad en su interior, como el de la figura de la derecha.
Como no habíamos puesto ninguna regla más, las dos soluciones están bien... pero en realidad una de ellas es más interesante que la otra.
El mapa de carreteras de la izquierda tiene un cruce y el de la derecha no. Como un cruce de carreteras es un peligro, vamos a intentar evitar los cruces. Así, nuestro nuevo objetivo será:
Colocar las ciudades de manera que, al unir cada par de ellas en línea recta, no aparezca ningún cruce.¿Está claro, verdad? Pues ahora vamos a por el caso con 5 ciudades. Otro rato para que dibujes; tic, tac, tic, tac. ¿Has acabado? No me lo creo, inténtalo otro rato. Tic, tac, tic, tac. ¿Cómo? ¿Que no lo consigues?
No te preocupes...
Para el caso de 5 ciudades hay tres posibles mapas de carretera:
- Un pentágono convexo (figura izquierda).
- Un cuadrilátero con un punto dentro (figura central).
- Un triángulo con dos ciudades en su interior (figura derecha).
¡¡Y en todos los mapas de carretera hay algún cruce!! Resulta que para 5 ciudades no se puede encontrar una solución sin cruces (si quieres, puedes leer por qué al final de la entrada).
Además, a partir de 5 ciudades (6, 7, 8, las que sean) cualquier mapa de carreteras contendrá un mapa de carreteras con 5 ciudades. Por lo de antes, éste tendrá cruces... así que a partir de 5 ciudades cualquier mapa de carreteras tendrá cruces.
Así que tendremos que cambiar otra vez de objetivo, pero te prometo que éste es el definitivo:
Colocar las ciudades de manera que, al unir cada par de ellas en línea recta, haya el menor número posible de cruces.En el caso de 5 ciudades el mapa de carreteras que menos cruces tiene es el de la derecha, que tiene sólo uno, mientras que el del centro tiene tres y el de la izquierda tiene cinco.
¿Está claro el problema? ¿Te animas a seguir jugando? Puedes pensar un rato cómo colocar 6 ciudades de manera que al unirlas haya el menor número posible de cruces.
Lea el artículo completo en:
Mente Enjambre