XLV OM - III - Zadanie 4

Dysponujemy trzema naczyniami bez podziałki: pustym $ m $-litrowym, pustym $ n $-litrowym oraz napełnionym wodą $ (m+n) $-litrowym. Liczby $ m $ i $ n $ są liczbami naturalnymi względnie pierwszymi. Udowodnić, że dla każdej liczby $ k \in \{1,2, \ldots , m+n-1\} $ można za pomocą przelewania wody otrzymać w trzecim naczyniu dokładnie $ k $ litrów wody.

Rozwiązanie

Przelewając wodę z jednego naczynia do drugiego, każdorazowo albo całkowicie opróżniamy naczynie, z którego przelewamy, albo całkowicie napełniamy drugie naczynie. (Skoro naczynia są bez podziałki, jest to jedyna metoda pozwalająca kontrolować objętość przelewanej wody.) Tak więc po każdym przelaniu mamy w każdym naczyniu nieujemną całkowitą liczbę litrów wody (nie przekraczającą, rzecz jasna, pojemności danego naczynia). Przyjmijmy oznaczenia:

  • $ A $ - naczynie $ m $-litrowe,
  • $ B $ - naczynie $ n $-litrowe,
  • $ C $ - naczynie $ (m+n) $-litrowe.

Przypuśćmy, że w pewnym momencie w naczyniu $ C $ jest $ c $ litrów wody. Wykażemy, że za pomocą co najwyżej dwóch przelań można doprowadzić do stanu, w którym w naczyniu $ C $ jest $ c' $ litrów wody, gdzie

\[<br /> (1) \qquad c'= \left\{\begin{array}{ll}<br /> c + n & \textrm{jeśli } c \leq m,\\<br /> c - m & \textrm{jeśli } c>m.<br /> \end{array}\right.<br /> \]

Oznaczmy przez $ a $ i $ b $ objętość (w litrach) wody w naczyniach $ A $ i $ B $ w rozważanym momencie. Tak więc $ a $, $ b $, $ c $ są liczbami całkowitymi,

\[<br /> 0\leq a\leq m, \quad 0\leq b \leq n, \quad 0 \leq c \leq m + n; \quad a + b + c = m + n.<br /> \]

Załóżmy, że $ c\leq m $. Zatem $ a + b \geq n $. Przelewamy wodę z naczynia $ A $ do naczynia $ B $, całkowicie je napełniając; to znaczy, przelewamy $ n - b $ litrów z $ A $ do $ B $ (jest to możliwe, bo $ a\geq n - b $). Następnie całą zawartość naczynia $ B $, czyli $ n $ litrów, wlewamy do $ C $, uzyskując $ c + n $ litrów w naczyniu $ C $.

Rozpatrzmy drugi przypadek: $ c>m $. Zatem $ a + b<n $. Całą zawartość naczynia $ A $, czyli $ a $ litrów, wlewamy do $ B $. Do pustego naczynia $ A $ odlewamy $ m $ litrów z $ C $; w naczyniu $ C $ zostało $ c-m $ litrów wody.

Uzyskaliśmy więc $ c' $ litrów w naczyniu $ C $, gdzie liczba $ c' $ jest dana wzorem (1). Z tego wzoru wynika, że

\[<br /> c' \equiv c + n \pmod{m + n}.<br /> \]

W chwili początkowej w naczyniu $ C $ było $ m + n $ litrów. Stosując opisaną procedurę uzyskujemy w naczyniu $ C $:
\begin{center}
po (co najwyżej) dwóch przelaniach - $ c_1 $ litrów;\\
po (co najwyżej) czterech przelaniach - $ c_2 $ litrów;\\
itd.;\\
po (co najwyżej) $ 2i $ przelaniach - $ c_i $ litrów,
\end{center}
gdzie

\[<br /> (2) \qquad c_i \equiv in \pmod{m + n}.<br /> \]

Udowodnimy, że każda liczba $ k \in \{1,2,\ldots,m+n-1\} $ jest równa $ c_i $ dla pewnego $ i $; jest więc możliwą do uzyskania objętością wody w naczyniu $ C $.

Przyjmijmy $ c_0 = 0 $. Każda z liczb

\[<br /> (3) \qquad c_0, c_1 , c_2, \ldots, c_{m+n-1}<br /> \]

należy do zbioru $ \{0,1,2,\ldots,m+n-1\} $; jest więc, zgodnie ze wzorem (2), resztą z dzielenia iloczynu $ in $ przez $ m + n $.

Liczby $ m $ i $ n $ są z założenia względnie pierwsze. Wobec tego także liczby $ n $ i $ m + n $ są względnie pierwsze. Stąd wynika, że reszty (3) są wszystkie różne. Istotnie: gdyby dla pewnych numerów $ i $, $ j $ takich, że $ 0\leq i<j \leq m + n - 1 $ zachodziła równość $ c_i = c_j $, znaczyłoby to, że różnica $ jn-in $, czyli iloczyn $ (j - i)n $, dzieli się przez $ m + n $. Drugi czynnik tego iloczynu (czyli $ n $) nie ma z liczbą $ m + n $ wspólnych czynników pierwszych; ta liczba musiałaby być więc dzielnikiem różnicy $ (j - i) $ - sprzeczność, skoro $ 0 <j - i <m + n $.

Zatem, rzeczywiście, wypisane powyżej reszty (3) są różnymi elementami zbioru $ \{0,1,2,\ldots, m+n-1\} $. Jest ich $ m + n $. W takim razie każda liczba $ k $, należąca do tego zbioru, jest równa pewnej liczbie $ c_i $. A to właśnie zamierzaliśmy udowodnić.

Uwaga: Opisana metoda pozwala osiągnąć dowolnie zadaną wartość $ k $ w wyniku nie więcej niż $ 2(m + n -1) $ przelań. Oszacowanie to można poprawić. Jeśli bowiem żądana liczba $ k $ znajduje się w drugiej połowie ciągu (3), wówczas szybciej doprowadzi do celu stosowanie procedury ,,odwrotnej'' - takiej, która za pomocą co najwyżej dwóch przelań spowoduje, by objętość wody w naczyniu $ C $ zmieniła się od wartości $ c $ do wartości

\[<br /> c''= \left\{\begin{array}{ll}<br /> c + m & \textrm{jeśli } c \leq n,\\<br /> c - n & \textrm{jeśli } c>n.<br /> \end{array}\right.<br /> \]

Pozostawiamy Czytelnikowi jako ćwiczenie dopracowanie szczegółów i przekonanie się, że wybierając jedną z tych procedur jesteśmy w stanie uzyskać zadaną wartość $ k $ w wyniku nie więcej niż $ 2[\frac{1}{2}(m + n)] $ przelań.

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

Komentarze

Dodaj nową odpowiedź