56Machten

Oplossing van Probleem 56.1.

1. De korrels verdubbelen van veld tot veld vanaf $1 = 2^0$: veld $k$ bevat $2^{k-1}$ korrels (Definitie 56.1). Veld $64$ bevat $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$: altijd één minder dan de volgende macht van $2$ ($2$, $4$, $8$, $16$, $32$). Vermoeden: $S_n = 2^n - 1$.

3. Elke term van $S_n$ verdubbelen schuift elke macht één op ($2 \times 2^{k} = 2^{k+1}$):

Trek de eerste regel van de tweede af: elke term van $2$ tot $2^{n-1}$ staat in beide en valt weg:

4. Het totaal is $S_{64} = 2^{64} - 1$ korrels. Een vijfenzestigste veld zou $2^{64}$ korrels bevatten: het hele bord draagt precies één korrel minder dan dat ene veld.

5. De eerste helft bevat $S_{32} = 2^{32} - 1$ korrels. Het hele bord bevat $2^{64} - 1$, dus bevat de tweede helft

($2^{32}$ buiten haakjes gebracht, met $2^{32} \times 2^{32} = 2^{64}$, Stelling 56.3): precies $2^{32}$ keer de eerste helft.

6. Met de rekenregels is $2^{64} = 2^{4 + 60} = 2^4 \times \left(2^{10}\right)^6$. Omdat $2^{10} = 1024 > 10^3$, geldt

7. Meer dan $1.6 \times 10^{19}$ korrels van elk $5 \times 10^{-2}$ g:

Delen door $10^6$ g per ton: meer dan $8 \times 10^{11}$ ton — achthonderd miljard ton.

8. $\dfrac{8 \times 10^{11}}{8 \times 10^{8}} = 10^3$: de koning beloofde minstens duizend jaar van de hele huidige wereldoogst. (De legende zegt dat zijn raadgevers hem dat vertelden.)

9. $2^{19} = 2^9 \times 2^{10} = 512 \times 1024 = 524\,288 < 10^6$, terwijl $2^{20} = \left(2^{10}\right)^2 = 1024^2 = 1\,048\,576 > 10^6$. De kleinste exponent is dus $n = 20$: twintig verdubbelingen gaan het miljoen voorbij.

10. Het loon op dag $n$ is $2^{n-1}$ cent (dag 1: $2^0 = 1$). Nu is

Het dagloon gaat dus voor het eerst boven $10^8$ cent als $n - 1 = 27$: op dag $28$.

11. $21 = 16 + 4 + 1$: de gewichten $16$, $4$ en $1$ g. $27 = 16 + 8 + 2 + 1$: de gewichten $16$, $8$, $2$ en $1$ g.

12. Volgens vraag 3 wegen de gewichten $1, 2, 4, 8$ samen $S_4 = 2^4 - 1 = 15$ g. Zonder het gewicht van $16$ g komt de koopvrouw dus niet voorbij $15$ g: elk doelgewicht van $16$ g of meer moet het gebruiken. En een doelgewicht van $15$ g of minder mag het niet gebruiken, want het gewicht van $16$ g alleen is al te zwaar. De keuze van het grootste gewicht is dus gedwongen. Wat overblijft, is een doelgewicht van hoogstens $15$ g dat met $1, 2, 4, 8$ gevormd moet worden — en daar herhaalt hetzelfde argument zich: $8$ is gedwongen (gebruikt als het resterende doel $\geq 8$ is, anders niet, want $1 + 2 + 4 = 7$), dan $4$ (want $1 + 2 = 3$), dan $2$, dan $1$.

13. Als je de gedwongen keuzes volgt, is het resterende doel na elke stap hoogstens het totaal van de resterende gewichten, dus eindigt het proces met rest $0$: elk doel van $1$ tot $31$ wordt bereikt. En omdat elke keuze onderweg gedwongen was, kan geen andere selectie gewichten hetzelfde doel bereiken: de schrijfwijze van elk getal van $1$ tot $31$ als een som van verschillende machten van $2$ bestaat en is uniek.

14. De zes gewichten zijn samen $S_6 = 2^6 - 1 = 63$ g, en hetzelfde argument met gedwongen keuzes dekt elk doel van $1$ tot $63$ g. Voor $45$: het doel is $\geq 32$, dus gebruik $32$; er blijft $13 < 16$, dus $16$ overslaan; gebruik $8$ (blijft $5$), gebruik $4$ (blijft $1$), sla $2$ over, gebruik $1$:

15. Op elk van de $64$ velden een $0$ of een $1$ kiezen komt neer op kiezen welke machten $2^0, 2^1, \dots, 2^{63}$ in een som meedoen — precies het wegen van de koopvrouw met $64$ gewichten. Het kleinste getal dat je kunt bewaren is $0$ (alle velden op $0$); het grootste is de som van alle machten, en dat is het totaal van de koning: $S_{64} = 2^{64} - 1$ (deel I). Volgens het argument met de gedwongen keuzes wordt elk heel getal daartussen precies één keer bereikt: een $64$-bitsmachine bewaart precies de hele getallen van $0$ tot $2^{64} - 1$.