Komentarz

LII OM - I - Zadanie 11

Układ liczb całkowitych dodatnich $ c_1,c_2,\ldots,c_n $ nazwiemy dopuszczalnym, gdy za pomocą wagi szalkowej i dwóch kompletów odważników o ciężarach $ c_1,c_2,\ldots,c_n $ można zważyć dowolny przedmiot o ciężarze będącym liczbą naturalną nie przekraczającą $ 2(c_1 + c_2 +\ldots + c_n) $. Dla każdej liczby $ n $ wyznaczyć maksymalną sumę $ n $ liczb tworzących układ dopuszczalny.

Uwaga: Odważniki można kłaść na obie szalki wagi.

Rozwiązanie

Niech $ p_1,p_2,\ldots,p_n $ oraz $ q_1,q_2,\ldots,q_n $ będą dwoma zestawami odważników o ciężarach odpowiednio $ c_1,c_2,\ldots,c_n $. Wykażemy najpierw, że za pomocą tych dwóch zestawów możemy zważyć co najwyżej $ \frac{1}{2}(5^n-1) $ przedmiotów, niezależnie od tego, czy liczby $ c_1,c_2,\ldots,c_n $ tworzą układ dopuszczalny, czy nie.

Ustawienie odważników na szalkach wagi nazwiemy optymalnym, jeśli dla każdego $ k \in\{1,2,\ldots,n\} $ ciężarki $ p_k $ i $ q_k $ nie znajdują się na dwóch różnych szalkach wagi.

Aby otrzymać ustawienie optymalne, dwa odważniki $ p_k $ i $ q_k $ możemy ustawić na szalkach wagi na $ 5 $ sposobów (zob. tabela obok). Zatem liczba wszystkich optymalnych ustawień odważników jest równa $ 5^n $. W tej liczbie mieści się jedno ustawienie „puste", w którym na żadną szalkę nie kładziemy odważników. Pozostałe ustawienia można połączyć w pary symetryczne, w których jedno ustawienie powstaje z drugiego przez zamianę zawartości obydwu szalek wagi.

lewa szalka prawa szalka
0 0
1 0
2 0
0 1
0 2

Tak więc liczba niepustych, istotnie różnych optymalnych ustawień odważników wynosi $ \frac{1}{2}(5^n-1) $, co oznacza, że możemy zważyć co najwyżej $ \frac{1}{2}(5^n-1) $ przedmiotów o różnych ciężarach.

Załóżmy, że liczby $ c_1,c_2,\ldots,c_n $ tworzą układ dopuszczalny. Wówczas masa najcięższego przedmiotu, jaki można zważyć, wynosi $ 2(c_1 + c_2 +\ldots + c_n) $. Ponieważ nie da się zważyć więcej niż $ \frac{1}{2}(5^n-1) $ przedmiotów,

\[<br /> (1)\qquad 2(c_{1}+c_{2}+\ldots+c_{n})\leq\frac{1}{2}(5^{n}-1).<br /> \]

Wykażemy teraz, że liczby $ c_1 = 1, c_2 = 5, c_3 = 5^2,\ldots ,c_n = 5^{n-1} $ tworzą układ dopuszczalny. Dla tych wartości $ c_i $ zachodzi równość

\[<br /> (2)\qquad 2(c_{1}+c_{2}+\ldots+c_{n})=\frac{1}{2}(5^{n}-1).<br /> \]

Należy więc udowodnić, że za pomocą dwóch kompletów odważników o ciężarach $ 1, 5, 5^2,\ldots,5^{n-1} $ można zważyć każdy przedmiot o ciężarze będącym liczbą naturalną nie przekraczającą $ \frac{1}{2}(5^n-1) $. Dowód tego faktu przeprowadzimy na dwa sposoby.

Sposób I

Indukcja. Dla $ n = 1 $ mamy dwa odważniki o ciężarze $ 1 $ każdy i za ich pomocą można zważyć przedmiot o ciężarze $ 1 $ lub $ 2 = \frac{1}{2}(5^1 - 1) $.

Załóżmy, że dysponujemy dwoma zestawami odważników o ciężarach $ 1, 5, 5^2 ,\ldots , 5^{n-1} $ i za ich pomocą umiemy zważyć każdy przedmiot o ciężarze nie przekraczającym $ \frac{1}{2}(5^n-1) $. Oto jak zważyć przedmiot $ p $ o ciężarze $ c $, gdy:

(a) $ c\in \langle \frac{1}{2}(5^n-1)+1 ,5^n-1 \rangle $.

Korzystając z założenia indukcyjnego ważymy najpierw przedmiot $ q $ o ciężarze $ 5^n-c $ kładąc go na prawą szalkę wagi. Następnie kładziemy dodatkowy ciężarek o masie $ 5^n $ na prawą szalkę wagi, zdejmujemy przedmiot $ q $ i kładziemy przedmiot $ p $ na lewą szalkę.

(b) $ c\in \langle 5^n+1,\frac{1}{2}(3\cdot 5^n-1)\rangle $.

Podobnie jak w przypadku (a), ważymy najpierw przedmiot $ q $ o ciężarze $ c - 5^n $ kładąc go na prawą szalkę wagi. Następnie kładziemy dodatkowy ciężarek o masie $ 5^n $ na lewą szalkę wagi, zdejmujemy przedmiot $ q $ i kładziemy przedmiot $ p $ na prawą szalkę.

(c) $ c\in \langle\frac{1}{2}(3\cdot 5^n-1)+1,2\cdot 5^n-1\rangle $.

Ważymy najpierw przedmiot $ q $ o ciężarze $ 2\cdot 5^n - c $ kładąc go na prawą szalkę wagi. Następnie kładziemy dwa ciężarki o masie $ 5^n $ na prawą szalkę wagi, zdejmujemy przedmiot $ q $, po czym kładziemy przedmiot $ p $ na lewą szalkę.

(d) $ c\in \langle 2\cdot 5^n+1,\frac{1}{2}(5^{n+1}-1) \rangle $.

Ważymy najpierw przedmiot $ q $ o ciężarze $ c - 2\cdot 5^n $ kładąc go na prawą szalkę wagi. Następnie kładziemy dwa ciężarki o masie $ 5^n $ na lewą szalkę wagi, zdejmujemy przedmiot $ q $, po czym kładziemy przedmiot $ p $ na prawą szalkę.

Przedmioty o masach $ 5^n $ i $ 2\cdot 5^n $ można zważyć używając jedynie dwóch odważników o masie $ 5^n $. Dowód indukcyjny został więc zakończony.

Sposób II

Niech $ c $ będzie dowolną liczbą naturalną nie przekraczającą $ \frac{1}{2}(5^n-1) $. Wówczas liczba $ c + \frac{1}{2}(5^n-1) $ jest mniejsza od $ 5^n $. Liczbę tę można zatem zapisać w systemie piątkowym przy użyciu co najwyżej $ n $ cyfr. Innymi słowy

\[<br /> c+\frac{1}{2}(5^{n}-1)=\sum_{i=0}^{n-1}a_{i}5^{i},\ \textrm{gdzie} \ a_{i}\in\{0,1,2,3,4\}.<br /> \]

Ponieważ $ \frac{1}{2}(5^{n}-1)=2(1+5+5^{2}+\ldots+5^{n-1}) $, więc

\[<br /> c=\sum_{i=0}^{n-1}\varepsilon_{i}5^{i},\ \textrm{gdzie}\ \varepsilon_{i}\in\{-2,-1,0,1,2\}.<br /> \]

Powyższa równość oznacza, że przedmiot o ciężarze $ c $ można zważyć za pomocą dwóch kompletów odważników o ciężarach $ 1, 5, 5^2, \ldots,5^{n-1} $, co kończy dowód.

Z równości (1) i (2) wynika, że maksymalna suma zbioru $ n $ liczb dopuszczalnych wynosi $ \frac{1}{4}(5^n-1) $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz