Demostrar que esta repetición siempre ciclos

Question

Si $n$ es un entero no negativo, vamos a $S_n=\{0, 1, 2, \dots, 2n+1\}$. Para $t\in S_n$ realizan repetidamente

 if t is even  
     t = t/2
 else
    t = (n + 1 + ⌊t/2⌋)

Parece que últimamente $t$ es igual a la inicialmente elegida número.

Por ejemplo, si $n = 15$ (por lo $S_{15} = \{0, 1, 2, \dots, 31\}$):

Para $t=1$;
$ 1 - 16- 8- 4- 2 - 1$

Para $t=3$;
$3 - 17 - 24 - 12 - 6 - 3$

Demostrar que esta propiedad es siempre cierto para cualquier $n$ $t$ donde $n\geq 0$ $0\leq t\leq (2n+1)$ . También, Para un valor dado de a $T$, ¿cómo puedo encontrar un número en $S_n$ que nunca será ser encontró al siguiente esta propiedad para $T$?

Answer 1

Sugerencia: Cada operación tiene un inverso, es decir, dado un número t, existe un único sucesor y para cada número, hay un único antecesor. Una vez que prueba esto, sigue el resto. Tenga en cuenta que los números se asignan a la primera mitad y las probabilidades se asignan a la segunda mitad.

Answer 2

Estás iterando una función $f: X \to X$ donde $X=\{ 0, 1, \dots, 2n+1 \}$ y considerando la órbita un $t\in X$ en $f$. $X$ Es un conjunto finito, la iteración debe repetir un número en $X$. Una vez que se repite ese número, ciclos para siempre. Así la órbita termina con un ciclo. Ahora, puesto que $f$ es inyectiva, la órbita debe ser todo el ciclo y así vuelve a la inicial $t$.

Answer 3

Ya tienes dos buenas respuestas a la primera pregunta, que su operación $$ t\rightarrow \begin{cases} t/2 & \text{if %#%#% is even}\\ n+1+\lfloor t/2\rfloor & \text{if %#%#% is odd} \end{casos} $$ generará una secuencia que con el tiempo volverá a lo que a partir de un valor de uso. Para tu segunda pregunta, Jyrki ha señalado que esto está estrechamente relacionado con el prefecto de la barajadura de la operación. Por ejemplo, con $t$, a partir de con $t$ su transformación produciría la secuencia $$ 3\rightarrow 9\rightarrow 12\rightarrow 6\rightarrow 3 $$ Consideremos el conjunto a $n=7$ como un mazo de 16 cartas, ordenado en un principio. Un perfecto fuera-shuffle, como se le conoce, lleva a que la cubierta, la divide en dos de igual tamaño pilas, $t=3$$S_7=\{0, 1, \dots, 15\}$, y luego se vuelve a montar en un nuevo pedido, alternativamente entrelazando los dos pilas, dándole $$ \begin{array}{cccccccccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ 0 & 8 & 1 & 9 & 2 & 10 & 3 & 11 & 4 & 12 & 5 & 13 & 6 & 14 & 7 & 15 \end{array} $$ donde la segunda fila es la tarjeta de los valores y la fila superior es de sus posiciones en la nueva cubierta de la orden. Podemos ver esta permutación como una indicación de que la tarjeta en la posición 3 se colocará en la posición 9, la tarjeta en la posición 9 va a ir en la posición 12 de la tarjeta en la posición 12 será colocado en la posición 6 y la tarjeta en la posición 6 se colocará en la posición 3, donde empezamos. Hacer esto para todas las tarjetas da un distinto ciclo de descomposición, $$ (0)(1\ 8\ 4\ 2)(3\ 9\ 12\ 6)(5\ 10)(7\ 11\ 13\ 14)(15) $$ No es coincidencia (y es bastante fácil de demostrar) que el $\langle\; 0, 1, 2, 3, 4, 5, 6, 7\;\rangle$ ciclo es exactamente el mismo que el de su transformación producida y que esto es en general.

Este, entonces, es de largo aliento manera de responder a su segunda pregunta: dado cualquier $\langle\; 8, 9, 10, 11, 12, 13, 14, 15\;\rangle$, que se repite iteración de su transformación se olvida de todos los valores, no en el ciclo que contiene a $(3\ 9\ 12\ 6)$. En particular, para cualquier $T$, el ciclo que empieza con $T$ va a perder valor $n$, el ciclo que empieza con $0$ va a faltar $2n+1$ y cualquier otro valor de partida te extraño tanto $2n+1$ $0$ (que, he de admitirlo, en realidad no necesita ninguno de los resultados que he mostrado, pero es demasiado bonita para no mencionar).