¿Por qué es $3$ el coeficiente multiplicativo en la conjetura de Collatz?

Question

¿Cuál es la importancia de la multiplicación de un número impar por $3$ y la adición de $1$, en vez de sólo la adición de $1$? Después de todo, si usted agregar $1$ a un número impar, entonces se convierte en un número.

Aquí es un ejemplo de la comparación de los coeficientes $3$ y $1$ (cualquier número puede ser utilizado para esto, pero para la simplicidad de uso $1$)

• El uso de $3n+1$ por la cantidad de $27$, existen alrededor de $115$ pasos.

• El uso de $n+1$ por la cantidad de $27$, hay 7 pasos.

Sé que siempre se puede reemplazar $3$ por cualquier variable que desea, pero ¿por qué Lothar Collatz hacen específicamente $3$? Hubo alguna razón especial (tal vez su número de la suerte)? O con cualquier otro número natural causar inestabilidad (que no quiero contar)?

Answer 1

Como se explica en Isaac Salomón respuesta sólo la adición de $1$ haría que el problema simple. Multiplicar por $2$ (u otro número) y la adición de $1$ no iba a funcionar, así que no hay nadie en $3$.

Uno podría preguntar la misma pregunta para $5$ en lugar de $3 dólares, o hay otras variantes, pero tenga en cuenta lo siguiente:

Si se asume un modelo de probabilidad, a continuación, en la multiplicación por $3$ en caso de que usted está en la siguiente situación: en "la mitad" de los casos (incluso $n$) dividir por $2$, en "la mitad" de los casos (impar $n$) usted toma $3n+1$, pero entonces usted está garantizado para dividir por $2$ así que efectivamente la situación es la siguiente:

• "la mitad" el tiempo se multiplica por $\frac{1}{2}$
• "la mitad" el tiempo se multiplica por (aproximadamente) de $\frac{3}{2}$ (como la combinación de $3n+1$, y el entonces obligado a $\frac{(3n+1)}{2}$).

El producto de estos dos $\frac{1}{2}$ y $\frac{3}{2}$ es $\frac{3}{4}$ y este es menor que 1, por lo que en el largo plazo, se esperaría una disminución.

Así, la heurística se sugiere una disminución en el largo plazo. (Este argumento es duro, pero uno podría hacer un poco más preciso. Sin embargo, creo que para tener una idea aproximada esto podría hacer).

Si haces lo mismo con $5$ (o algo aún más grande) en lugar de $3$, usted tendría $ \frac{1}{2}$ y $\frac{5}{2}$ en su lugar. Así que vas a tener $\frac{5}{4}$, que es mayor que $1$. Así, en el largo plazo, se esperaría un aumento.

De hecho, también se puede estudiar este problema; por lo que $5$ en lugar de los $3$, pero luego la situación es diferente en el que (se cree) tienen una secuencia de arranque que ir hasta el infinito y varios pequeños bucles. Así que la pregunta sigue siendo interesante, pero de alguna manera los cambios como entonces uno va a tener los valores que se escapan al infinito.

Más en general, existen numerosas Collatz-como los problemas que se consideran. Pero para algunos puede ser incluso demostrado que son formalmente indecidible.

Answer 2

Aquí hay una explicación posible: 3 es el único factor que, presumiblemente, permite a los efectos de la 3x+1 pasos y los efectos de la x/2 pasos para compensar estadísticamente. Como tal, Collatz algoritmo se encuentra en el límite de escapar hacia el infinito y de golpear 1 después de un (largo) tiempo. De ahí la emoción y, tal vez, la dificultad...

Para explicar la heurística, considerar que cada 3x+1 paso produce un entero par y es seguido por uno o varios x/2 pasos. Por cada $k\geqslant1$, la proporción de números enteros que requieren de $k$ de estos x/2 pasos es de $1/2^k$ por lo tanto el efecto global de estos x/2 pasos en un entero par elegido al azar, se debe multiplicar por un factor cuya media es $$ \frac12\cdot\frac12+\frac14\cdot\frac14+\cdots+\frac1{2^k}\cdot\frac1{2^k}+\cdots=\frac13. $$ Esto contrarresta exactamente, asintóticamente, el efecto de las únicas 3x+1 paso antes de una nueva sucesión de x/2 pasos que se produce.

Cabe mencionar que para realizar este argumento riguroso es una tarea de enormes proporciones. Por ejemplo, es obvio que el entero producida por la 3x+1 paso es distribuido uniformemente, asintóticamente. Por lo tanto, la heurística anterior es casi seguro falsas, y el reto es demostrar que no es falso lo suficiente como para invalidar la conjetura de que, para cada punto de partida, Collatz algoritmo hits el ciclo 1→2→4→1. Tenga en cuenta, finalmente, que la analogía con algunos de cero deriva de paseo aleatorio sugiere que el golpear el tiempo de este ciclo debe ser finitas, sí, pero por lo general de gran tamaño desde null recurrente de paseo aleatorio de aciertos de cada vértice después de casi seguramente finito, pero no integrable, tiempo aleatorio.

Answer 3

Si usted usa $n \n+1$, este siempre va a ir a $1$. Esto es debido a que, si usted comienza con un número $n$, hay tres posibilidades en cuanto a lo que podría suceder en los próximos dos vueltas. Si $n$ es impar, entonces

$$ n \a \frac{n+1}{2}$$

Si $n$ es par, se tiene

$$ n \a \frac{n}{2} + 1$$

o

$$ n \a \frac{n}{4}$$

Puedes comprobar por ti mismo que si $n>2$, este siempre se reduce el valor de $n$. A lo largo del tiempo, debemos llegar a $1$.

De forma heurística, el crecimiento de las fuerzas de $+1$ y la reducción de las fuerzas de $/ 2$ no son equilibrados. Además por $1$ no es tan potente como la división por $2$.

La importancia de la elección de $n \a 3n + 1$ es que la división por $2$ es equilibrada por multiplicar por $3$ y la adición de $1$, ya que en algunas ocasiones dividimos por $2$ más de una vez en una fila. Consulte ¿la respuesta de abajo para una explicación de cómo el equilibrio se produce.

Answer 4

Dado un conjunto de números, la mitad debe tener $\frac{3x+1}2$ aplicada y la mitad de $\frac x2$. Tanto $\frac{3x+1}2$ y $\frac x2$ son igualmente probables para producir números pares e impares. Así que la mitad de los números producidos por $\frac{3x+1}2$, entonces debe tener $\frac{3x+1}2$ aplicado otra vez y media $\frac x2$; asimismo, la mitad de los números producidos por $\frac x2$, entonces debe tener $\frac{3x+1}2$ aplicada y la mitad de $\frac x2$. Y así sucesivamente.

Considerar el efecto después de $n$ iteraciones. $\frac1{2^n}\binom{n}{k}$ de la cantidad inicial $\frac{3x+1}2$ aplica $n-k$ veces y $\frac x2$ aplica $k$ veces. Por lo tanto, dado un primer promedio del valor de $m$, se espera que el valor final sería $$ \frac1{2^n}\sum_{k=0}^n\binom{n}{k}\left(\frac32\right)^{n-k}\left(\frac12\right)^km=m $$ Por lo tanto, los $\frac{3x+1}2$ y $\frac x2$ mapas de lograr una constancia en el valor esperado de sus resultados.

---

Del mismo modo, el uso de la $\frac{x+1}2$ y $\frac x2$ mapas, obtendríamos un valor esperado de $$ \frac1{2^n}\sum_{k=0}^n\binom{n}{k}\left(\frac12\right)^{n-k}\left(\frac12\right)^km=\frac m{2^n} $$ Esto daría un abrupto descenso en el valor esperado.