Zbiór zadań, (zadania ciekawe)
Zadanie 11
Problem Mendelejewa
Mendelejew kojarzy się z tablicą pierwiastków chemicznych. Był on jednak
także w swoim czasie przewodniczącym Komitetu Miar i Wag i ta funkcja
nasunęła mu pomysł sformułowania następującego problemu:
Jeśli mam odważniki o ciężarze a, b, c, d
gramów, to jaka powinna być wartość liczbowa a, b,
c, d, żeby przy pomocy tych czterech odważników
można było zważyć każdy ciężar o wadze nie przewyższającej
a+b+c+d gramów?
Problem ten ma dwie wersje, związane ze sposobem ważenia na wadze
szalkowej.
Wersja I Odważniki wolno kłaść tylko na jednej szalce wagi, zaś
na drugiej ważony towar.
Wersja II Odważniki można kłaść także na tej szalce, na której
znajduje się ważony towar.
Rozwiązanie
Do rozwiązania problemu w wersji I wystarczy użyć dwójkowego (binarnego)
systemu pozycyjnego.
Rozważmy to na przykładzie, gdzie musimy zważyć towar nie
przekraczający 100 gramów - np. 89 gramów. Jakie odważniki będą do tego
potrzebne? Liczbę 87 zapisujemy w systemie binarnym.
89 = 1 · 26 + 0 · 25 +
1 · 24 + 1 · 23 +
0 · 22 + 0 · 21 +
1 · 20 = 10110012
Waga będzie zrównoważona, jeśli na drugiej szalce położymy odważniki o
ciężarach odpowiednio 1, 8, 16, 64, tzn. będących potęgami dwójki.
Ponieważ każdą liczbę naturalną można zapisać w systemie dwójkowym,
więc jeśli mamy komplet odważników, których ciężary są kolejnymi
potęgami dwójki, 1, 2, 4, 8, 16, 64, 128, itd. wówczas możemy zważyć
każdy towar nie przewyższający sumy ciężarów odważników tego kompletu.
Jeżeli ważenie odbywa się według wersji II, to wystarczy do tego celu
komplet odważników, których ciężary są kolejnymi potęgami trójki:
1, 3, 9, 27, 81, ... .
Wykorzystać należy więc trójkowy zapis pozycyjny, którego cyframi są 0,
1 i 2. Jeżeli ciężar ważonego towaru wyraża się liczbą, której trójkowy
zapis pozycyjny zawiera wyłącznie 0 i 1, to wówczas zważyć go można
metodą wersji I, kładąc na szalce tylko odważniki, odpowiadające cyfrom
1 w zapisie trójkowym. Na przykład towar o wadze 90 gramów zważymy za
pomocą odważników odpowiednio 81 i 9 gramów, gdyż:
90 = 1 · 34 + 0 · 33 +
1 · 32 + 0 · 31 + 0 · 30
= 101003
Tą metodą nie da się jednak zważyć towaru o wadze np. 64 g, skoro mamy
do dyspozycji tylko jeden komplet odważników. Przyczyną jest cyfra 2 w
zapisie trójkowym liczby 64.
64 = 2 · 33 + 1 · 32 +
0 · 31 + 1 · 30
= 21013
Więc potrzebne byłyby dwa odważniki o ciężarze 27 gramów oraz po jednym
o ciężarach odpowiednio 9 i 1 gramów. Ale 64 = 91 - 27 co w zapisie
trójkowym wygląda tak:
21013 = 101013 - 10003.
A więc na jednej szalce należy położyć odważniki o ciężarze 81, 9 i 1,
zaś na drugiej razem z towarem odważnik o ciężarze 27 gramów, a
następnie dla ustalenia wagi towaru wykonać odejmowanie.
Powstaje tylko pytanie: czy powyższy przykład to szczęśliwy przypadek?
Nie!
Każda liczba naturalna c jest różnicą liczb naturalnych a
i b takich, że cyframi w zapisie trójkowym każdej liczby z nich
są tylko 1 i 0, przy czym cyfry 1 występują na innych pozycjach w
odjemnej a niż w odjemniku b.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>