Odmierzanie Cukru

Odpowiedź

Potrzeba zaledwie 10 ważeń.

Wyjaśnienie

1 kg = 1000g, więc możliwe jest jest odmierzenie 1kg poprzez 1000 ważeń. Jest to jednak metoda dla kogoś kto ma bardzo dużo czasu. Zakładając, że co sekunde odbywa się ważenie to uzyskanie kilograma trwałoby 16 minut i 40 sekund. Zauważmy jednak, że po odmierzeniu 1g możemy zmierzyć już 2g kładąc na jednej szalce odważnik jak i zmierzony już 1g. Jak łatwo zauważyć kolejno dałoby się zważyć 1g, 2g, .., 512g oraz 1024 przy dziesiątym ważeniu. W ten sposób zmierzymy, aż 2047g, ale nie możemy wydzielić z tego 1000g, ponieważ wszystkie dotychczas zmierzone wartości są teraz w jednym pojemniku.

Jeśli jednak dodatkowy 1g odważnik nie będzie używany to jest to prosty sposób na podwajanie wartości. Zacznijmy od 1000g. Wykonamy na tym operację odwrotną: 1000 > 500 > 250 > 125. Teraz dzielenia na dwa nie można wykonać, ponieważ uzyskalibyśmy połówkę, której nie odmierzymy. Zauważmy, że 125 = 62 + 63 = 2·62 + 1. Z kolei 62 = 31 + 31. Z kolei 31 można uzyskać poprzez 1 < 2 < 4 < 8 < 16 < 32. W ostatnim kroku bez dołożenia odważnika uzyskamy o 1 mniej czyli tyle ile potrzebujemy.