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 T²(n). Se repite esta operación una y otra vez, obteniendo una sucesión de números: n, T(n), T²(n), T³(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 T^m (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: T^P+1 (n) = T^P (n) = K, siendo K, p y n Є a Z⁺.

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

Veamos si la transformación tiene periodo uno:

T^P (n) = K y T^P+1 (n) = K/2 si K = par

Aplicando la condición:

T^P+1 (n) = T^P (n) con lo cual K/2 = K de donde K = 0

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

T^P+1 (n) = T^P (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 T^m (n) no tiene periodo uno.

PERIODO DOS

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

T^P+2 (n) = T^P (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:

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

T^P+2 (n) = T^P (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:

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

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

T^P (n) = T^P+2 (n)

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

PERIODO TRES

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

T^P (n) = T^P+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:

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

T^P (n) = T^P+3 (n)

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

Entonces T^P (n) = 2, T^P+1 (n) = 1, T^P+2 (n) = 4 y T^P+3 (n) = 2

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

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

T^P (n) = T^P+3 (n)

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

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

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

Si K es impar obtenemos:

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

T^P (n) = T^P+3 (n)

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

Si reiteramos en la función n/2:

T^P (n) = K, T^P+1 (n) = 3K+1, T^P+2 (n) = (3K+1)/2 y T^P+3 (n) = (3K+1)/4 y como:

T^P (n) = T^P+3 (n)

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

T^P (n) = 1, T^P+1 (n) = 4, T^P+2 (n) = 2 y T^P+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:

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

T^P (n) = T^P+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:

T^P (n) = r +s, T^P+1 (n) = (r +s)/2, T^P+2 (n) = (r +s)/4, T^P+3 (n) = (r +s)/8 y

T^P+4 (n) = (r +s)/16 y como:

T^P (n) = T^P+4 (n)

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

T^P (n) = r +s, T^P+1 (n) = (r +s)/2, T^P+2 (n) = (r +s)/4, T^P+3 (n) = (3r + 3s +4)/4 y

T^P+4 (n) = (3r + 3s +4)/8 y sabiendo que:

T^P (n) = T^P+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:

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

T^P (n) = T^P+4 (n)

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

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

T^P (n) = T^P+4 (n)

r +s = (3r + 3s +1)/8, r = (-5s +1)/5 y si T^P+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 T^m (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 T^m (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

T^m (n) = 3^qxn/2^r + 3^q-1/2^r + 3^q-2/2^r-p(1) + 3^q-3/2^r-p(2) +……….+3/2^r-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 3^q/2^r es inferior a 1 y r tiende a infinito,  T^m (n) converge a 4. Esto es así ya que cuando r 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.

EJEMPLOS

T¹⁷ (7) = 3⁶x7/2¹¹ +3⁵/2¹¹ + 3⁴/2¹⁰ + 3³/2⁹ + 3²/2⁷ + 3/2⁴ + 1=4

T²⁰ (9) = 3⁷x9/2¹³ + 3⁶/2¹³ + 3⁵/2¹¹ + 3⁴/2¹⁰ + 3³/2⁹ + 3²/2⁷ + 3/2⁴ + 1=4

T¹⁵ (11) = 3⁵x11/2¹⁰ + 3⁴/2¹⁰ + 3³/2⁹ + 3²/2⁷ + 3/2⁴ + 1=4

T¹⁰ (13) = 3³x13/2⁷ + 3²/2⁷ + 3/2⁴ + 1=4

TEORÍA DE LAS TRANSFORMACIONES

1. Toda transformación T^m (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 T^P (n) = T^P+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 T^m (n) tendrá período h para todo n, si su serie converge a k independientemente del valor de n.

3. Un número n no tiene período en la transformación T^m (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.
4. Cualquier transformación H^X (w), para todo x Є a Z⁺ y w perteneciente a los números reales, cumple todas las propiedades anteriormente citadas.
5. Las ecuaciones del método de los períodos en las transformaciones son independientes del número por el cual comencemos. Si la transformación tiene período h, todos sus miembros n tienen ese período. Si un miembro de la transformación tiene período h, todos sus miembros n tienen ese período. Si un solo miembro es divergente, todos sus miembros n son divergentes.

 Todo número impar converge a 4,2,1

De la ecuación general del árbol de reiteraciones 4,2,1 (página 32) se obtiene:

x3^q= 2²ⁿ-y₁ e  y3^q=2^2n-1-y₂ , siendo x los impares que cumplen la primera ecuación e

y los impares que cumplen la segunda ecuación. Todos los impares que cumplan las ecuaciones son miembros del árbol de reiteraciones y por lo tanto convergen a 4,2,1.

y₁= 2^{m1+m2+...+m(q-1)}+3^q-1+3^q-22^m1+3^q-32^m1+m2+….+2^{m1+m2+...+m(q-2)}3 que depende de las reiteraciones del impar x

y₂₌ 2^{m1+m2+...+m(q-1)}+3^q-1+3^q-22^m1+3^q-32^m1+m2+….+2^{m1+m2+...+m(q-2)}3 que depende de las reiteraciones del impar y

Sabiendo que en la sucesión a_n1= 2²ⁿ-1 todos sus términos son impares múltiplos de 3 , ya que 2²ⁿ-1= 3(2^2n-2+2^2n-4+…..+2²+1), podemos hallar un conjunto de sucesiones en las que todos sus términos positivos sean múltiplos de 3. Si a la sucesión anterior le restamos 6 obtenemos otra sucesión cuyos términos positivos son todos múltiplos de 3 (a_n2= 2²ⁿ-7). Si a esta última sucesión le volvemos a restar 6 obtenemos la tercera sucesión, a_n3= 2²ⁿ-13 y así sucesivamente. Observamos que estas sucesiones coinciden con el segundo miembro de la primera ecuación. Las sucesiones son las siguientes:

a_n1= 2²ⁿ-1 para todo n

a_n2= 2²ⁿ-7 para todo n≥2

a_n3= 2²ⁿ-13 para todo n≥2

a_n4= 2²ⁿ-19 para todo n≥3

………….

………….

………….

a_nm= 2²ⁿ-(6m-5)

Sabiendo que en la sucesión a_r= 2^2n-1+1 todos sus términos son impares múltiplos de 3, puesto que 2^2n-1+1= 3(2^2n-3+2^2n-5+….+2+1), hallamos la siguiente sucesión restando 6 a la anterior y así sucesivamente. Se observa que las sucesiones halladas (a excepción de la primera) coinciden con el segundo miembro de la segunda ecuación. Las sucesiones en las que todos sus términos positivos son múltiplos de 3 son las siguientes:

a_r1= 2^2n-1-5 para todo n≥2

a_r2= 2^2n-1-11 para todo n≥3

a_r3= 2^2n-1-17 para todo n≥3

a_r4= 2^2n-1-23 para todo n≥3

…………………

…………………

…………………

a_rm= 2^2n-1-(6m-1)

Todo impar múltiplo de 3 y por lo tanto todo impar múltiplo de 3^q, está en una de estas sucesiones. En las sucesiones están todos los impares múltiplos de 3 porque a las potencias de base 2 se le ha restado todos los impares que hacen que los términos positivos de las sucesiones sean múltiplos de 3.

De aquí se deduce que y₁= 6m-5 e y₂= 6m-1. Cada impar x tiene un único y₁ y cada impar y tiene un único y₂.

Por lo tanto las dos ecuaciones se transforman en:

x3^q= 2²ⁿ-(6m-5) e   y3^q=2^2n-1-(6m-1)

Cada impar que converge a 4,2,1 cumple una de las dos ecuaciones. Todo impar al multiplicarlo por 3^q se obtiene un múltiplo de 3^q que está en una de las sucesiones y por lo tanto en una de las dos ecuaciones. Todo impar cumple una de las dos ecuaciones y por ello converge a 4,2,1.

CONCLUSIÓN

Puesto que todo número entero positivo converge a 4,2,1 se concluye que la conjetura es correcta.

Teorema de Collatz: Para cualquier número natural n, si se aplica repetidamente la siguiente operación: dividir entre 2 si n es par, o multiplicar por 3 y sumar 1 si n es impar, se llega siempre al ciclo 4,2,1.

Francisco Colón Rosado