XLVIII OM - I - Zadanie 8

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

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,

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

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

$ \begin{split} X_k = \{6k+1, 6k+2, 6k+3, 6k+4, 6k+5, 6k+6\},\\ Y_k = \{7k+1, 7k+2, 7k+3, 7k+4, 7k+5, 7k+6\}, \end{split} $

oraz

$ X = X_0 \cup X_1 \cup \ldots \cup X_{n-1} ( = \{1,2,\ldots,6n\}),\quad Y = Y_0 \cup Y_1 \cup \ldots \cup Y_{n-1}, $

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

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

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:

$ \qquad (2) \textrm{jeśli}\ x \in X_k,\ \textrm{to}\ h(x) \in Y_k,\ h(x) \equiv 3^x (\mathrm{mod} 7). $

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

$ \qquad (3) 3^u \equiv 3^v (\mathrm{mod} 7). $

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

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

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}$ :

$ 3^{6(k+1)} \equiv 3^{6(k+1)} \cdot 3^{v-u} (\mathrm{mod} 7). $

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:

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

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

$ y_i = h(x_i) \equiv 3^{x_i} (\mathrm{mod} 7) $

(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:

$ 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); $

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

$ s(A) \equiv 5 (\mathrm{mod} 6)\ \textrm{wtedy i tylko wtedy, gdy}\ p(h(A)) \equiv 5 (\mathrm{mod} 7). $

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

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

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:

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

$ a_n=a(n,5), \ b_n = b(n,5). $

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:

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

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

$ \qquad (6) a(n+1,r) = \sum_{j=0}^5 a(1,j) \cdot a(n, r \ominus j). $

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

$ \qquad (7) b(n+1,q) = \sum_{i=0}^6 b(1,i) \cdot b(n, q\oslash i); $

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:

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

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

$ \begin{split} 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) =\\ &= 10 \sum_{j=0}^5 a(n,r\ominus j) + 2a(n,r)+2a(n,r\ominus 3) \end{split} $

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

$ \begin{split} 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) =\\ &= 10 \sum_{i=1}^6 b(n,q\oslash i) + 2b(n,q)+2b(n,q\oslash 6) \end{split} $

(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ć

$ \begin{split} a(n+1, r) = 10 \cdot 2^{6n} + 2a(n,r) + 2a(n,r \ominus 3),\\ b(n+1, q) = 10 \cdot 2^{6n} + 2b(n,q) + 2b(n,q \ominus 6). \end{split} $

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

Dostajemy więc zależności

$ \begin{split} a(n+1,2)=10 \cdot 2^{6n} + 2a(n,2) + 2a(n,5), \\ a(n+1,5)=10 \cdot 2^{6n} + 2a(n,5) + 2a(n,2), \\ b(n+1,2)=10 \cdot 2^{6n} + 2b(n,2) + 2b(n,5), \\ b(n+1,5)=10 \cdot 2^{6n} + 2b(n,5) + 2b(n,2). \end{split} $

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ć:

$ a_{n+1} = 10 \cdot 2^{6n} + 4 a_n,\ b_{n+1}=10 \cdot 2^{6n}+4b_n. $

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