Archivo por meses: noviembre 2012

Teorema de los 4 colores

Hoy me he encontrado en la Wikipedia con el teorema de los 4 colores. El teorema está enunciado de la siguiente manera:

Dado cualquier mapa geográfico con regiones continuas, éste puede ser coloreado con cuatro colores diferentes, de forma que no queden regiones adyacentes (es decir, regiones que compartan no sólo un punto, sino todo un segmento de borde en común) con el mismo color.

Ejemplo de un mapa

mapamundi con 4 colores
Es decir, dos países con frontera (que tienen un segmento común), no comparten color, o dicho de otro modo, si viajamos por los países, cruzar una frontera nos obliga a cambiar de color.

Según se puede leer en la wikipedia, la demostración de este teorema es polémica, ya que sólo se ha podido llevar a cabo con métodos computacionales “poco elegantes”. No con lápiz y papel.

Sea esto cierto o no y, ya que NO soy matemático deduje (con muy buen criterio :D) que debería dedicarle un tiempo de sábado a esto mientras iba al supermercado a comprar. Tras comportarme como un zombi en el supermercado pensando en el problema, esto es lo que traigo…

Al parecer es suficiente con 4 colores. Si eso no fuese así, debería poder existir un mapa donde 5 países se conociesen entre sí, haciendo falta 5 colores.

Sin embargo, yo creo que es imposible y enuncio ( :D ) lo siguiente:

Si 4 países comparten frontera todos entre sí, entonces uno de ellos está totalmente rodeado.

Supongamos que lo que digo es cierto. Si es así, el quinto país que apareciese no podría formar frontera con el país rodeado, por lo que no se cumpliría nunca que 5 países se conocen entre sí. O, dicho de otro modo, el quinto país podría reutilizar el color del país rodeado.

Para demostrar que, cuando añadamos 4 países a un mapamundi, siempre quedará uno rodeado, vamos a ir construyéndolo. Trato de que que todas las afirmaciones se cumplan para cualquier mapamundi que construyamos con 4 países conocidos entre sí.

En cada paso, se deberá cumplir lo siguiente:

El nuevo país debe tener frontera con todos los que ya están y ninguno debe quedar rodeado. Es decir, todos deben preservar algo de “costa”.

  1. Paso 1. Añadimos el primer país. Fácil. Paso 1
  2. Paso 2. Ahora debemos añadir el segundo país. Para tener frontera con todos los existentes (1 por ahora), siempre debemos crear dos puntos que delimiten la nueva frontera. Después, crearemos el país con su costa y su frontera. Quedando así.Paso 2
  3. Paso 3. En este punto, los países existentes tienen todos a) una línea de costa y b) frontera (o fronteras) con los demás. Entonces, para dar cabida a un nuevo país, cada país existente siempre deberá ceder parte de su costa para la nueva frontera con el nuevo país, es decir, tendremos que poner un punto en algún lugar de la costa. A un lado del punto habrá la nueva frontera y, al otro, seguirá habiendo costa. Busquemos esos dos puntos en el ejemplo: Paso 3
    Y creamos el país:

    Paso 3b

  4. Paso 4.. Ahora debemos hacer lo mismo que antes. Es decir, buscar un punto en la costa de cada país (nota: no hacerlo en la costa haría que no añadiesemos un nuevo país al final, sino varios de golpe y esto no sería una “historia de la formación de países” válida. Todo mapamundi tiene una historia en la que en cada paso se añade sólo uno). Necesitamos, por lo tanto, 3 puntos:
    Paso 4.
    Problema: No podemos añadir un único país sin reunciar a uno de los 3 puntos. El país que tenga el punto al que vamos a renunciar a) o bien quedará rodeado o b) no conocerá al nuevo país. La siguiente figura muestra la renuncia al punto del país verde y la aparición de un nuevo país que lo termina rodeando.
    Paso 4b
    La otra opción sería trazar el azul por el otro lado, pero no conocería al país verde, no cumpliéndose que tenemos 4 países que se conocen entre sí.

Mi teoría es que esta es la única forma de crear un mapamundi de 4 países que se conocen entre sí, es decir, uno siempre quedará rodeado, por lo que el quinto nunca puede conocer a todos, es decir, es imposible un mapamundi de cinco países todos con frontera entre sí.

Esto debe ser todo menos una demostración, pero en fin… :D