¿Cuál es la posición del ratón superviviente?

Question

Tengo esta pregunta que creo que puede ser muy interesante para todos los amantes de las matemáticas.

Un gato atrapado $n$ (enteros) y los puso en fila, los numeró del 1 al $n$ , de izquierda a derecha. Comienza a comer todos los demás ratones, empezando por el ratón de la primera posición, es decir, 1, 3, 5 ... (todos los ratones en las posiciones Impares habrán desaparecido). A continuación, comienza una nueva iteración, sin importar si hay un ratón superviviente al final de la línea, volviendo a la izquierda y comiendo cada uno de los ratones de nuevo, empezando siempre con el primer ratón superviviente de la iteración anterior.

Hasta que quede un solo ratón.

¿Cuál es la posición del ratón superviviente en la secuencia original de 1 a n?

Answer 1

Las otras respuestas son correctas, pero permíteme ofrecer una forma alternativa de verlo. Supongamos que tienes 7 ratones, por ejemplo. Numéralos en binario y recorre las iteraciones del gato:

001 -> 001
010 -> 010 -> 010
011 -> 011
100 -> 100 -> 100
101 -> 101
110 -> 110 -> 110
111 -> 111

En la primera ronda el gato se come todos los ratones que terminan en 1, de modo que sólo quedan los que terminan en 0. En la segunda ronda el gato se come todos los ratones que terminan en 10, de modo que sólo quedan los que terminan en 00. Y así sucesivamente. (Como alternativa, se puede eliminar un cero final de todos los ratones después de la primera ronda e iterar comiendo siempre ratones que terminen en 1).

Es decir, si un ratón tiene $k$ ceros al final, sobrevivirá exactamente $k$ rondas. El último superviviente es el que tiene la mayor cantidad de ceros al final.

El número de ceros finales en el conjunto $\{1,\dots,n\}$ siempre es maximizado por una potencia de dos y el maximizador es único. (Por favor, pregunta si quieres una prueba de esta afirmación. También podría funcionar como una pregunta aparte). La mayor potencia de dos que no supera $n$ es de hecho $a_n = 2^{\lfloor \log_2 n \rfloor}$ como otros han señalado.

Answer 2

Si $n$ es par, entonces tenemos algo como $[1, 2, 3, 4, 5, 6]$ convirtiéndose en $[2, 4, 6]$ que es lo mismo que jugar un nuevo juego de tamaño $n/2$ y multiplicando la respuesta de $[1, 2, 3]$ por $2$ .

Si $n$ es impar, entonces tenemos algo como $[1, 2, 3, 4, 5]$ convirtiéndose en $[2, 4]$ que es lo mismo que jugar un nuevo juego de tamaño $(n-1)/2$ y multiplicando la respuesta de $[1, 2]$ por $2$ .

Podemos simplificar los dos casos en uno solo diciendo $n$ se convierte en $\lfloor\frac{n}{2}\rfloor$ en su lugar. Por lo tanto:

$S(n) = 2S(\lfloor\frac{n}{2}\rfloor)$ donde $S(1) = 1$

Así que $S(n) = 2^{\lfloor \log_2(n)\rfloor}$

Esto también es lo mismo que encontrar el bit más significativo de $n$ (es decir, la mayor potencia de $2$ menor o igual a $n$ ). Escriba $n$ en binario y luego poner todo en $0$ excepto la parte inicial.

Answer 3

Siguiendo la pista de Arthur: después de la $k$ de la ronda, los únicos ratones que quedan son los múltiplos de $2^{k+1}$ . Esto se debe a que en el $k$ El gato se come todos los ratones que no son divisibles por $2^k$ .

Dejemos que $2^k$ sea la mayor potencia de $2$ es decir $\le n$ es decir $k=\lfloor \log_2 n\rfloor$ .

Entonces el último ratón es el más grande divisible por $2^k$ es decir $m2^k$ donde $m=\lfloor n/2^k\rfloor$ .

Entonces, el último ratón es $$m2^k = \lfloor n/2^k\rfloor 2^k = \lfloor 2^{\log_2 (n) - k}\rfloor 2^k = \lfloor 2^{\log_2 (n) - \lfloor \log_2 n\rfloor}\rfloor 2^{\lfloor \log_2 n\rfloor} = 2^{\lfloor \log_2 n\rfloor},$$ donde utilizamos el hecho de que $\log_2(n) - \lfloor \log_2 n \rfloor \in [0,1)$ .

Answer 4

Se puede utilizar la recursividad para resolver estas cuestiones. Sea $a_{n}$ sea el número del último ratón que sobrevive cuando hay $n$ para empezar.

• Si $n$ es impar, $n = 2k+1$ Entonces, después de una ronda, nos quedamos con $k$ ratones, $2, 4, \ldots, 2k$ y hacemos el mismo procedimiento. El ratón que queda es $2a_k$ . Así, $$ a_{2k+1} = 2a_k. $$

• Si $n$ está en paz, $n = 2k$ Entonces, después de una ronda, nos quedamos con $k$ ratones de nuevo, los mismos. Así, $$ a_{2k} = 2a_k. $$

Se deduce por inducción que $$ a_n = 2^{\lfloor \log_2 n \rfloor}. $$