XLV OM - III - Zadanie 4

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

III

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

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

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,

$ 0\leq a\leq m, \quad 0\leq b \leq n, \quad 0 \leq c \leq m + n; \quad a + b + c = m + n. $

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

$ c' \equiv c + n \pmod{m + n}. $

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

$ (2) \qquad c_i \equiv in \pmod{m + n}. $

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

$ (3) \qquad c_0, c_1 , c_2, \ldots, c_{m+n-1} $

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

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

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ń.