Problem Mendelejewa
Mendelejew kojarzy się z tablicą pierwiastów chemicznych. Był on jednak
także w swoim czasie przewodniczącym Komitetu Miar i Wag i ta funkcja
nasunęła mu pomysł sformuławania nastepują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
zanjduje się ważony towar.
Rozwiązanie jest proste jeśli zastosuje się niedziesiętne systemy pozycyjne zapisywania liczb naturalnych.
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ównaoważ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 symy 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 wygłą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 cieżarze 27 gramów, a
następnie dla ustalenia wagi towaru wykonać odejmowanie.
Powstaje tylko pytanie: czy powyższy przykład to szczęsliwy 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.