eliminación alternativa de enteros entre 1 y 128, ¿cuál es la última?

Question

Matemáticas pregunta:

Escribir todos los números entre 1 y 128 en línea. A continuación, comience a eliminar la los números de esta manera: borrar el número 1, no 2, eliminar 3, deje de 4 y así sucesivamente. Ir hasta el final de la línea y, a continuación, comience a eliminar en el otra dirección desde el primer número no se eliminan, a continuación, salir de la segundo y así sucesivamente. Seguir así hasta que sólo hay un número a la izquierda. ¿Cuál es este número?

Ahora, tengo una solución fácil para este problema. El punto es que he leído una solución diferente que parece más limpio y muy interesante, pero lo que no entiendo.

Aquí la solución que no entiendo:

Deje $x_k$ ser el último número restante después de proceder como se describe con los números entre el$1$$2^k$. Si usted proceder con los números entre el$1$$2^{k+1}$, después de la primera iteración sólo se quedan en el $2^k$ números, y el siguiente $k$ iteraciones seleccione el incluso el número en la posición $x_k$ a contar desde la parte inferior ($x_k^{th}$ número de la parte inferior). Así tenemos $$ x_{k+1}=2(2^k-x_k+1)=2^{k+1}-2x_k+2 $$ Sabiendo que $x_0=1$, podemos obtener fácilmente $x_1$, $x_2$, ..., $x_7$. Por lo $x_7=86$ es la solución.

Ahora mi problema es cómo motivar el paso de$2^k$$2^{k+1}$. Alguna pista?

Answer 1

Hagamos los pasos aquí de forma explícita. Ya que voy a usar la computadora de la ayuda, voy a hacer el trabajo en su lenguaje la escritura de los números en representación binaria. La lista inicial es:

  1 ~ 00000001
  2 ~ 00000010
  3 ~ 00000011
  4 ~ 00000100
  5 ~ 00000101
  6 ~ 00000110
  7 ~ 00000111
  8 ~ 00001000
  9 ~ 00001001
::::::::::::::: many other numbers
119 ~ 01110111
120 ~ 01111000
121 ~ 01111001
122 ~ 01111010
123 ~ 01111011
124 ~ 01111100
125 ~ 01111101
126 ~ 01111110
127 ~ 01111111
128 ~ 10000000

El último dígito es $1,0,1,0,1,0,$... Después de la primera operación de eliminación no es ningún número a la izquierda que termina en $1$, exactamente las mismas que se quedan números que terminan en $0$. Vamos a escribir de forma explícita.

  2 ~ 00000010
  4 ~ 00000100
  6 ~ 00000110
  8 ~ 00001000
::::::::::::::: many other numbers
120 ~ 01111000
122 ~ 01111010
124 ~ 01111100
126 ~ 01111110
128 ~ 10000000

OK. Ahora partimos de la final. El último dígito es un cero. Nos olvidamos de ella. El forelast, a partir de la final, $0,1,0,1,0,1,\dots$ y así sucesivamente. Debemos eliminar todos los números de tener un forelast cero. La lista es, pues, después del segundo paso

  2 ~ 00000010
  6 ~ 00000110
::::::::::::::: many other numbers
122 ~ 01111010
126 ~ 01111110

Y no son sólo números que terminan en 10 se mantuvo. Nos olvidamos de la 10 y reinicie el procedimiento. Borramos el primer número en la lista, tiene el patrón *010, por lo que podemos eliminar todos los números con este patrón. Solo quedan los números de tener el patrón *110. Así nota de la asimetría. En la primera vuelta-y-vuelta operación de eliminación de el primer número se terminó en uno. Ahora es un cero en la posición en la que cuenta. El resto de los números son así

  6 ~ (0)0000110
::::::::::::::: many other numbers
126 ~ (0)1111110

Ahora el patrón para el primer número y el último número es "el mismo", sólo ceros, resp. sólo para ser eliminado en la posición que le da la señal. Repetimos y completa:

• Después de 1.san supresión $\to$ seguimos con el patrón *0.
• Después de 2.nd supresión $\leftarrow$ seguimos con el patrón *10.
• Después de 3.rd supresión $\to$ seguimos con el patrón *1 10.
• Después de 4.th supresión $\leftarrow$ seguimos con el patrón *01 10. A partir de ahora en la vuelta-y-vuelta eliminaciones reemplace * por *01 por el mismo argumento. Así que...
• Después de 5.th supresión $\to$ seguimos con el patrón *1 01 10.
• Después de las 6.th supresión $\leftarrow$ seguimos con el patrón *01 01 10.
• Después de 7.th supresión $\to$ seguimos con el patrón *1 01 01 10.

Hay sólo un número, de esta forma en la lista, es

01 01 01 10

Y el ganador es 01 01 01 10${}_2$, que es el decimal $2+4+16+64 = 20+66=86$.

Answer 2

La relación de recurrencia \begin{align*} x_{k+1}&=\color{blue}{2}(2^k-x_k+1)\qquad\qquad\qquad (k\geq 0)\tag{1}\\ x_0&=1 \end{align*} pueden ser derivados por considerar dos situaciones diferentes.

Primer juego: $1,2,\ldots,2^k$:

• En este juego que vamos a empezar con los números de $1,2,\ldots 2^k$. Jugamos el juego hasta que después de $k$ pasos el elemento $x_k\in\{1,2,\ldots,2^k\}$.

Ahora podemos relacionar la solución de $x_k$ desde el primer juego con la solución de $x_{k+1}$ en un juego que consta de los números $1,2,\ldots,2^{k+1}$.

Segundo juego: $1,2,\ldots,2^{k+1}$:

• El primer paso es eliminar todos los números impares, dejando $2^k$ números de $2,4,\ldots,2^{k+1}$.

• Ahora estamos en una situación muy similar a la del primer juego. Tenemos $2^k$ números, pero hay dos diferencias. Cada elemento es el doble de tamaño y empezamos desde el otro lado con el elemento $2^{k+1}=2\cdot 2^k$ ya que este es el segundo paso en este juego.

  • Tenemos $2^k$ números, es decir,$2,4,6,\ldots,2^{k+1}$, cada número de dos veces tan grande como en el primer juego. Esto se explica por el factor de $\color{blue}{2}$ (1) marcado en azul.

  • La posición $x_k$, lo que derivó en el primer juego, cuando a partir de $1$ tiene que ser cambiado con $2^k-x_k+1$ que es la posición correspondiente al iniciar desde el otro lado.

Esto explica la recurrencia de la relación (1) dar: \begin{align*} (x_k)_{k\geq 0}=(1,2,2,6,6,22,22,\color{blue}{86},86,342,342,\ldots) \end{align*}

Answer 3

La representación binaria método usado en otras obras más suavemente si lo primero que restar $1$ de cada número así que ahora van de $0$ $127$-- mejor representa como $0000000$ $1111111$base dos. Ahora los bits en cada lugar de alternar entre los $0$ $1$ con igual longitud de los bloques de bits idénticos en cada lugar de valor (un número de bloques en los bits, de dos bloques de números en los dos bits, etc). Esto garantiza que todos los números que se retiró en el primer paso ha $0$ en los bits, los retirados en el segundo paso (en orden inverso) ha $1$ en los dos bits, todos los números que se retiró en el tercer paso ha $0$ en los cuatro bits, y así sucesivamente en esta alternancia de la moda. El número con el que sobreviven los bits después de siete eliminaciones es $1010101_2$. La adición de $1$ a restaurar el original de la secuencia de los números de la hora de traducir y volver a la base diez da $86$ como el ganador.