En balansvåg har två skålar. Om tyngderna på skålarna är lika visar balansvågen jämvikt. Annars visar den vilken skål som är tyngre. Det finns en stor påse strösocker, en balansvåg samt en vikt på 1g. Hur kan man snabbast väga upp ett hekto strösocker? Observera att om man lägger två sockerhögar i en och samma skål, så blandar sockret ihop sig till en enda hög förstås.
Lösning:
Det finns två saker vi måste göra: dels hitta på ett sätt att få 100 g överhuvudtaget och dels bevisa att det sättet verkligen är det snabbaste. Det är då kanske mer logiskt att göra detta i omvänd ordning: först uppskatta hur många vägningar behövs som minst, och sedan f’örsöka hitta på en algoritm för detta antal vägningar.
I allmänhet, gör alltid först den delen av lösningen som verkar vara enklast. I vårt fall är det ganska lätt att uppskatta en gräns i alla fall. Vi kan mäta hur mycket socker vi maximalt kan väga upp efter ett visst antal vägningar.
Första gången finns det bara en sak att göra: väga upp 1 g socker med hjälp av vikten. (1 g socker uppvägt)
Andra gången kan vi max väga upp 2 g socker till (placera vikten + 1 g socker på ena skålen och uppnå balans genom att hälla socker i den andra skålen). Efter detta har vi engramsvikten, en sockerhög som väger 1 g och en sockerhög som väger 2 g. (3 g socker uppvägt)
Tredje gången kan vi igen ta alltihop på en skål och på så sätt få en sockerhög som väger 4 g. (7 g socker uppvägt)
Fortsätt räkna på samma sätt, det vill säga väg upp så mycket socker som möjligt varje gång. Efter 6 gånger kommer vi ha 63 g socker uppvägt som mest. Det kan vara uppdelat i olika högar, men det är bara 63 g totalt som vi känner till massan för. Alltså räcker det inte med 6 vägningar.
Men går det med 7?
Det går faktiskt, men det är ett lite lurigt sätt. Jag tackar Johan som har berättat lösningen för mig. Djalal hade också en korrekt lösning.
Först observerade vi att man kunde dubbla all vikt man hade. Men genom att strunta i att använda engramsvikten, så kan vi dubblera allt vi hade minus 1 gram. Man kan förstås få dubletter av enskilda småhögar också, eller få en hög som vägde 1 g mer än en annan. Vi kan faktiskt även få en hög som väger 1 mindre än en viss vald, helt enkelt genom att placera den gamla högen på ena vågskålen och engramsvikten på den andra och sedan hälla socker tills det blir balans.
Första vägningen: 1 g vikt = 1 g socker
Andra vägningen: 1 g vikt + 1 g socker = 2 g socker
Tredje vägningen: 3 g socker = 3 g socker
Fjärde vägningen: 6 g socker = 6 g socker
Femte vägningen: 1 g vikt + 12 g socker = 13 g socker
Sjätte vägningen: 25 g socker = 25 g socker
Sjunde vägningen: 50 g socker = 50 g socker
Efter den sista vägningen har vi två högar med 50 g socker i varje, så det är bara att lägga ihop dem. Vi har fått ett hekto strösocker!
En turist vill ta en promenad i Gamla Stan från busshållplatsen (punkt A) till sitt hotell (punkt B). Han vill ha en så lång rutt som möjligt. Han tycker att det är tråkigt att komma tillbaka till korsningar där han har varit förut, så det undviker han. Rita en så lång rutt som möjligt åt turisten och visa att det inte finns längre.
. Det gäller alltså att ha vettigt bevis för att antalet vägningar är det minsta möjliga.
