XLVIII OM - I - Zadanie 8

Niech $ a_n $ będzie liczbą wszystkich niepustych podzbiorów zbioru $ \{1,2,\ldots,6n\} $, których suma elementów daje przy dzieleniu przez 6 resztę 5 oraz niech $ b_n $ będzie liczbą wszystkich niepustych podzbiorów zbioru $ \{1,2,\ldots,7n\} $, których iloczyn elementów daje przy dzieleniu przez 7 resztę 5. Obliczyć iloraz $ a_n/b_n $.

Rozwiązanie

Sposób I

Dla skończonego zbioru liczb $ A $ symbole $ s(A) $ oraz $ p(A) $ będą oznaczały odpowiednio sumę oraz iloczyn wszystkich liczb w tym zbiorze. Niech $ n $ będzie ustaloną liczbą naturalną. Zgodnie z treścią zadania,

\[<br />
\begin{split}<br />
a_n = \textrm{liczba zbiorów}\ A \subset \{1,2,\ldots,6n\}\ \textrm{takich, że}\ s(A)\equiv 5 (\mathrm{mod}  6), \\<br />
b_n = \textrm{liczba zbiorów}\ B \subset \{1,2,\ldots,7n\}\ \textrm{takich, że}\ p(B) = 5 (\mathrm{mod}  7).<br />
\end{split}<br />
\]

Zauważmy, że w określeniu liczby $ b_n $ można ze zbioru $ \{1,2,\ldots,7n\} $ usunąć wszystkie wielokrotności liczby $ 7 $; jeśli bowiem zbiór $ B $ zawiera jakąkolwiek liczbę podzielną przez $ 7 $, to warunek $ p(B) \equiv 5 (\mathrm{mod}  7) $ na pewno nie jest spełniony. Przyjmując oznaczenia

\[<br />
\begin{split}<br />
 X_k = \{6k+1, 6k+2, 6k+3, 6k+4, 6k+5, 6k+6\},\\<br />
 Y_k = \{7k+1, 7k+2, 7k+3, 7k+4, 7k+5, 7k+6\},<br />
\end{split}<br />
\]

oraz

\[<br />
X = X_0 \cup X_1 \cup \ldots \cup X_{n-1} ( = \{1,2,\ldots,6n\}),\quad<br />
Y = Y_0 \cup Y_1 \cup \ldots \cup Y_{n-1},<br />
\]

można zatem przepisać określenie liczb $ a_n $ i $ b_n $, jak następuje:

\[<br />
\begin{split}<br />
a_n = \textrm{liczba zbiorów}\ A \subset X\ \textrm{takich, że}\ s(A)\equiv 5 (\mathrm{mod}  6), \\<br />
b_n = \textrm{liczba zbiorów}\ B \subset Y\ \textrm{takich, że}\ p(B) \equiv 5 (\mathrm{mod}  7).<br />
\end{split}<br />
\]

Weźmy pod uwagę dowolną liczbę $ x \in X $. Jest ona elementem dokładnie jednego ze zbiorów $ X_0, X_1,\ldots, X_{n-1} $. Liczba $ 3^x $ nie dzieli się przez $ 7 $, a więc w każdym ze zbiorów $ Y_0, Y_1, \ldots, Y_{n-1} $ istnieje dokładnie jeden element przystający do $ 3^x $ modulo $ 7 $. Spośród nich wybieramy element $ y $ należący do zbioru $ Y_k $ o tym samym numerze $ k $, co numer zbioru $ X_k $ zawierającego $ x $. Oznaczmy ten element $ y $ przez $ h(x) $. W ten sposób została określona funkcja $ h: X \to Y $ o własności:

\[<br />
\qquad (2) \textrm{jeśli}\ x \in X_k,\ \textrm{to}\ h(x) \in Y_k,\ h(x) \equiv 3^x (\mathrm{mod}  7).<br />
\]

Wykażemy, że jest ona różnowartościowa.

Przypuśćmy, że $ h(u) = h(v) $ dla pewnych liczb $ u,v \in X $. Przyjmijmy, że $ u \leq v $ oraz $ u \in X_k $, $ v \in X_l $. Wówczas $ h(u) \in Y_k $, $ h(v) \in Y_l $, więc z równości $ h(u) = h(v) $ wynika, że $ k=l $, a ponadto

\[<br />
\qquad (3) 3^u \equiv 3^v  (\mathrm{mod}  7).<br />
\]

Kluczem do dalszych rozważań będzie następująca, łatwa do sprawdzenia, własność:

\[<br />
\qquad (4) 3^6 \equiv 1 (\mathrm{mod}  7);\ 3^r \not\equiv 1 (\mathrm{mod}  7)\ \textrm{dla}\ r = 1,2,3,4,5.<br />
\]

Skoro $ u \leq v $ oraz $ u,v \in X_k $, zatem $ 0 \leq v-u \leq 5 $. Mnożymy związek (3) stronami przez liczbę całkowitą $ 3^{6(k+1)-u} $:

\[<br />
3^{6(k+1)} \equiv 3^{6(k+1)} \cdot 3^{v-u} (\mathrm{mod}  7).<br />
\]

Stąd na podstawie wzorów (4) wnosimy najpierw, że $ 1 \equiv 3^{v-u} (\mathrm{mod}  7) $, a następnie, że $ v - u = 0 $, czyli $ u = v $. Różnowartościowość funkcji $ h $ została wykazana.

Funkcja $ h $ odwzorowuje zbiór $ X $, liczący $ 6n $ elementów, w zbiór $ Y $, liczący także $ 6n $ elementów. Stąd wniosek, że jest ona różnowartościowym odwzorowaniem zbioru $ X $ na cały zbiór $ Y $.

Niech teraz $ A $ będzie dowolnym niepustym podzbiorem zbioru $ X $ i niech $ h(A) $ będzie obrazem zbioru $ A $ w odwzorowaniu $ h $. Udowodnimy, że zachodzi implikacja:

\[<br />
\qquad (5) \textrm{jeżeli}\ s(A) \equiv r(\mathrm{mod}  6),\ 0 \leq r<6,\ \textrm{to}\ p(h(A)) \equiv 3^{r} (\mathrm{mod}  7).<br />
\]

Przyjmijmy, że $ A = \{x_1,\ldots,x_m\} $. Zatem $ h(A) =\{y_1, \ldots, y_m\} $, gdzie

\[<br />
y_i = h(x_i) \equiv 3^{x_i} (\mathrm{mod}  7)<br />
\]

(por. (2)). Jeżeli $ s(A) \equiv r (\mathrm{mod}  6) $, $ 0 \leq r<6 $, to istnieje taka liczba całkowita $ q \geq 0 $, że $ x_1 + \ldots + x_m = 6q + r $. Korzystając ponownie z pierwszego wzoru (4) obliczamy:

\[<br />
p(h(A)) = y_1 \cdot \ldots \cdot y_m \equiv 3^{x_1} \cdot \ldots \cdot 3^{x_m}= 3^{x_1 + \ldots + x_m} = 3^{6q} \cdot 3^r \equiv 3^r (\mathrm{mod}  7);<br />
\]

to dowodzi słuszności implikacji (5).

Korzystając z własności (4) nietrudno się przekonać, że $ 3^5 \equiv 5 (\mathrm{mod}  7) $ oraz $ 3^r \not\equiv 5 (\mathrm{mod}  7) $ dla $ r \neq 5 \ (0 \leq r<6) $. Ze zdania (5) wynika zatem, że

\[<br />
s(A) \equiv 5 (\mathrm{mod}  6)\ \textrm{wtedy i tylko wtedy, gdy}\ p(h(A)) \equiv 5 (\mathrm{mod}  7).<br />
\]

A ponieważ $ h $ jest wzajemnie jednoznacznym odwzorowaniem zbioru $ X $ na $ Y $, wnosimy stąd, że w zbiorze $ X $ jest tyle samo podzbiorów $ A $ spełniających warunek $ s(A) \equiv 5 (\mathrm{mod}  6) $, ile jest w zbiorze $ Y $ podzbiorów $ B $ spełniających warunek $ p(B) \equiv 5 (\mathrm{mod}  7) $. To znaczy, że $ a_n = b_n $.

Otrzymujemy odpowiedź: dla każdej liczby naturalnej $ n $ iloraz $ a_n/b_n $ jest równy $ 1 $.

Uwaga: Własność (5) można tak wyrazić słowami —-- sugestywnie, choć nie ściśle: odwzorowanie $ h $ „przeprowadza'' dodawanie modulo $ 6 $ na mnożenie modulo $ 7 $. Czytelnicy, którym nie są obce najprostsze fakty oraz język teorii grup, wiedzą, że zbiór $ \{0,\ldots,5\} $ jest grupą przy działaniu dodawania modulo $ 6 $, a zbiór $ \{1,\ldots,6\} $ jest grupą przy działaniu mnożenia modulo $ 7 $.

Wspomniana własność, już w ścisłej terminologii, mówi, że operacja, która liczbie $ x \in \{0,\ldots ,5\} $ przyporządkowuje resztę z dzielenia liczby $ 3^x $ przez 7, jest {\it izomorfizmem} pierwszej z tych grup na drugą - i na tym spostrzeżeniu opiera się całe powyższe rozwiązanie.

Istotną rolę gra przy tym fakt, że potęgi trójki $ 3^0, 3^1, \ldots, 3^5 $ dają przy dzieleniu przez 7 różne reszty - por. wzory (4) . Tę samą własność ma też piątka; można więc wszędzie konsekwentnie zastąpić potęgowanie o podstawie 3 potęgowaniem o podstawie 5, i tak zmodyfikowane rozwiązanie też będzie poprawne.

Sposób II

Zachowajmy z poprzedniego rozwiązania oznaczenia: $ s(A),\ p(A),\ X_k,\ Y_k $ oraz

\[<br />
X = X_0 \cup X_1 \cup \ldots \cup X_{n-1},\quad Y = Y_0 \cup Y_1 \cup \ldots \cup Y_{n-1}.<br />
\]

Powtarzamy początkowy fragment tamtego rozwiązania i dochodzimy do wzorów (1) . Celem rozważań będzie wyprowadzenie zależności rekurencyjnych dla ciągów $ (a_n) $ i $ (b_n) $ (przy zmieniającym się $ n $).

Przyjmijmy dodatkowo oznaczenia:

\[<br />
\begin{split}<br />
&a(n,r) =\ \textrm{liczba zbiorów}\ A \subset X\ \textrm{takich, że}\ s(A) \equiv r (\mathrm{mod}  6)\\<br />
&\qquad \textrm{(dla}\ r = 0,1,2,3,4,5)\ \textrm{oraz} \\<br />
&b(n,q) = \textrm{liczba zbiorów}\ B \subset Y\ \textrm{takich, że}\ p(B) \equiv q  (\mathrm{mod}  7)\\<br />
& \qquad \textrm{(dla}\ q = 1,2,3,4,5,6);\ \textrm{tak więc}<br />
\end{split}<br />
\]
\[<br />
a_n=a(n,5), \ b_n = b(n,5).<br />
\]

Nie ograniczamy przy tym uwagi do zbiorów niepustych; dla $ r = 0 $ zbiór $ A $ może być pusty; podobnie dla $ q = 1 $ zbiór $ B $ może być pusty.

(Przyjmujemy zwykłą umowę, że $ s(\varnothing) = 0,\ p(\varnothing) = 1 $).

Ustalmy liczbę naturalną $ n $ i weźmy pod uwagę analogiczne zagadnienie dla liczby $ n+1 $. Oznaczmy:

\[<br />
\widetilde{X} = X_0\cup X_1\cup\ldots \cup X_{n-1}\cup X_{n},\  \widetilde{Y} = Y_0\cup Y_1\cup\ldots \cup Y_{n-1}\cup Y_{n}.<br />
\]

Każdy zbiór $ \widetilde{A}\subset \widetilde{X} $ jest sumą rozłącznych zbiorów $ A_0 $ i $ A $, gdzie $ A_0 = \widetilde{A}\cap X_0 $, $ A = \widetilde{A} \cap (X_1 \cup \ldots \cup X_n) $; przy tym $ s(\widetilde{A}) = s (A_0) + s(A) $. Jeśli reszta z dzielenia liczby $ s(A_0) $ przez $ 6 $ wynosi $ j $, to reszta z dzielenia liczby $ s(A) $ przez $ 6 $ wynosi $ r \ominus j $ tym symbolem będziemy oznaczać jedyną liczbę $ j' \in \{0,1,\ldots,5\} $ spełniającą warunek $ j+j' \equiv r (\mathrm{mod}  6) $. (Działanie $ \ominus $ jest więc namiastką zwykłego odejmowania).

Ustalmy zbiór $ \widetilde{A}\subset \widetilde{X} $ oraz ustalmy na chwilę wartość reszty $ j \in \{0,\ldots,5\} $. Policzymy, ile jest sposobów przedstawienia zbioru $ \widetilde{A} $ w postaci sumy $ A_0\cup A $, gdzie $ A_0\subset X_0 $, $ A \subset (X_1\cup \ldots \cup X_n) $, $ s(A_0) \equiv j $, $ s(A) \equiv r\ominus j (\mathrm{mod}  6) $.

Zbiór $ A_0 $ można wybrać na $ a(1,j) $ sposobów. Liczba podzbiorów $ A $ zbioru $ X_1\cup\ldots\cup X_n $ spełniających warunek $ s(A) = r \ominus j (\mathrm{mod}  6) $ jest dokładnie taka sama, jak liczba podzbiorów zbioru $ X_0\cup\ldots\cup X_{n-1} $ spełniających analogiczny warunek. Wynika to stąd, że zbiór $ X_1 \cup \ldots \cup X_n $ - to po prostu zbiór $ X_0\cup\ldots\cup X_{n-1} $ przesunięty o $ 6 $ jednostek. Mamy zatem $ a(n, r\ominus j) $ możliwości wyboru zbioru $ A $. Dla ustalonej wartości $ j $ daje to $ a(1, j) \cdot a(n, r \ominus j) $ sposobów przedstawienia zbioru $ \widetilde{A} $ w rozważanej postaci.

Liczba wszystkich zbiorów $ \widetilde{A} $ zawartych w zbiorze $ \widetilde{X} $ oraz spełniających warunek $ s(\widetilde{A}) \equiv r (\mathrm{mod}  6) $ jest sumą takich iloczynów przy zmieniającym się $ j=0,\ldots,5 $:

\[<br />
\qquad (6) a(n+1,r) = \sum_{j=0}^5 a(1,j) \cdot a(n, r \ominus j).<br />
\]

Dokładnie takie samo rozumowanie prowadzi do podobnego wzoru dla $ b(n+1,q) $:

\[<br />
\qquad (7) b(n+1,q) = \sum_{i=0}^6 b(1,i) \cdot b(n, q\oslash i);<br />
\]

literki $ q $ oraz $ i $ oznaczają teraz możliwe reszty z dzielenia przez $ 7 $ (jak pamiętamy, reszta zerowa została wykluczona); zaś dla $ q,i \in \{1,2,...,6\} $ symbol $ q\oslash i $ oznacza jedyną liczbę $ i' \in \{1,2,\ldots,6\} $ spełniającą warunek $ i\cdot i' \equiv q (mod 7) $. (Działanie $ \oslash $ jest namiastką dzielenia). Wyprowadzenie wzoru (7) tym się tylko różni od wyprowadzenia wzoru (6), że zamiast zbiorów $ X_0 $ i $ X_1\cup\ldots\cup X_n $ rozważa się zbiory $ Y_0 $ i $ Y_1 \cup\ldots \cup Y_n $, zamiast sum $ s(A) $ — iloczyny $ p(B) $, a zamiast przystawania modulo $ 6 $ — przystawanie modulo $ 7 $.

Wartości $ a(1,j) $ oraz $ b(1,i) $ można wyznaczyć empirycznie, wypisując wszystkie możliwe podzbiory zbiorów $ X_0 $ oraz $ Y_0 $. (Można je też wyznaczyć metodą mniej pracochłonną - pozostawiamy to sprytowi Czytelnika.)

Oto wynik zliczania:

\[<br />
a(1,j)=\left\{<br />
\begin{array}{ll}<br />
10&\textrm{dla}\ j=1,2,4,5, \\<br />
12&\textrm{dla}\ j=0,3,<br />
\end{array}<br />
\right.<br />
\quad<br />
b(1,i)=\left\{<br />
\begin{array}{ll}<br />
10&\textrm{dla}\ j=2,3,4,5, \\<br />
12&\textrm{dla}\ j=1,6.<br />
\end{array}<br />
\right.<br />
\]

Podstawiając te wartości do wzorów (6) oraz (7) dostajemy kolejne wzory

\[<br />
\begin{split}<br />
a(n+1,r) &=   \sum_{j=1,2,4,5} 10 \cdot a(n, r\ominus j) + \sum_{j=0,3} 12\cdot a(n, r\ominus j) =\\<br />
&= 10 \sum_{j=0}^5 a(n,r\ominus j) + 2a(n,r)+2a(n,r\ominus 3)<br />
\end{split}<br />
\]

(bowiem $ r\ominus 0 = r $) oraz

\[<br />
\begin{split}<br />
b(n+1,q) &=   \sum_{i=2,3,4,5} 10 \cdot b(n, q\oslash i) + \sum_{i=1,6} 12\cdot b(n, q\oslash i) =\\<br />
&= 10 \sum_{i=1}^6 b(n,q\oslash i) + 2b(n,q)+2b(n,q\oslash 6)<br />
\end{split}<br />
\]

(bowiem $ q\oslash 1 = q $).

Gdy $ j $ przebiega wartości od $ 0 $ do $ 5 $, czyli wszystkie możliwe reszty z dzielenia przez $ 6 $, wówczas także $ r \ominus j $ przebiega wszystkie możliwe reszty z dzielenia przez $ 6 $ (przy ustalonej wartości $ r $). Zatem suma $ \sum_{j=0}^5 a(n, r \ominus j) $ jest liczbą wszystkich podzbiorów zbioru $ X = X_0 \cup \ldots \cup X_{n-1} $.

Gdy $ i $ przebiega wartości od $ 1 $ do $ 6 $, czyli wszystkie {\it niezerowe} reszty z dzielenia przez $ 7 $, wówczas $ q \oslash i $ przebiega wszystkie {\it niezerowe} reszty z dzielenia przez $ 7 $ (przy ustalonej wartości $ q $). Zatem suma $ \sum_{i=1}^6 b(n, q \oslash i) $ jest liczbą wszystkich podzbiorów zbioru $ Y = Y_0 \cup \ldots \cup Y_{n-1} $; korzystamy tu z faktu, że dla każdego zbioru $ B \subset Y $ wartość $ p(B) $ jest niepodzielna przez $ 7 $ (wielokrotności siódemki zostały odrzucone przy definiowaniu zbioru $ Y $).

Zbiory $ X $ i $ Y $ są ($ 6n $)-elementowe; mają zatem po $ 2^{6n} $ podzbiorów. Uzyskane wzory przybierają prostszą postać

\[<br />
\begin{split}<br />
a(n+1, r) = 10 \cdot 2^{6n} + 2a(n,r) + 2a(n,r \ominus 3),\\<br />
b(n+1, q) = 10 \cdot 2^{6n} + 2b(n,q) + 2b(n,q \ominus 6).<br />
\end{split}<br />
\]

Zauważmy, że
$ r \ominus 3 =<br />
\left\{<br />
\begin{array}{ll}<br />
5 & \textrm{dla}\ r=2, \\<br />
2 & \textrm{dla}\ r=5,<br />
\end{array}<br />
\right. $
oraz także
$ q \oslash 6 =<br />
\left\{<br />
\begin{array}{ll}<br />
5 & \textrm{dla}\ q=2, \\<br />
2 & \textrm{dla}\ q=5.<br />
\end{array}<br />
\right. $

Dostajemy więc zależności

\[<br />
\begin{split}<br />
a(n+1,2)=10 \cdot 2^{6n} + 2a(n,2) + 2a(n,5), \\<br />
a(n+1,5)=10 \cdot 2^{6n} + 2a(n,5) + 2a(n,2), \\<br />
b(n+1,2)=10 \cdot 2^{6n} + 2b(n,2) + 2b(n,5), \\<br />
b(n+1,5)=10 \cdot 2^{6n} + 2b(n,5) + 2b(n,2).<br />
\end{split}<br />
\]

Ponieważ $ a(1,2) = a(1,5) = 10 $ oraz $ b(1,2) =b(1,5) = 10 $, zatem pierwsze dwa wzory (spośród czterech wypisanych powyżej) prowadzą przez indukcję do wniosku, że $ a(n,2) = a(n,5) = a_n $ dla wszystkich $ n $, natomiast dwa dalsze wzory dają wniosek, że $ b(n,2) = b(n,5) = b_n $ dla wszystkich $ n $. Wzór drugi oraz wzór czwarty możemy teraz tak przepisać:

\[<br />
a_{n+1} = 10 \cdot 2^{6n} + 4 a_n,\ b_{n+1}=10 \cdot 2^{6n}+4b_n.<br />
\]

Tak więc ciągi $ (a_n) $ i $ (b_n) $ spełniają dokładnie tę samą zależność rekurencyjną. A skoro $ a_1 = b_1 = 10 $, przez indukcję wnosimy, że $ a_n = b_n $ dla wszystkich $ n $. Wniosek: iloraz $ a_n/b_n $ jest równy $ 1 $.

Komentarze

Dodaj nową odpowiedź