Dos amigos tienen$2$ natural escrito en la frente. Uno es$2$ multiplicado por el otro +$1$. Pueden levantar sus manos.

Question

El problema:

Dos amigos tienen $2$ natural escrita en su frente. Uno de ellos es $2$ veces los otros + $1$. Vamos a llamarlos $X$ e $2X + 1$. Ellos tienen que venir para arriba con una estrategia para adivinar su propio número, y que puede levantar la mano o no (comunicarse $1$ poco de información para cada uno de los otros).

Así, por ejemplo, si usted ve $23$ a sus amigos en la frente, usted tiene que decidir por sólo comunicarse $1$ poco de información si usted tiene o no $11$ o $47$ sobre su frente.

Mi intento:

(Vamos a llamar el número de cada jugador ve en su amigo frente de $S$.)

Paso $1$. Si el número que se ve es, incluso, inmediatamente dicen "$2S+1$ es en mi frente!"

(Obviamente $2X+1$ no se puede aun, así que estamos bien hasta ahora.)

Paso $2$. Si el número que se ve es de la forma $4n+1$, decir "$2S + 1$ es en mi frente!"

(Esto también funciona, ya que si $2X+1=4n+1 \ \rightarrow\ X=2n$, que ya estaba contemplada en el Paso $1$. Esto significa que los ve $S = 4n+1 \ne 2X+1$, en lugar de $S = 4n+1=X$, así que nuestro número debe ser $2X+1$.)

Aquí es donde se vuelve problamatic, ya que:

• Si $X=4n+3 \ \rightarrow\ 2X+1=8n+7 \stackrel{also}{=} 4\hat{n}+3 \quad (\hat{n} = 2n+1)$
• No sólo eso, sino que si $X=8n+7 \ \rightarrow\ 2X+1=16n+15 \stackrel{also}{=} 8\hat{n}+7 \quad (\hat{n} = 2n+1)$

También he tratado de divisibilidad por $3$, $5$ e $6$, pero ninguno de los que llevan a una solución, por ejemplo:

• Si $X=3n \ \rightarrow\ 2X+1 \equiv 1 \ (\text{mod}\ 3)$ e $X=3n+1 \ \rightarrow\ 2X+1 \equiv 0 \ (\text{mod}\ 3)$, lo que está bien, si $S=3n$ o $S=3n+1$, se puede determinar cuál es tu número, ...
• Pero si $X=3n+2 \ \rightarrow\ 2X+1=6n+5=3\hat{n}+2 \quad (\hat{n} = 2n+1)$, por lo levantando la mano cuando $S=3n+2$ no funciona bien.

No creo que estoy lejos de ser la solución, pero simplemente no puedo entenderlo, así que cualquier ayuda será muy apreciada!

Answer 1

La función de $X\mapsto 2X+1$ particiones de los enteros positivos en cadenas, como a continuación. Cada cadena se inicia con un número par, o uno, y cada número $X$ está unido por una flecha a $2X+1$. Es de conocimiento común a los dos jugadores que la cadena se encuentran. Además, todas las cadenas tienen la misma estructura. Por lo tanto, vamos a suponer sin pérdida de generalidad que los jugadores están en el indicado de la cadena.

\begin{align} &\boxed{1\to 3\to 7\to 15\to 31\to \dots} \\ &2\to 5\to 11\to 23\to47\to \dots \\ &4\to 9\to 19\to 39 \to 79\to \dots \\ &6\to 13\to 27\to 55\to 111\to \dots \\ &8\to 17\to 35\to 71\to 142\to \dots \\ &\hspace{3cm}\vdots \end{align} El Color de los elementos de la cadena alternativamente rojo y negro en bloques de dos, como se muestra. Cada jugador se comunica el color que ven al otro jugador usando su mano subir. Esto permite a cada jugador para deducir su número. Por ejemplo, si había de $15$ y su amigo hubiese $31$, entonces usted podría estar seguro de si su número se $15$ o $63$. Pero una vez que tu amigo dice que su número es de color rojo, usted sabe que su número es $15$. $$ 1\3\a \color{red}{7}\\color{red}{15}\31\63\a \color{red}{127}\\color{red}{255}\511\a \dots $$ El color puede ser descrito de forma explícita. La función de inversión de $X\mapsto 2X+1$ es $X\mapsto (X-1)/2$, el cual es definido como el tiempo $X$ es impar y mayor que $1$. Si se aplica la asignación inversa de una y otra para el número que ve, entonces usted acabará finalmente con un número par (o uno). Si tarda $n$ pasos para hacer esto, entonces usted debe levantar la mano si $\lfloor n/2\rfloor$ es incluso.