VI OM - I - Zadanie 2

Zawody matematyczne:

VI OM, 1954-1955

Etap:

Fabryka wysyła towar w paczkach po $3$ kg i po $5$ kg. Wykazać, że można w ten sposób wysłać każdą całkowitą ilość kilogramów większą niż $7$ . Czy można w tym zadaniu zastąpić dane liczby innymi liczbami?

Rozwiązanie

Każda liczba całkowita większa niż $7$ może być przedstawiona w jednej z postaci $3k-1$ , $3k$ , $3k+1$ , gdzie $k$ jest liczbą całkowitą większą niż $2$ . Ponieważ $3k - 1 = 3 (k - 2) + 5$ , a $3k + 1 = 3 (k - 3) + 2 \cdot 5$ , więc wnioskujemy stąd, że każda liczba całkowita większa niż $7$ może być przedstawiona w postaci $3x + 5y$ , gdzie $x$ i $y$ są liczbami całkowitymi nieujemnymi. Istotnie więc można wysłać każdą całkowitą ilość kilogramów towaru, większą niż $7$ , używając tylko paczek trzy- i pięciokilogramowych. Łatwo sprawdzić, że nie można wysłać w ten sposób $7$ kg.

Twierdzenie to można uogólnić w sposób następujący. Przypuśćmy, że towar wysyła się w paczkach po $a$ i po $b$ kilogramów. Gdy $a$ i $b$ mają wspólny podzielnik $d > 1$ , wtedy oczywiście liczba kilogramów każdej wysłanej paczki towaru musi być podzielna przez $d$ . Załóżmy tedy, że liczby naturalne $a$ i $b$ są pierwsze względem siebie, przy czym żadna z nich nie jest równa $1$ . Dowiedziemy, że w paczkach po $a$ kg i po $b$ kg można wysłać każdą całkowitą ilość $c$ kilogramów większą niż $ab - a - b$ , nie można zaś wysłać $ab - a - b$ kilogramów.

Aby to wykazać, weźmy pod uwagę równanie $ax + by = c$ , skąd

$ y = \frac{c-ax}{b}. $

Nadajmy zmiennej $x$ wartości $x_0 = 0, x_1 = 1, x_2 = 2, \ldots, x_{b_1} = b - 1$ ; odpowiednie wartości zmiennej $y$ oznaczmy literami $y_0, y_1, y_2, \ldots, y_{b-1}$ ; wartości te tworzą ciąg malejący. Łatwo dowieść, że jedna i tylko jedna z nich jest liczbą całkowitą. Istotnie, każda z liczb $c - ax_i$ ( $i = 0, 1, \ldots, b - 1$ ) daje inną resztę przy dzielniku $b$ ; gdyby bowiem dwie z nich, np. $c - ax_i$ i $c - ax_k$ , dawały tę samą resztę, to różnica

$ (c - ax_i) - (c - ax_k) = a (x_k - x_i) $

byłaby podzielna przez $b$ , co jest niemożliwe, gdyż liczba $a$ jest pierwsza względem $b$ , a liczba $x_k - x_i$ jest bezwzględnie mniejsza od $b$ .

Stąd wynika, że jedna i tylko jedna z owych $b$ reszt jest równa zeru, a zatem jedna i tylko jedna z liczb $y_0, y_1, \ldots, y_{k-1}$ jest całkowita. Aby liczba ta była nieujemna, tzn. większa niż $- 1$ wystarczy, żeby najmniejsza z liczb $y_0, y_1, \ldots$ tj. liczba $y_{b-1}$ była większa od $- 1$ , co daje warunek

$ \frac{c - a (b - 1)}{b} > - 1 \textrm{ lub } c > ab - a - b. $

A zatem, jeśli warunek ten jest spełniony, to równanie $ax + by =c$ ma rozwiązanie w liczbach całkowitych nieujemnych $(x, y)$ .

Jeśli $c = ab - a - b$ , to

$ y_{b-1} = \frac{ab - a - b - a (b - 1)}{b} = -1. $

Równanie $ax + by = c$ nie ma wówczas rozwiązań całkowitych nieujemnych, gdyż wobec tego, że $y_{b-1}$ jest całkowite, żadna z liczb $y_0, y_1, \ldots, y_{b-2}$ nie jest całkowita, a gdy $x > b - 1$ , wtedy $y < - 1$ .