56Potestades

Solución de Problema 56.1.

1. Los granos se duplican de cuadrado en cuadrado a partir de $1 = 2^0$: cuadrado $k$ contiene granos $2^{k-1}$ (Definición 56.1). El cuadrado $64$ contiene $2^{63}$.

2. $S_1 = 1$, $S_2 = 1 + 2 = 3$, $S_3 = 3 + 4 = 7$, $S_4 = 7 + 8 = 15$, $S_5 = 15 + 16 = 31$: siempre uno menos que la siguiente potencia de $2$ ($2$, $4$, $8$, $16$, $32$). Conjetura: $S_n = 2^n - 1$.

3. Duplicar cada término de $S_n$ aumenta cada potencia en uno ($2 \times 2^{k} = 2^{k+1}$):

Restando la primera línea de la segunda, cada término de $2$ a $2^{n-1}$ aparece en ambos y cancela:

4. El total es $S_{64} = 2^{64} - 1$ granos. un el sexagésimo quinto cuadrado contendría granos $2^{64}$: todo el tablero lleva exactamente un grano menos que ese único cuadrado.

5. El primer medio contiene granos $S_{32} = 2^{32} - 1$. Todo el tablero contiene $2^{64} - 1$, por lo que el segundo medio contiene

(factorice $2^{32}$, usando $2^{32} \times 2^{32} = 2^{64}$, Teorema 56.3): exactamente $2^{32}$ veces la primera medio.

6. Por las reglas exponente, $2^{64} = 2^{4 + 60} = 2^4 \times \left(2^{10}\right)^6$. Desde $2^{10} = 1024 > 10^3$,

7. Más de $1.6 \times 10^{19}$ granos en $5 \times 10^{-2}$ g cada uno:

Dividiendo por $10^6$ g por tonelada: más de $8 \times 10^{11}$ toneladas — ochocientos mil millones de toneladas.

8. $\dfrac{8 \times 10^{11}}{8 \times 10^{8}} = 10^3$: el rey prometió al menos un mil años del de hoy cosecha mundial entera. (La leyenda dice que sus asesores le dijeron como mucho.)

9. $2^{19} = 2^9 \times 2^{10} = 512 \times 1024 = 524\,288 < 10^6$, mientras que $2^{20} = \left(2^{10}\right)^2 = 1024^2 = 1\,048\,576 > 10^6$. Entonces el exponente más pequeño es $n = 20$: veinte duplicaciones pasan del millón.

10. El pago del día $n$ es de $2^{n-1}$ céntimos (día 1: $2^0 = 1$). ahora

Entonces, el pago diario excede primero los centavos $10^8$ cuando $n - 1 = 27$: el día $28$.

11. $21 = 16 + 4 + 1$: pesos $16$, $4$ y $1$ g. $27 = 16 + 8 + 2 + 1$: pesos $16$, $8$, $2$ y $1$ g.

12. Por la pregunta 3, los pesos $1, 2, 4, 8$ juntos pesar $S_4 = 2^4 - 1 = 15$ g. Así que sin el peso $16$ g el El comerciante no puede pasar $15$ g: cualquier objetivo de $16$ g o más debe úsalo. Y un objetivo de $15$ go menos no debe usarlo, ya que el $16$ g de peso por sí solo ya supera el objetivo. La elección del Por lo tanto, el peso mayor es forzado. Lo que queda es un objetivo de como máximo $15$ g que se formará con $1, 2, 4, 8$ — y se repite el mismo argumento: $8$ es forzado (se usa si el resto el objetivo es $\geq 8$, de lo contrario no se usará, porque $1 + 2 + 4 = 7$), luego $4$ (porque $1 + 2 = 3$), luego $2$, luego $1$.

13. Tras las elecciones forzadas, el objetivo restante después de cada etapa es como máximo el total de los pesos restantes, entonces el proceso termina con resto $0$: cada objetivo desde $1$ hasta Se alcanza $31$. Y dado que cada elección en el camino fue forzada, ninguna otra selección de pesos puede alcanzar el mismo objetivo: el escritura de cada número desde $1$ hasta $31$ como suma de distinto Los poderes de $2$ existen y son único.

14. Los seis pesos suman $S_6 = 2^6 - 1 = 63$ g, y El mismo argumento de elección forzada cubre todos los objetivos desde $1$ hasta $63$ g. Para $45$: el objetivo es $\geq 32$, así que use $32$; permanece $13 < 16$, así que omita $16$; use $8$ (permanece $5$), use $4$ (permanece $1$), omita $2$, use $1$:

15. Eligiendo un $0$ o un $1$ en cada uno de los cuadrados $64$ equivale a elegir qué poderes $2^0, 2^1, \dots, 2^{63}$ incluir en un suma — exactamente el pesaje del comerciante con $64$ pesos. El número más pequeño que se puede almacenar es $0$ (todos los cuadrados en $0$); el más grande es el suma de todo los poderes, que es total del rey: $S_{64} = 2^{64} - 1$ (Parte I). por el argumento de elección forzada, se alcanza cada número entero intermedio exactamente una vez: una máquina de $64$-bit almacena precisamente todo números de $0$ a $2^{64} - 1$.