Los usos de "Collatz inducción"?

Question

La conjetura de Collatz es equivalente a la siguiente "principio de inducción":

Si $P(0) \de la tierra P(1) \de la tierra (\forall{x} P(3 \cdot x + 2) \implica P(2 \cdot x + 1)) \de la tierra (\forall x P(x) \implica P(2 \cdot x))$,

entonces $\forall x P(x)$.

Me pregunto si hay alguna de las declaraciones que se pueden probar usando este principio, que no son obvias y no son, evidentemente, equivalente a la conjetura de Collatz sí mismo? No estoy tan interesado en los problemas abiertos (implicaciones de la conjetura de Collatz), en lugar de algo que puede ser fácilmente demostrable de una manera diferente, pero también tiene una prueba simple de usar "Collatz de la inducción".

He probado algunas de las declaraciones de $P(x)$ como "existe un número de la forma $2^a \cdot 3^b$ dentro de una distancia de $f(x)$ de $x$" pero yo no puedo hacer este trabajo.

Answer 1

Aquí es el mejor que soy capaz de hacer hasta ahora, después de mi idea en los comentarios:

Deje que $P(x)$ ser la afirmación de que cualquier conjunto de $x$ enteros pueden ser ordenados en una secuencia de $s_i$ con $1 \le i \le x$ que si $a \lt b \lt c$, entonces $s_a + s_b \ne s_c$.

Supongamos $S$ es un conjunto que contiene $2 \cdot x$ enteros. Tenemos $S = V \taza de W$, donde $V$ contiene el valor de $x$ elementos más pequeños de $S$ y $W$ contiene el valor de $x$ elementos mayores de $S$. Si $V$ y $W$ y cada uno corresponde a una secuencia con la propiedad, a continuación, podemos hacer una secuencia de $S$ iniciando con $W$'s de la secuencia y anexando $V$'s de la secuencia. Por lo que $\forall x P(x) \implica P(2 \cdot x)$.

Si un conjunto pueden ser ordenados de tal manera que puede ser que todos sus subconjuntos: para encontrar una secuencia de un conjunto después de haber eliminado algunos elementos, basta con quitar esos mismos elementos del conjunto original de la secuencia. Así que si $y < x$ entonces $P(x) \implica P(y)$, y en particular, esto le da $\forall x P(3 \cdot x + 2) \implica P(2 \cdot x + 1)$.

Por lo tanto, si la conjetura de Collatz es cierto, $\forall x P(x)$.

Ahora bien, esto es decepcionante porque es simplemente un largo aliento manera de decir ordenar el conjunto de mayor a menor, también resulta mucho más que $P(3 \cdot x + 2) \implica P(2 \cdot x + 1)$. Tal vez un punto de partida para un mejor ejemplo.