lunes, 22 de septiembre de 2008

ENIGMAS MATEMÁTICOS


Problema de los cuatro colores


¿Es suficiente con cuatro colores para colorear todos los mapas posibles sin que ninguna región tenga frontera con otra del mismo color?




METODO DE LAS REGIONES INFINITAS



Partimos de una región cualquiera, que podemos representar mediante una línea cerrada, y la rodeamos haciendo frontera con un número infinito (la cantidad que deseemos) de otras regiones. Con cada región obtenida repetimos el mismo proceso que hemos realizado con la primera región y así indefinidamente con todas las regiones que nos vayan saliendo. De esta forma obtenemos “todos los mapas posibles” puesto que cada región tiene frontera con el número que elijamos de otras regiones.


Para todo mapa elegido se llega a las siguientes conclusiones:


1ª. Toda región rodeada completamente por un número par de otras regiones se dibuja (el conjunto de las regiones) con tres colores.


2ª. Toda región rodeada completamente por un número impar de otras regiones se dibuja (el conjunto de las regiones) con cuatro colores.


3ª. Si una cualquiera de las regiones de un mapa tiene frontera con un número impar de otras regiones, entonces el mapa se colorea con cuatro colores. En caso contrario, es decir, si todas las regiones tienen fronteras con un número par de otras regiones el mapa se colorea con tres colores.


4ª. El número mínimo de colores que se requiere para colorear cualquier mapa de modo que ninguna región tenga frontera con otra del mismo color “depende única y exclusivamente del número de regiones que rodean o tienen fronteras con cada una de las regiones del mapa”.


Conjetura 3n+1


Se escoge un entero positivo cualquiera “n”. Si n es par, se divide por 2. Si n es impar, se multiplica por 3 y se añade 1, es decir, se forma el entero 3n +1. Llamemos a esta operación T(n). Y ahora se vuelve a hacer lo mismo con el resultado que tienes, obteniéndose T (T(n)), que denotaremos T2(n). Se repite esta operación una y otra vez, obteniendo una sucesión de números: n, T(n), T2(n), T3(n)…que llamaremos la trayectoria de n por el algoritmo T. Se observa que siempre, comiences por el número que quieras, llegas, más pronto o más tarde al 1, 4, 2 y ya se repite el ciclo: 1, 4, 2, 1, 4, 2… ¿Cómo se demuestra que sucede lo mismo partiendo de cualquier número?




SOLUCIÓN: MÉTODO DE LOS PERIODOS



PERIODO UNO


Analizaremos si la transformación Tm (n) tiene un punto fijo, es decir, periodo 1 a partir de un número determinado de reiteraciones, partiendo de cualquier número entero positivo. Será así si cumple la siguiente condición: TP+1 (n) = TP (n) = K, siendo K, p y n Є a Z+.

K = valor de la transformación Tm (n) para p y p+1 reiteraciones.

Veamos si la transformación tiene periodo uno:


TP (n) = K y TP+1 (n) = K/2 si K = par


Aplicando la condición:


TP+1 (n) = TP (n) con lo cual K/2 = K de donde K = 0


Si K es impar tenemos que TP (n) = K y TP+1 (n) = 3K+1 y aplicando la condición de periodicidad uno:


TP+1 (n) = TP (n)


3K+1 = K y por lo tanto K = -1/2 que no pertenece a Z+. Con lo cual llegamos a la conclusión que Tm (n) no tiene periodo uno.



PERIODO DOS


La transformación Tm (n) será de periodo 2 si cumple la condición siguiente:


TP+2 (n) = TP (n) = K, siendo K, p y n Є a Z+.


K = valor de la transformación para p y p+2 reiteraciones. Analicemos si la transformación es de periodo 2:

TP (n) = K, TP+1 (n) = K/2 y TP+2 (n) = (3K+2)/2 siendo K = par. Aplicando la condición obtenemos:


TP+2 (n) = TP (n), (3K+2)/2 = K con lo cual K = -2 que no pertenece a los Z+.


Tampoco tendrá solución si hacemos una reiteración en la función par, n/2:


TP (n) = K, TP+1 (n) = K/2 y TP+2 (n) = K/4. Utilizando la condición: TP (n) = TP+2 (n) hallamos que K = K/4 y K = 0


Si K es impar tenemos que TP (n) = K, TP+1 (n) = 3K +1 y TP+2 (n) = (3K+1)/2. Empleando la condición de periodicidad 2:

TP (n) = TP+2 (n)

K = (3K+1)/2 y por ello k = -1. Como consecuencia de lo dicho anteriormente Tm (n) no tiene periodos dos.



PERIODO TRES



La transformación Tm (n) tendrá periodo 3 si cumple la siguiente condición:

TP (n) = TP+3 (n) = K, siendo K, p y n Є a Z+.

K = valor de la transformación para p y p+3 reiteraciones. Comprobemos si tiene periodo tres:

TP (n) = K, TP+1 (n) = K/2, TP+2 (n) = (3K+2)/2, y TP+3 (n) = (3K+2)/4 si K es par. Mediante la condición de periodicidad:

TP (n) = TP+3 (n)

K = (3K+2)4, con lo que K = 2

Entonces TP (n) = 2, TP+1 (n) = 1, TP+2 (n) = 4 y TP+3 (n) = 2


Si hacemos una o dos reiteraciones en la función par n/2:

TP (n) = K, TP+1 (n) = K/2, TP+2 (n) = K/4 y TP+3 (n) = (3K+4)/4 y aplicando la condición de periodicidad 3:

TP (n) = TP+3 (n)

K = (3K+4)/4 con lo cual K = 4 y obtenemos los siguientes resultados:

TP (n) = 4, TP+1 (n) = 2, TP+2 (n) = 1 y TP+3 (n) = 4. Si hacemos dos reiteraciones en la función n/2:

TP (n) = K, TP+1 (n) = K/2, TP+2 (n) = K/4 y TP+3 (n) = K/8 y como TP (n) = TP+3 (n) entonces K = K/8 de donde K = 0


Si K es impar obtenemos:

TP (n) = K, TP+1 (n) = 3K+1, TP+2 (n) = (3K+1)/2 y TP+3 (n) = (9K+5)/2 y utilizando la condición de periodo tres:

TP (n) = TP+3 (n)

K = (9K+5)/2 con lo que K = -5/7

Si reiteramos en la función n/2:

TP (n) = K, TP+1 (n) = 3K+1, TP+2 (n) = (3K+1)/2 y TP+3 (n) = (3K+1)/4 y como:

TP (n) = TP+3 (n)

K = (3K+1)/4 y K = 1, por lo tanto:

TP (n) = 1, TP+1 (n) = 4, TP+2 (n) = 2 y TP+3 (n) = 1


Supongamos que existe un K´ Є a Z+ para algún n con periodo 4 o superior. Sea K´=r+s, siendo r y s números pertenecientes a Z+. Averigüemos si tiene periodo cuatro:

TP (n) = K´= r +s, T P+1 (n) = (r +s)/2, TP+2 (n) = (3r +3s +2)/2, TP+3 (n) = (3r +3s +2)/4 y TP+4 (n) = (9r + 9s + 10)/4 si K´es par. Utilizando la condición de periodo cuatro:

TP (n) = TP+4 (n)

r +s = (9r + 9s + 10)/4 y por lo tanto r = (-5s -10)/5 que no pertenece a Z+. Si reiteramos en la función n/2 obtendremos:

TP (n) = r +s, TP+1 (n) = (r +s)/2, TP+2 (n) = (r +s)/4, TP+3 (n) = (r +s)/8 y

TP+4 (n) = (r +s)/16 y como:

TP (n) = TP+4 (n)

r +s = (r +s)/16, por lo que r = -s. También podemos obtener:

TP (n) = r +s, TP+1 (n) = (r +s)/2, TP+2 (n) = (r +s)/4, TP+3 (n) = (3r + 3s +4)/4 y

TP+4 (n) = (3r + 3s +4)/8 y sabiendo que:

TP (n) = TP+4 (n)

r +s = (3r + 3s +4)/8 de donde r = (-5s +4)/5 que no pertenece a Z+. Hay otras posibles combinaciones pero todas dan como soluciones números enteros negativos.


Si K´es impar tenemos:

TP (n) = r +s, TP+1 (n) = 3r + 3s +1, TP+2 (n) = (3r + 3s + 1)/2, TP+3 (n) = (9r +9s +5)/2 y TP+4 (n) = (9r +9s +5)/4 y como:

TP (n) = TP+4 (n)

r +s = (9r + 9s +5)/4 y por ello r = -s-1. Si reiteramos en la función n/2:

TP(n) = r +s, TP+1 (n) = 3r + 3s +1, TP+2 (n) = (3r +3s +1)/2, TP+3 (n) = (3r + 3s + 1)/4 y TP+4 (n) = (3r +3s +1)/8 y por la condición de periodo cuatro:

TP (n) = TP+4 (n)

r +s = (3r + 3s +1)/8, r = (-5s +1)/5 y si TP+4 (n) = (9r + 9s +7)/4 entonces r = (-5s-7)/5 que tampoco pertenece a Z+. Por lo tanto no es de periodo 4. Si generalizamos los resultados a periodos superiores a cuatro, llegamos a la siguiente conclusión: r siempre va a tener valor negativo, ya que siempre en el miembro de la igualdad donde hay mayor número de r positivas también hay mayor número de s positivas. Con lo cual al despejar r siempre saldrá negativa.


La transformación Tm (n) es divergente si hay en su trayectoria términos más grandes que cualquier número prefijado. Es decir, no existe un número K Є a Z+ que sea común a dos reiteraciones cualesquiera de la transformación. En toda transformación divergente al aplicarle el método de los periodos no hallaremos ninguna solución Є a Z+ en ninguno de los posibles periodos. Como la transformación Tm (n) tiene soluciones enteras positivas para periodo tres, entonces no puede ser divergente. Por lo tanto los resultados obtenidos al aplicar el método de los periodos son independientes del valor de n por el cual comencemos.


SERIE 3N+1




Tm (n) = 3qxn/2r + 3q-1/2r + 3q-2/2r-p(1) + 3q-3/2r-p(2) +……….+3/2r-p +1




Siendo:


p (1) el número de reiteraciones de la función n/2 entre la primera y segunda reiteración de la función 3n +1.


p (2) el número de reiteraciones de la función n/2 entre la primera y tercera reiteración de la función 3n +1.


.

.

.

p el número de reiteraciones de la función n/2 entre la primera y (q-1) reiteraciones de la función 3n +1.


n = cualquier número impar.

q = número de reiteraciones de la función 3n +1.

r = número de reiteraciones de la función n/2.

m = q +r.


Cuando 3q/2r es inferior a 1 y q tiende a infinito, es decir, r es aproximadamente 2q o superior, entonces Tm (n) converge a 4. Esto es así ya que cuando q tiende a infinito cada sumando, excepto el 1, converge a cero y como la última reiteración tiene lugar en la función 3n +1 (puesto que la serie acaba necesariamente en esta función), la serie converge a 4 que es el último resultado posible de la función 3n +1.



¿Cómo se demuestra que todo número impar tiene una trayectoria en la que r es aproximadamente 2q o superior?



EJEMPLOS



T17 (7) = 36x7/211 +35/211 + 34/210 + 33/29 + 32/27 + 3/24 + 1



T20 (9) = 37x9/213 + 36/213 + 35/211 + 34/210 + 33/29 + 32/27 + 3/24 + 1



T15 (11) = 35x11/210 + 34/210 + 33/29 + 32/27 + 3/24 + 1


T10 (13) = 33x13/27 + 32/27 + 3/24 + 1


TEORÍA DE LAS TRANSFORMACIONES





  1. Toda transformación Tm (n) se convierte en una serie en la que el número de reiteraciones es la variable. Un número n tiene período h en la transformación si TP (n) = TP+h (n) = k, siendo p y h números enteros positivos y k pertenece al dominio de la transformación. Es decir, su serie converge a k para el valor n.

  2. La transformación Tm (n) tendrá período h para todo n, si su serie converge a k independientemente del valor de n.


  1. Un número n no tiene período en la transformación Tm (n), si su serie es divergente. La transformación no tiene período para todo n, si su serie es divergente independientemente del valor de n.

  2. Cualquier transformación HX (w), para todo x Є a Z+ y w perteneciente a los números reales, cumple todas las propiedades anteriormente citadas.






No hay comentarios: