Rompecabezas: Dejar caer bolas en el camino

Question

Un hombre tiene algunas pelotas en su bolsillo. Deje que el número de bolas en el bolsillo se $n$.(Considere el $n$ como un entero. Si cualquier valor decimal se produce, considere la posibilidad de su piso de valor. Por ejemplo, si $n$ = 2.6, entonces la tome como 2). Por cada milla que se ejecuta, él se queda con la mitad del número de bolas.

Por ejemplo, si inicialmente se tiene 10 bolas.

Después de ejecutar la primera milla de que va a tener 5 bolas.
Después de ejecutar la segunda milla, él va a tener 2 bolas.
Después de ejecutar el tercio de milla, él va a tener 1 balón.
Después de correr el cuarto de milla, él va a tener 0 pelotas.

Así que, toma 4 millas a perder todas las bolas.

Así que, ¿cuántos kilómetros tiene que ejecutar, con el fin de perder $n$ bolas.

Answer 1

Encontrar un patrón

Voy a empezar con un gráfico para tener una idea de un patrón:

Balls        Miles
0            0
1            1
2            2
3            2
4            3
5            3
6            3
7            3
8            4
9            4
10           4
11           4

Adivinar y comprobar en una fórmula

Usted podría notar un patrón ya. Cada vez que nos topamos con un número de bolas es una potencia de 2, el número de millas que se incrementa en uno. Vamos a hacer otro cuadro, con mi suposición de una fórmula:

Balls        Miles     log2(n)              Floor
1            1         log2(1)+1  = 1       1
2            2         log2(2)+1  = 2       2
3            2         log2(3)+1  = 2.58    2
4            3         log2(4)+1  = 3       3
5            3         log2(5)+1  = 3.32    3
6            3         log2(6)+1  = 3.58    3
7            3         log2(7)+1  = 3.81    3
8            4         log2(8)+1  = 4       4
9            4         log2(9)+1  = 4.17    4
10           4         log2(10)+1 = 4.32    4
11           4         log2(11)+1 = 4.46    4
12           4         log2(12)+1 = 4.58    4
13           4         log2(13)+1 = 4.70    4
14           4         log2(14)+1 = 4.81    4
15           4         log2(15)+1 = 4.91    4
16           5         log2(16)+1 = 5       5
17           5         log2(17)+1 = 5.09    5

Por tanto, la fórmula ⌊log2(n)+1⌋ parece un buen ajuste. Se me ocurrió log2(n) desde que deshace 2^n, que es el patrón me di cuenta en el primer gráfico.

Empecé intentando ⌊log2(n)⌋ y ⌈log2(n)⌉, pero me di cuenta de que estaban un poco fuera, así que he hecho algunos cambios hasta que finalmente llegué a ⌊log2(n)+1⌋.

Probarlo

Intente con decimales. Tratar con números más grandes. Yo lo hice en mi cabeza, sólo para asegurarse de que esta es realmente la respuesta correcta.

Answer 2

Suponga que$n$ está escrito en base$2$,

ps

Si$$n = \sum_{k = 0}^s a_k 2^k = \overline{a_s \ldots a_1 a_0}^2$ es el número de bolas después de$u_t$ millas, entonces$t$, y$u_0 = n$. Usted puede comprobar fácilmente que

$$ \begin{eqnarray*} u_0 &=& \overline{a_s \ldots a_2 a_1 a_0}^2 \\ u_1 &=& \overline{a_s \ldots a_2 a_1}^2 \\ u_2 &=& \overline{a_s \ldots a_2}^2 \\ \vdots & & \vdots \\ u_s &=& \overline{a_s}^2 \end {eqnarray *} $$

Así que tiene que ejecutar$u_{t+1} = \left\lfloor\frac{u_t}{2}\right\rfloor$ millas para perder todas las bolas (que es el número de dígitos de$s+1$ en base$n$). Ahora la desigualdad$2$ produce la fórmula$2^s \le n < 2^{s+1}$. Así que finalmente las respuestas son$s = \lfloor \log_2(n) \rfloor$.

Answer 3

Deje $a_k$ el número de bolas en el hombre del bolsillo después de $k$ km. Así, por ejemplo: $$a_0 = 10$$ $$a_1 = 5$$ $$a_2 = 2$$ $$a_3 = 1$$ $$a_4 = 0$$

La forma general para $a_k$ es: $$a_k = \left \lfloor \frac{a_{k-1}}{2} \right \rfloor$$

Por lo tanto, el rompecabezas puede ser fácilmente resuelto en O(n) tiempo (por programación)...

Para probarlo en tiempo constante, usted necesita encontrar el número de veces que se puede realizar la división entera por 2 antes de llegar a 0. Esto me hace pensar que podría ser algo similar a $log_2(n)$.

Una comprobación rápida con un programa de muestra de que la computación $$\lceil \log_2(n) \rceil$$ devuelve la respuesta correcta.

EDITADO: Como se señaló en los comentarios, el de arriba, no se devuelve la respuesta correcta para las potencias de 2. La respuesta correcta es: $$\lfloor \log_2(n) \rfloor + 1$$

Answer 4

La respuesta correcta es diez.

Answer 5

Para intergers mi conjetura es$$\lfloor \log_2 n +1\rfloor$ $