En Topología existen varios teoremas sobre el pintado de mapas. El más famoso es el Teorema de los cuatro colores, propuesto en 1852 y resuelto recién en 1970 con ayuda de la computadora. . En la banda de Moebius hacen falta 6 colores y en el toroide, siete.
Por otro lado el método de demostración por inducción matemática, inventado por el italiano Francesco Maurolico, pero sistematizado por el francés Blas Pascal, sirve para demostrar propiedades que involucren números naturales.
En este post relaciono ambos conceptos: inducción matemática y teorema de los dos colores.
TEOREMA DE LOS DOS COLORES:
El teorema de los dos colores dice que si sobre una hoja se trazan segmentos de extremo a extremo (con la condición de que no haya una intersección triple en un punto), siempre será posible pintar las regiones con solo dos colores, de tal forma que regiones vecinas (con más de un punto en común) no tengan el mismo color.
Llamamos P(n) a la propiedad, donde n es el número de segmentos.
Demostración por Inducción matemática:
Paso 1) P(n=1) verificamos que se cumple para n=1 segmento.
Si trazamos un solo segmento quedan dos regiones: se cumple.
fig. 1
Paso 2) P(h) =>P(h+1)
Suponemos que se cumple para h segmentos (Hipótesis inductiva); debemos demostrar que se cumplirá para h+1 segmentos (Tesis).
Demostración:
Aclaración: Si empezamos con h+1 segmentos y le quitamos uno, el razonamiento es el mismo.
Por hipótesis inductiva suponemos que se cumple con h segmentos (ver ejemplo, figura 2)
fig. 2
Agregamos un nuevo segmento AB (tenemos h+1 segmentos) que no pase por ninguna intersección existente. Tal segmento divide a la hoja en dos partes (ver ejemplo, fig. 3).
fig. 3
Una de las partes la dejamos como estaba (Por ejemplo, la de la izquierda).
Ahora podemos intercambiar los colores de la otra región (en el ejemplo, la de la derecha).
De esta manera, con h+1 segmentos es necesario solo dos colores, como postula la tesis.
Lo haremos por parte para no confundirnos: 1º el verde lo cambiamos por gris:
Al rojo lo cambiamos por verde:
Y finalmente al gris lo coloreamos de rojo:
El segmento amarillo lo pintamos de negro para terminar:
El proceso seguido garantiza el cumplimiento del enunciado ya que:
1º) El segmento agregado al atravesar cada región la divide en dos y a cada “mitad” de un lado la cambiamos de color, por lo que queda de distinto color que su vecina del otro lado.
2º) regiones vecinas que no fueron atravesadas por el nuevo segmento, sus colores fueron intercambiados y seguirán siendo de distinto color.
Así queda demostrada la propiedad para un número finito de segmentos.
Por otro lado el método de demostración por inducción matemática, inventado por el italiano Francesco Maurolico, pero sistematizado por el francés Blas Pascal, sirve para demostrar propiedades que involucren números naturales.
En este post relaciono ambos conceptos: inducción matemática y teorema de los dos colores.
TEOREMA DE LOS DOS COLORES:
El teorema de los dos colores dice que si sobre una hoja se trazan segmentos de extremo a extremo (con la condición de que no haya una intersección triple en un punto), siempre será posible pintar las regiones con solo dos colores, de tal forma que regiones vecinas (con más de un punto en común) no tengan el mismo color.
Llamamos P(n) a la propiedad, donde n es el número de segmentos.
Demostración por Inducción matemática:
Paso 1) P(n=1) verificamos que se cumple para n=1 segmento.
Si trazamos un solo segmento quedan dos regiones: se cumple.
fig. 1
Paso 2) P(h) =>P(h+1)
Suponemos que se cumple para h segmentos (Hipótesis inductiva); debemos demostrar que se cumplirá para h+1 segmentos (Tesis).
Demostración:
Aclaración: Si empezamos con h+1 segmentos y le quitamos uno, el razonamiento es el mismo.
Por hipótesis inductiva suponemos que se cumple con h segmentos (ver ejemplo, figura 2)
fig. 2
Agregamos un nuevo segmento AB (tenemos h+1 segmentos) que no pase por ninguna intersección existente. Tal segmento divide a la hoja en dos partes (ver ejemplo, fig. 3).
fig. 3
Una de las partes la dejamos como estaba (Por ejemplo, la de la izquierda).
Ahora podemos intercambiar los colores de la otra región (en el ejemplo, la de la derecha).
De esta manera, con h+1 segmentos es necesario solo dos colores, como postula la tesis.
Lo haremos por parte para no confundirnos: 1º el verde lo cambiamos por gris:
Al rojo lo cambiamos por verde:
Y finalmente al gris lo coloreamos de rojo:
El segmento amarillo lo pintamos de negro para terminar:
El proceso seguido garantiza el cumplimiento del enunciado ya que:
1º) El segmento agregado al atravesar cada región la divide en dos y a cada “mitad” de un lado la cambiamos de color, por lo que queda de distinto color que su vecina del otro lado.
2º) regiones vecinas que no fueron atravesadas por el nuevo segmento, sus colores fueron intercambiados y seguirán siendo de distinto color.
Así queda demostrada la propiedad para un número finito de segmentos.