7090996921

W. Guzicki: Zadania z kombinatoryki

jedynek. Nietrudno zauważyć, że spełnione są także dwa pozostałe warunki (R2) i (R3), co dowodzi, że zbiory A i B mają tyle samo elementów.

Uwaga. W dalszym ciągu (zadanie 29) wykażemy, że istnieje 2" ciągów zerojedynkowych długości n. Stąd wynika, że oba zbiory A i B mają po 2¹⁴ elementów.

3.    Udowodnij, że liczba ciągów zerojedynkowych długości 16, w których występuje parzysta liczba jedynek, jest równa liczbie ciągów zerojedynkowych długości 16, w których występuje nieparzysta liczba jedynek.

Rozwiązanie. Metoda łączenia w pary, opisana w rozwiązaniu poprzedniego zadania, nie działa. Jeśli bowiem tym razem w ciągu (aj, a^, ■ ■ ■, aie), ^w którym występuje parzysta liczba jedynek, zastąpimy zera jedynkami i jedynki zerami, to otrzymamy ciąg, w którym także występuje parzysta liczba jedynek. Potrzebny jest więc inny sposób łączenia w pary. Ten nowy sposób polega na tym, by tylko na ostatnim miejscu zastąpić zero jedynką, a jedynkę zerem. Zatem ciąg (oi,..., ais, «ie) łączymy w parę z ciągiem (ai,..., ais, 1 — ai6). To znaczy, że:

•    ciąg (ai,...,ai5,0) łączymy w parę z ciągiem (ai,... ,ais, 1),

•    ciąg (ai,..., ais, 1) łączymy w parę z ciągiem (a_x,...,ai₅,0).

Na przykład, ciąg 0110001001110001 łączymy w parę z ciągiem 0110001001110000. Sprawdzenie, że spełnione są warunki (Rl), (R2) i (R3) opisane w zasadzie równoliczności, pozostawię jako ćwiczenie. Uwaga. Zauważmy, że sposób łączenia w pary opisany w tym rozwiązaniu jest dobry dla ciągów dowolnej długości. Stąd wynika, że dla każdego n istnieje 2^n_1 ciągów zerojedynkowych długości n, w których występuje parzysta liczba jedynek i tyle samo ciągów, w których występuje nieparzysta liczba jedynek.

4.    Udowodnij, że liczba ciągów zerojedynkowych długości 15, w których występuje więcej jedynek niż zer, jest równa liczbie ciągów zerojedynkowych długości 15, w których występuje więcej zer niż jedynek.

Rozwiązanie. Sposób łączenia w pary opisany w rozwiązaniu zadania 1 jest dobry.

Uwaga. W uwadze po zadaniu 2 wspomniałem, że istnieje 2ⁿ ciągów zerojedynkowych długości n. Wynika stąd, że jeśli liczba n jest nieparzysta, to istnieje 2^n_1 ciągów zerojedynkowych długości n, w których jest więcej jedynek niż zer i tyle samo ciągów zerojedynkowych długości n, w których jest więcej zer niż jedynek. Oczywiście, jeśli n jest liczbą parzystą, to także liczba ciągów zerojedynkowych długości n, w których jest więcej jedynek niż zer, jest równa liczbie ciągów zerojedynkowych długości n, w których jest więcej zer niż jedynek. W tym przypadku nie możemy jednak twierdzić, że w obu tych zbiorach znajduje się po 2^n_1 ciągów, gdyż istnieją ciągi, w których jest tyle samo jedynek i zer. Dopóki nie dowiemy się, ile jest tych ostatnich ciągów, nie będziemy mogli obliczyć, ile elementów ma zbiór ciągów, w których jest więcej jedynek i zbiór ciągów, w których jest więcej zer.

5.    Niech n > 6. Rozważamy zbiór S ciągów (a_x,..., a_n), których wyrazy należą do zbioru {0,1,..., 9}. Można powiedzieć, że elementami zbioru S są liczby mające co najwyżej n cyfr; z tym tylko, że jeśli liczba ma mniej niż n cyfr, to jej zapis dziesiętny jest uzupełniany na początku odpowiednią liczbą zer. Teraz w zbiorze S wyróżniamy dwa podzbiory. Zbiór A składa się z tych ciągów, w których każda liczba parzysta (tzn. 0, 2, 4, 6 i 8) występuje dokładnie jeden raz, pozostałe wyrazy ciągu są natomiast liczbami nieparzystymi. Zbiór B składa się natomiast z tych ciągów, w których każda liczba nieparzysta (tzn. 1, 3, 5, 7 i 9) występuje dokładnie jeden raz, pozostałe wyrazy ciągu są zaś liczbami parzystymi. Udowodnij, że zbiory A i B mają tyle samo elementów, tzn. \A\ = \B\.

Rozwiązanie. Ciąg (oi,... ,a„) należący do zbioru A łączymy w parę z ciągiem (6_X,..., b_n) zdefiniowanym w następujący sposób:

•    jeśli aj jest liczbą parzystą, to 6, = a_x + 1,

•    jeśli a, jest liczbą nieparzystą, to bi = a, — 1.

Popatrzmy na kilka przykładów. Niech n = 8. Wówczas:

•    ciąg 10386524 łączymy w parę z ciągiem 01297435,

•    ciąg 02468111 łączymy w parę z ciągiem 13579000,

•    ciąg 97586420 łączymy w parę z ciągiem 86497531.

Sprawdzenie, że ten sposób łączenia w pary jest dobry, pozostawię jako ćwiczenie.

Warszawa, 19-20 października 2013 r.