Komentarz

VI OM - I - Zadanie 2

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

\[<br /> y = \frac{c-ax}{b}.<br /> \]

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

\[<br /> (c - ax_i) - (c - ax_k) = a (x_k - x_i)<br /> \]

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

\[<br /> \frac{c - a (b - 1)}{b} > - 1 \textrm{ lub } c > ab - a - b.<br /> \]

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

\[<br /> y_{b-1} = \frac{ab - a - b - a (b - 1)}{b} = -1.<br /> \]

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

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

Dodaj komentarz