Komentarz

II OM - III - Zadanie 2

Jakie cyfry należy umieścić zamiast zer na trzecim i piątym miejscu w liczbie $ 3000003 $, aby otrzymać liczbę podzielną przez $ 13 $?

Rozwiązanie

Oznaczmy poszukiwane cyfry przez $ x $ i $ y $ i napiszmy liczbę $ 30x0y03 $ w postaci

\[<br /> N = 3 \cdot 10^6 + x \cdot 10^4 + y \cdot 10^2 + 3.<br /> \]

Mamy znaleźć takie liczby całkowite $ x $ i $ y $, żeby liczba $ N $ była podzielna przez $ 13 $ i żeby spełnione były nierówności

\[<br /> 0 \leq x \leq 9,\ 0 \leq y \leq 9.<br /> \]

Liczby $ 10^6 $, $ 10^4 $, $ 10^2 $ dają przy dzielniku $ 13 $ odpowiednio reszty $ 1 $, $ 3 $, $ 9 $ wobec czego

\[ 3 \cdot 10^6 = 13k_1 + 3, \]
\[ x \cdot 10^4 = 13k_2 + 3x,\]
\[ y \cdot 10^2 = 13k_3 + 9y,\]

gdzie $ k_1 $, $ k_2 $, $ k_3 $ są liczbami naturalnymi. W takim razie

\[<br /> N = 13k + 3 + 3x + 9y + 3,<br /> \]

czyli

\[<br /> N = 13k + 3 (x + 3y + 2),<br /> \]

gdzie $ k $ jest liczbą naturalną.

Aby liczba $ N $ była podzielna przez $ 13 $, potrzeba i wystarcza, żeby liczba $ x + 3y + 2 $ była podzielna przez $ 13 $, tj. żeby $ x $ i $ y $ spełniały równanie

\[<br /> x + 3y + 2 = 13m,<br /> \]

w którym $ m $ oznacza liczbę naturalną.

Z nierówności $ x \leq 9 $, $ y \leq 9 $ wynika, że

\[<br /> x + 3y + 2 \leq 9 + 3 \cdot 9 + 2,<br /> \textrm{ czyli }<br /> x + 3y + 2 \leq 38,<br /> \]

zatem liczba $ m $ spełniać musi nierówność $ 13m \leq 38 $, tzn. $ m $ może być równe tylko $ 1 $ albo $ 2 $.

1° Biorąc $ m = 1 $ otrzymujemy dla $ x $ i $ y $ równanie

\[<br /> x + 3y + 2 = 13, \textrm{ czyli }x = 11 - 3y.<br /> \]

Przy ograniczeniach $ 0 \leq x \leq 9 $, $ 0 \leq y \leq 9 $ równanie to ma trzy rozwiązania w liczbach całkowitych:

\[<br /> \left\{<br /> \begin{array}{l}<br /> y =1\\<br /> x = 8<br /> \end{array}<br /> \right.<br /> \quad<br /> \left\{<br /> \begin{array}{l}<br /> y = 2\\<br /> x =4<br /> \end{array}<br /> \right.<br /> \quad<br /> \left\{<br /> \begin{array}{l}<br /> y = 3\\<br /> x = 2<br /> \end{array}<br /> \right.<br /> \]

2° Biorąc $ m = 2 $ mamy równanie

\[<br /> x + 3y + 2 = 26, \textrm{ czyli } x = 3 (8 - y)<br /> \]

i otrzymujemy rozwiązania:

\[<br /> \left\{<br /> \begin{array}{l}<br /> y = 5\\<br /> x = 9<br /> \end{array}<br /> \right.<br /> \quad<br /> \left\{<br /> \begin{array}{l}<br /> y =6\\<br /> x =6<br /> \end{array}<br /> \right.<br /> \quad<br /> \left\{<br /> \begin{array}{l}<br /> y = 7\\<br /> x = 3<br /> \end{array}<br /> \right.<br /> \quad<br /> \left\{<br /> \begin{array}{l}<br /> y = 8\\<br /> x = 0<br /> \end{array}<br /> \right.<br /> \]

Zadanie ma zatem $ 7 $ rozwiązań, którym odpowiadają liczby: $ 3080103 $, $ 3040203 $, $ 3020303 $, $ 3090503 $, $ 3060603 $, $ 3030703 $, $ 3000803 $.

Uwaga. W zadaniu nr 35 chodziło o zmianę cyfr pewnej określonej liczby. Rozważmy dwa przykłady ogólniejszych zadań tego typu:

I. Dana jest liczba naturalna $ N $ niepodzielna przez liczbę pierwszą $ p $ i mająca na $ k $-tym miejscu dziesiętnym cyfrę $ 0 $. Czy można zastąpić owo zero taką cyfrą $ x $, żeby nowa liczba była podzielna przez $ p $?

Zauważmy najpierw, że gdy $ p $ jest równe $ 2 $ lub $ 5 $, wtedy zadanie nie ma rozwiązania. Założymy przeto w dalszym ciągu, że $ p \ne 2 $ i $ p \ne 5 $.

Gdy na $ k $-tym miejscu dziesiętnym liczby $ N $ umieścimy cyfrę $ x $, wówczas otrzymana liczba $ N(x) $ wyraża się wzorem

\[<br /> (1) \qquad N(x) = N + x \cdot 10^{k-1}.<br /> \]

Weźmy pod uwagę wartości funkcji $ N(x) $, gdy $ x $ przybiera wartości $ 0, 1, 2, \ldots, (p -1) $:

\[<br /> (2) \qquad N(0), N(1), N(2), \ldots, N(p-1).<br /> \]

Każda z $ p $ liczb ciągu (2) daje inną resztę przy dzielniku $ p $. Istotnie, według wzoru (1) różnica dwóch liczb ciągu (2) wyraża się wzorem

\[<br /> N(i) - N(j) = (i - j) \cdot 10^{k-1}.<br /> \]

Gdy $ i \ne j $, liczba ta nie jest podzielna przez $ p $, gdyż czynnik $ (i - j) $ jest różny od zera i bezwzględnie mniejszy od $ p $, a czynnik $ 10^{k-1} $ ma tylko podzielniki pierwsze $ 2 $ i $ 5 $. Liczby $ N(i) $ i $ N(j) $ dają więc przy dzielniku $ p $ reszty różne.

Ponieważ reszty liczb ciągu (2) są różne, a jest ich $ p $, więc jedna i tylko jedna z tych reszt równa się zeru, tzn. jedna i tylko jedna z liczb ciągu (2) jest podzielna przez $ p $; niech liczbą tą będzie $ N(x_0) $.

Jeśli $ x_0 \leq 9 $, to $ x_0 $ daje rozwiązanie zadania.

Jeśli $ x_0 > 9 $, zadanie nie ma rozwiązania.

Stąd wniosek:

a) Gdy $ p =3 $, zadanie ma zawsze trzy rozwiązania; szukanymi cyframi są bądź $ 1 $, $ 4 $, $ 7 $, bądź $ 2 $, $ 5 $, $ 8 $.

b) Gdy $ p = 7 $, zadanie ma bądź dwa rozwiązania - cyfry $ 1 $, $ 8 $ lub $ 2 $, $ 9 $, bądź jedno rozwiązanie - którąś z cyfr $ 3 $, $ 4 $, $ 5 $, $ 6 $.

c) Gdy $ p \geq 11 $, zadanie może mieć jedno rozwiązanie lub nie mieć żadnego rozwiązania. Jeśli $ p = 11 $, to pierwszy z tych przypadków zachodzi np. dla liczby $ 10 $, przykład zaś przypadku drugiego daje liczba $ 109 $.

II. Dana jest liczba naturalna $ N $ niepodzielna przez liczbę pierwszą $ p \geq 11 $ i mająca na $ k $-tym i na $ l $-tym miejscu dziesiętnym cyfrę $ 0 $. Czy można zastąpić te zera takimi cyframi $ x $ i $ y $, żeby nowa liczba była podzielna przez $ p $?

Gdy na $ k $-tym miejscu dziesiętnym liczby $ N $ umieścimy cyfrę $ x $, a na $ l $-tym miejscu cyfrę $ y $, otrzymamy liczbę $ N(x, y) $ wyrażającą się wzorem

\[<br /> (3) \qquad N(x, y) = N + x \cdot 10^{k-1} + y \cdot 10^{l-1}.<br /> \]

Weźmy pod uwagę te wartości funkcji $ N(x, y) $, które otrzymamy podstawiając zamiast $ x $ i $ y $ wartości $ 0, 1, 2, \ldots, (p - 1) $. Otrzymujemy $ p^2 $ liczb:

\[<br /> \begin{array}{lllll}<br /> N(0, 0), & N(0, 1), & N(0, 2), & \ldots, & N(0, p - 1)\\<br /> N(1, 0), & N(1, 1), & N(1, 2), & \ldots, & N(1, p - 1)\\<br /> N(p - 1, 0), & N(p - 1, 1), & N(p - 1, 2),& \ldots, & N(p - 1, p -1).<br /> \end{array}<br /> \]

Stwierdzamy jak w zadaniu I, że w każdym wierszu i w każdej kolumnie tej tablicy istnieje jedna i tylko jedna liczba podzielna przez $ p $; liczbę taką znajdującą się w $ i $-tym wierszu oznaczymy symbolem $ N(i, y_i) $.

Tabela zawiera więc $ p $ liczb podzielnych przez $ p $; są nimi liczby

\[<br /> (4) \qquad N(0, y_0),\ N(1, y_1),\ N(2, y_2),\ \ldots, \ N(p-1, y_{p-1}),<br /> \]

przy czym ciąg liczb $ y_0, y_1, y_2, \ldots, y_{p-1} $ zawiera te same liczby, co ciąg $ 0, 1, 2, \ldots, (p - 1) $, tylko w innym porządku. Zauważmy ponadto, że $ y_0 $ na pewno nie równa się $ 0 $, gdyż liczba $ N(0, 0) = N $, według założenia, nie jest podzielna przez $ p $.

Liczba $ N(i, y_i) $ ciągu (4) daje rozwiązanie zadania tylko wtedy, gdy $ i \leq 9 $ i $ y_i \leq 9 $. Łatwo policzyć, ile takich liczb ciąg (4) może zawierać. Należy ich szukać między liczbami

\[<br /> (5) \qquad N(0,y_0),\ N(1,y_1),\ \ldots,\ N(9,y_9).<br /> \]

W przypadku, gdy żadna z liczb $ y_0, y_1, \ldots, y_9 $ nie jest większa niż $ 9 $, zadanie ma $ 10 $ rozwiązań danych przez liczby ciągu (5). Jest to największa możliwa liczba rozwiązań.

Jeśli wśród liczb $ y_0, y_1, \ldots, y_9 $ znajdują się liczby większe niż $ 9 $ (liczb takich może być co najwyżej $ p - 10 $), należy odpowiednie wyrazy wykreślić z ciągu (5). Zadanie ma zatem co najmniej $ 10 - (p - 10) $, czyli $ 20 - p $ rozwiązań.

Stąd wniosek:

a) Gdy $ p = 11 $, zadanie ma co najmniej $ 9 $ rozwiązań. Przykładem przypadku, w którym mamy maksymalną liczbę $ 10 $ rozwiązań, jest liczba $ 101015 $.

b) Gdy $ p = 13 $, zadanie ma co najmniej $ 7 $ rozwiązań; przypadek, w którym jest tylko $ 7 $ rozwiązań, mieliśmy w zadaniu nr 35.

c) Gdy $ p = 17 $, mamy co najmniej trzy rozwiązania.

d) Gdy $ p = 19 $, zadanie ma co najmniej jedno rozwiązanie.

e) Gdy $ p \geq 23 $, zadanie może nie mieć żadnego rozwiązania. Odpowiedni przykład dla przypadku $ p = 23 $ można znaleźć bez trudu, gdy się zważy, że liczba $ 10^{22} $ daje przy dzielniku $ 23 $ resztę $ 1 $. Proponujemy to jako ćwiczenie.

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

Dodaj komentarz