Collatz-ish Olimpiada Problema

Question

La siguiente es una Olimpiada de pregunta Competencia, por lo que espero tener una bonita solución:

Para un entero positivo $d$, definir la secuencia: \begin{align} a_0 &= 1\\ a_n &= \begin{cases} \frac{a_{n-1}}{2}&\quad\text{if }a_{n-1}\text{ is even}, \\ a_{n-1}+d &\quad\text{if }a_{n-1}\text{ is odd.} \end{casos} \end{align} Encontrar todos los valores de $d$ tal que $a_n=1$ algunos $n>0$.

Es obvio que $d$ debe ser impar, o bien la sucesión es monótona creciente. También, he numéricamente se observó que todos los valores impares de $d$ parece funcionar. ¿Alguien puede proporcionar una sugerencia en cuanto a cómo empezar a probar esto? Gracias!

Answer 1

Aquí es un esquema de un argumento. Nuestra conjetura es que la secuencia vuelve a $1$ cualquier $d = 2m-1$.

En primer lugar, parece preferible trabajar con la secuencia

$$b_0 = 1, \quad b_n = \begin{cases} \dfrac{b_{n-1}}2 & (b_{n-1}\text{ even}) \\ \frac{b_{n-1}+d}2 & (b_{n-1} \text{ odd})\end{cases}$$

en lugar de $a_n$ (la norma para ser probada sigue siendo el mismo).

Sugerencia: Demostrar que es suficiente para mostrar la $b_n\equiv 1 \pmod d$ algunos $n$. ¿Qué hace la secuencia de $b_n$ aspecto de mod $d$?

---

He incluido un inventario detallado a continuación (pero me temo que está regalando demasiado!)

Reivindicación 1: Tenemos $0<b_n<d$ todos los $n$.

-

Esto nos permite trabajar mod $d$ a partir de ahora, es decir, tenemos $b_n = 1$ si y sólo si $b_n\equiv 1 \pmod d$.

-

Reivindicación 2: $\frac12 \equiv m \pmod d$ donde $d=2m-1$ anterior.

-

Ahora observe que la secuencia es muy simple, cuando se consideran a $\pmod d$! Use esto para mostrar

-

Reivindicación 3: $b_n \equiv m^n \pmod d$

-

La reivindicación 3 implica que $b_k \equiv 1 \pmod d$ algunos $k$ (por qué?), así que por la Reivindicación 1 se sigue que $b_k=1$ para este $k$. $\square$

Answer 2

Es cierto que regrese a $1$ para todos los impares $d$, y el poder de la $2$ que usted consigue para la devolución es la siguiente potencia de $2$ sobre $d$.

Todos los números impares de la serie están a menos de $d$, lo que significa que debe de ciclo. Si $a_n$ es impar y a menos de $d$, $a_{n+1}$ está a menos de $2d$, e incluso, por lo que el siguiente impar es nuevo a menos de $d$.

Para tener un ciclo que no incluye a $1$ debe tener un número que puede ser alcanzado a partir de dos números diferentes-uno para entrar en el ciclo y uno para continuar. Pero esto es imposible-los números impares tienen que ser alcanzadas por la división por $2$, incluso los números mayor que $d$ tiene que ser alcanzado por adición, e incluso los números de menos de $d$ tiene que ser alcanzado por la división.

Answer 3

La pregunta ya ha "aceptado" la respuesta -, pero en el esquema siguiente puede ser útil para algún lector más tarde de todos modos.
El proceso iterativo de la división y la adición puede ser expresado como un conjunto de la operación.
Formulamos una transformación como $$ a_{k+1}={a_k+d \over 2^A }$$ and work on odd $a_k$ solamente. El valor de Una es determinado por el requisito, que es el más alto de Un tal que el resultado de la transformación es un entero impar.
La segunda transformación es, a continuación, $$ a_{k+2}={{a_k+d \over 2^A }+d \over 2^B} = {a_k \over 2^{A+B} } + d \cdot ({1 \over 2^{A+B} } + {1 \over 2^B} )$ $ y así sucesivamente.

Deje que el h posteriores exponentes de dichas transformaciones $a_0 \to a_h = 1$ se denota como $A,B,C,\ldots,G,H$ y su suma como $S$. A continuación, la transformación completa puede ser escrito como
$$ 1 (=a_h) = {a_0 \over 2^S} + d \cdot {(1+2^A + 2^{A+B} + \ldots + 2^{A+B+\ldots + G})\over 2^S} $ $ , y debemos tener un número entero de solución para
$$ 2^S = a_0 + d \cdot (1+2^A + 2^{A+B} + \ldots + 2^{A+B+\ldots +G})= a_0 + d \cdot x $$
donde S se encuentra (si es que hay una solución en $A,B,C,\ldots,H$!).

Por lo tanto podemos resolver por S tal que $ 2^S = a_0 \pmod d$ que, en general, debe ser hecho por la búsqueda (ver "discretas-logaritmo-problema").
Ahora aquí parece ser el problema crítico de la pregunta original: necesitamos saber estas combinaciones de $d$ $a_0$ que esta ecuación tiene una solución en absoluto. Posiblemente, este es también el núcleo del problema en su tarea de asignación, así que no voy a continuar aquí ( #1 véase a continuación)

Si de hecho hay una solución para algunos S , a continuación, calculamos el
$$ x = { 2^S - a_0 \over d} $$. Entonces los bits en la representación binaria de x corresponden a la "división por 2" de la formulación original del problema.

Por ejemplo, con $a_0 = 605, d=13$ encontré $2^S = a_0 + d \cdot x $ $ S=11, x=111$ $2048 = 605 + 13 \cdot 111 $

(#1): se Refiere a otro respuesta podríamos reformular esta como $ 2 = a_0^{1 \over S} \pmod d$ cual alude al concepto de "raíces primitivas (mod p)".