¿Dónde está el fallo de esta "prueba" de la Conjetura de Collatz?

Question

Editar

He resaltado la zona de la prueba en la que se cometió el error, para que cualquiera pueda tropezar con ella en el futuro. Es el mismo error, cometido en dos lugares:

Esto ha demostrado la conjetura de Collatz para todos los números pares

Se ha demostrado que la conjetura de Collatz es válida para $N+1$ cuando $N+1$ es incluso nunca se demostró que se mantuviera para todo números pares sólo ese único número par.

[La conjetura de Collatz es válida para todos los números Impares para los que $N-1$ es un múltiplo de $4$

Lo mismo que antes: se ha demostrado que la conjetura de Collatz se cumple para $N+1$ si $N+1$ es de la forma $4k+1$ . Nunca se demostró que se mantuviera para todo números de esta forma sólo ese único número.

Para que mi prueba sea válida, tendría que demostrar que la conjetura de Collatz se cumple para $N+1+4j = 4k+1$ (cada cuarto número después de $N+1$ ) para, como mínimo, $N+1+4j < 1.5N+2$

Puesto original

Estuve cerca de una hora pensando en la Conjetura de Collatz y me topé con lo que se siente como una prueba... pero llegué a ella con demasiada facilidad para haberlo hecho todo bien.

1. lo obvio que todo el mundo ya se ha dado cuenta:

Supongamos que la conjetura de Collatz se cumple para todos los números $1...N$

Podemos demostrar trivialmente la Conjetura de Collatz para algunos casos base de $1,$ $2,$ $3,$ y $4$ . Esto es suficiente para seguir adelante.

2. Y aún más obvio:

1. Si $N$ es impar, $N+1$ es incluso
2. $(N+1)/2 < N$ para $N > 3$
3. Por la hipótesis de inducción, la conjetura de Collatz se cumple para $N+1$ cuando $N+1 = 2k$

3. Ahora la última obviedad:

1. Si $N$ está en paz, $N+1$ es impar
2. Si $N+1$ es impar, el siguiente número de la serie es 3(N+1)+1
3. Desde $(N+1)$ es impar, $3(N+1)+1$ es incluso
4. El siguiente el siguiente número de la serie es $(3(N+1)+1)/2$
5. Esto se simplifica a: $(3N + 4)/2 = 1.5N + 2$

4. Ahora la primera parte complicada:

1. Si $N$ es un múltiplo de $4$ :
2. $1.5N$ es un múltiplo de $6$ y por lo tanto, incluso. $1.5N + 2$ es, por lo tanto, incluso
3. El siguiente siguiente siguiente número de la serie es por tanto $(1.5N+2)/2$
4. Esto se simplifica a $0.75N + 1$
5. Esto es menos que $N$ para $N > 4$
6. Por la hipótesis de inducción, la conjetura de Collatz se cumple para $N+1$ cuando $N+1 = 4k + 1$

Esto ha demostrado la conjetura de Collatz para todos los números pares y todos los números Impares para los que $N-1$ es un múltiplo de $4$ ... Ahora para hacer volar sus mentes:

5. Romper con las ecuaciones formales en patrones y demás, ya que no sabía cómo formalizar esta parte con símbolos matemáticos:

1. Ahora sabemos que un número $N+1$ sólo puede violar la conjetura de Collatz si $N$ es incluso y no es un múltiplo de $4$ . En otras palabras, la única manera de que un número pueda potencialmente violar la Conjetura de Collatz es si es de la forma $N+1 = 4k - 1$
2. Esto limita nuestros números a probar a 2+1, 6+1, 10+1, 14+1, 18+1, 22+1, etc. (nota que escribí estos números en " $N+1$ "para que sea más sencillo aplicar el formato $1.5N+2$ acceso directo)
3. Aplicaremos nuestro $1.5N + 2$ acceso directo a un puñado de estos números:

2  -> 3+2  = 5  (4 +1) -- 4 is a multiple of 4 (duh)
6  -> 9+2  = 11 (10+1)
10 -> 15+2 = 17 (16+1) -- 16 is a multiple of 4
14 -> 21+2 = 23 (22+1)
18 -> 27+2 = 29 (28+1) -- 28 is a multiple of 4
22 -> 33+2 = 35 (34+1)
26 -> 39+2 = 41 (40+1) -- 40 is a multiple of 4
30 -> 45+2 = 47 (46+1)
34 -> 51+2 = 53 (52+1) -- 52 is a multiple of 4
38 -> 57+2 = 59 (58+1)
42 -> 63+2 = 65 (64+1) -- 64 is a multiple of 4
46 -> 69+2 = 71 (70+1)

4. Cada dos líneas sabemos automáticamente que la Conjetura de Collatz se cumple, porque hemos dado con un número que puede expresarse como $4k+1$
5. Observando las filas "conservadas", podemos ver que todo lo que necesitamos probar ahora son números de la forma N+1 = 8k - 1 (en otras palabras, las filas donde N = 8k - 2 -- 6, 14, 22, etc.)

6. Y por último, recurre a esta solución dibujando una nueva tabla y en lugar de calcular el valor "siguiente siguiente", calcula el valor "siguiente siguiente siguiente":

"Siguiente siguiente" valor = 3(1,5N + 2) + 1 = 4,5N + 7

El valor "next^4" es la mitad de esto -- 2.25N + 3.5

6  -> 27 +7 = 34  -> 17  (16 +1) -- 16 is a multiple of 4
14 -> 63 +7 = 70  -> 35  (34 +1)
22 -> 99 +7 = 106 -> 53  (52 +1) -- 52 is a multiple of 4
30 -> 135+7 = 142 -> 71  (70 +1)
38 -> 171+7 = 178 -> 89  (88 +1) -- 88 is a multiple of 4
46 -> 207+7 = 214 -> 107 (106+1)
54 -> 243+7 = 250 -> 125 (124+1) -- 124 is a multiple of 4
62 -> 279+7 = 286 -> 143 (142+1)

Cada dos líneas sabemos automáticamente que la Conjetura de Collatz se cumple, porque hemos dado con un número que puede expresarse como 4k+1

Ahora sabemos que un número sólo puede violar la Conjetura de Collatz si es de la forma N+1 = 16k - 1 ... Recurrir de nuevo:

El valor de "next^5" es 3(2.25N + 3.5) + 1 = 6.75N + 11.5

El valor de "next^6" es (6,75N + 11,5)/2 = 3,375N + 5,75

14   -> 53  = 52  + 1 -- 52 is a multiple of 4
30   -> 107 = 106 + 1
46   -> 161 = 160 + 1 -- 160 is a multiple of 4
62   -> 215 = 214 + 1
78   -> 269 = 268 + 1 -- 268 is a multiple of 4
94   -> 323 = 322 + 1
110  -> 377 = 376 + 1 -- 376 is a multiple of 4
126  -> 431 = 430 + 1

Ahora sabemos que un número sólo puede violar la Conjetura de Collatz si es de la forma N+1 = 32k - 1

En este punto, está surgiendo rápidamente un patrón:

1. En primer lugar, un número sólo podría violar la Conjetura de Collatz si fuera de la forma N+1 = 4k - 1
2. A continuación, se demostró que un número sólo podía violar la Conjetura de Collatz si era de la forma N+1 = 8k - 1
3. A continuación, se demostró que un número sólo puede violar la Conjetura de Collatz si es de la forma N+1 = 16k - 1
4. Ahora, se ha demostrado que un número sólo puede violar la Conjetura de Collatz si es de la forma N+1 = 32k - 1

He continuado este proceso (construyendo recursivamente esta tabla y eliminando las filas que sé que no pueden violar la Conjetura de Collatz ya que se pueden expresar como 4k+1 ) hasta 512k - 1 a mano.

No sé cómo formalizar este proceso final en notación matemática, pero creo que demuestra al menos un método viable para demostrar la Conjetura de Collatz. Por cada dos pasos que demos en la serie de Collatz, aumentamos la potencia en nuestra definición de "únicos números que podrían violar la conjetura". Por lo tanto, para una potencia arbitrariamente grande sabemos que la conjetura seguirá siendo válida.

Por diversión

Para ayudarme a construir estas tablas, he creado el siguiente script:

# Increment this variable to recurse one level deeper
test = 1

### No need to edit below here, but feel free to read it ###
depth = 2 * test
step = 2 ** (test + 1)
start = step - 1

for x in range(0, 20):
    num = start + x * step
    _num = num
    _depth = depth
    while _depth > 0:
        if _num % 2 == 0:
            _num = _num / 2
        else:
            _num = 3 * _num + 1
        _depth -= 1
    text = ""
    if (_num - 1) % 4 == 0:
        text = "-- multiple of 4"
    print "%s: %s = %s + 1 %s" % (num - 1, _num, _num - 1, text)

Answer 1

Hay un problema sutil con tu argumento de inducción: estás asumiendo que la conjetura de Collatz es válida para todos los enteros $\leq n$ y luego quiere demostrar que es válida para $n+1$ (inducción fuerte). Hasta ahora, todo va bien.

Luego se demuestra que para algunos casos ( $n+1$ incluso, o de la forma $4k+1$ ) que la conjetura de Collatz se cumple por la hipótesis inductiva. Bien.

A continuación, intenta argumentar que para algunos números de la forma $4k+3$ , al final se encuentra con un número de la forma $4k+1$ para que la conjetura de Collatz se mantenga... no tan rápido. No has demostrado que la conjetura de Collatz sea válida para todo enteros de la forma $4k+1$ . Ha demostrado que es cierto para $n+1$ Si $n+1$ resulta ser de esa forma, y has asumido que es cierto para todos los números de esa forma $\leq n$ (por la hipótesis inductiva) pero no has demostrado que Collatz es válido para números de la forma $4k+1$ que son mayores que $n+1$ .

Answer 2

El error es:

Ahora sabemos que un número $N+1$ sólo puede violar la conjetura de Collatz si $N$ es par y no es múltiplo de $4$ .

Eso no lo sabemos. Lo que sabemos es que si hay números que violan la conjetura de Collatz, entonces el número más pequeño es $1$ algo más que algo uniforme y no un múltiplo de $4$ . Pero puede haber contraejemplos más grandes que no se parecen a eso.

Así es como funciona la prueba por inducción: si hay un contraejemplo, debe haber un contraejemplo más pequeño, es decir, la conjetura es falsa para algún número $n+1$ pero es cierto para todos los números $\leq n$ . Entonces podemos intentar demostrar que esto no puede suceder. Pero si no podemos deducir una contradicción de esto, sino sólo obtener algunas condiciones que $n+1$ tiene que satisfacer, entonces estas condiciones sólo se cumplen para el contraejemplo más pequeño, no para todos los contraejemplos, ya que tuvimos que suponer que $n+1$ era el contraejemplo más pequeño para poder hacer la deducción.

Answer 3

Además de los comentarios anteriores, hay otra suposición implícita que debe abordarse para que esta prueba funcione: La consideración de otros bucles.

El peligro de este defecto es evidente aquí: Utilicé el método descrito en su prueba, asumiendo $4k+1$ define los números que convergen a 1 y así demostrar la Conjetura de Collatz. Extendí esta fórmula a la regla de Collatz modificada $3x+5$ ya que la única diferencia es el $+5$ en lugar de $+1$ . (Me he abstenido de utilizar $3x+3$ porque su estructura es completamente diferente a la de $3x+1$ y $3x+5$ .)

Para ello, he utilizado $4k+5$ para su adecuación, ya que el $n/2$ la norma se sigue aplicando para $3x+5$ . A continuación, miro la siguiente secuencia generada:

9,17,21,25,29,...

Inmediatamente se desencadenan los problemas. El 9 pasa al 32, que pasa al 1, que completa el bucle 8-4-2-1.

El 13 va al 11, que va al 38, que luego se encuentra en el bucle del 19. [19-62-31-98-49-152-76-38-19]

El 17 va al 7, que va al 13. El 21 va al 17 que va al 7... ¿tal vez haya un patrón aquí?

25... arruina todo el nuevo patrón. Va a 80, que es un tiro recto al bucle 5 [20-10-5-20].

¿Y la 29? En el centro del bucle 23. [29-92-46-23-74-37-116-58-29].

Por lo tanto, afinando esta prueba para demostrar que $3x+1$ no vagará hasta el infinito es completamente posible, sin embargo, asumir que cada número alcanza una potencia de 2 en algún momento puede llevar a más problemas. Especialmente porque una secuencia que vaga hasta el infinito para la Conjetura de Collatz nunca debe alcanzar una potencia de 2 como $5x+1$ parece demostrar con su aparentemente infinita secuencia 7.