Etikett: konstruktionsproblem

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!