7090996920

W. Guzicki: Zadania z kombinatoryki

ile pełnych, siedmioelementowych grup. A więc 128. A jak jest w przypadku dzielenia przez 17? Tym razem mamy 52 pełne siedemnastoelementowe grupy i jedną niepełną grupę. Ale ta ostatnia grupa ma

16 elementów:

100	101	102	103 .	. 114	115	116
117	118	119	120 .	. 131	132	133
134	135	136	137 .	. 148	149	150
967	968	969	970 .	. 981	982	983
984	985	986	987 .	. 998	999

W każdej grupie liczba podzielna przez 17 stoi na trzecim miejscu. Zatem w tej ostatniej grupie też znajduje się liczba podzielna przez 17. Stąd wynika, że szukanych liczb jest 53, mianowicie o jedną więcej niż liczba pełnych siedemnastoelementowych grup. Ten sposób rozwiązania musi więc uwzględniać także to, gdzie w rozważanych grupach liczb stoją liczby podzielne przez tę liczbę, przez którą mamy dzielić.

Pokażę teraz, w jaki sposób możemy rozwiązać zadanie za pomocą zasady równoliczności. Niech A będzie zbiorem liczb trzycyfrowych podzielnych przez 7. Są to liczby postaci 7k, przy czym 100 < 7k < 999. Stąd wynika, że 15 < k < 142. Zatem

A = {7k : 15 <k< 142}.

Łączymy w parę liczbę 7k z liczbą k. W ten sposób połączymy w pary liczby ze zbioru A z liczbami ze zbioru {15,16,..., 142}. Ten ostatni zbiór ma 128 elementów, a więc |A| = 128. Podobnie możemy pokazać, że zbiór liczb trzycyfrowych podzielnych przez 17 ma postać

{17fc : 6<fc<58}.

Ten zbiór ma zatem tyle elementów, co zbiór {6,7,..., 58}, czyli 53 elementy. Wreszcie zbiór liczb trzycyfrowych, które przy dzieleniu przez 7 dają resztę 1, to zbiór

{106,113,120,...,995} = {7k+ 1 : 15 < k < 142}.

Ma on 128 elementów. Podobnie zbiór liczb trzycyfrowych dających resztę 6 przy dzieleniu przez 7, to zbiór

{104,111,118,..., 993} = {7k + 6 : 14 < k < 141}.

Ten zbiór też ma 128 elementów. Wreszcie zbiór liczb trzycyfrowych dających resztę 4 przy dzieleniu przez 7, to zbiór

{102,109,116,...,991,998} = {7fc + 4 : 14 < fc < 142}.

Ten zbiór ma 129 elementów.

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

Rozwiązanie. Najprostsze rozwiązanie, które uczniowie znajdują najczęściej, polega na następującym łączeniu ciągów w pary. Przypuśćmy, że dany jest ciąg (ai,a2,..., ais), ^w którym jest parzysta liczba jedynek. Łączymy go w parę z ciągiem (6i, 62,..., &15) określonym za pomocą wzoru:

bi = l-ai dla i = 1,2,..., 15.

Inaczej mówiąc każde zero zamieniamy na jedynkę i każdą jedynkę zamieniamy na zero:

•    jeśli aj = 0, to 6j = 1,

•    jeśli a, = 1, to b, = 0.

Na przykład, ciąg 011000100111000 łączymy w parę z ciągiem 100111011000111. Oczywiście, jeśli w ciągu (01,02, • • •, ais) była parzysta liczba jedynek, to była nieparzysta liczba zer. Zatem w ciągu (61,62,...,615) występuje nieparzysta liczba jedynek. Stąd wynika, że spełniony jest warunek (Rl) z zasady równoliczności, gdzie A jest zbiorem ciągów z parzystą liczbą jedynek, zaś B jest zbiorem ciągów z nieparzystą liczbą

Warszawa, 19-20 października 2013 r.