7090996914

18 W. Guzicki: Zadania z kombinatoryki

•    druga czynność polega na wybraniu drugiej liczby ze zbioru [m]; ta czynność, niezależnie od wyniku pierwszej czynności, także kończy się jednym z m wyników, gdyż za drugim razem możemy ponownie wybrać dowolną liczbę, nawet jeśli ją już wybraliśmy za pierwszym razem,

•    ostatnia, n-ta czynność polega na wybraniu n-tej liczby ze zbioru [m]; ta czynność, niezależnie od wyniku pierwszych n — 1 czynności, także kończy się jednym z m wyników, gdyż za ostatnim razem możemy ponownie wybrać dowolną liczbę, nawet jeśli ją już wybraliśmy raz lub więcej razy wcześniej.

Z reguły mnożenia wynika, że łącznie możemy otrzymać m-m -... ■ m = mⁿ wyników.

n czynników

29.    Dana jest liczba naturalna n > 1. Udowodnij, że wówczas |S(n)| = 2".

Rozwiązanie. Wystarczy skorzystać z poprzedniego zadania, w którym przyjmujemy m = 2.

30.    Dane są liczby naturalne n i m (takie, że n, m > 1) i dany jest zbiór A taki, że | A| = m. Definiujemy zbiór B w następujący sposób:

•    zbiór B składa się z ciągów (ai,..., a_n) takich, że a\,... ,a_n G A.

Udowodnij, że |A| = mⁿ.

Rozwiązanie. Wykonujemy n czynności:

•    pierwsza czynność polega na wybraniu pierwszego elementu ze zbioru A; ta czynność kończy się jednym z m wyników,

•    druga czynność polega na wybraniu drugiego elementu ze zbioru A; ta czynność, niezależnie od wyniku pierwszej czynności, także kończy się jednym z m wyników, gdyż za drugim razem możemy ponownie wybrać dowolny element zbioru A, nawet jeśli go już wybraliśmy za pierwszym razem,

•    ...

•    ostatnia, n-ta czynność polega na wybraniu n-tego elementu ze zbioru A; ta czynność, niezależnie od wyniku pierwszych n — 1 czynności, także kończy się jednym z m wyników, gdyż za ostatnim razem możemy ponownie wybrać dowolny element zbioru A, nawet jeśli go już wybraliśmy raz lub więcej razy wcześniej.

Z reguły mnożenia wynika, że łącznie możemy otrzymać m-m -... ■ rn = mⁿ wyników.

n czynników

31.    Rzucamy 5 razy kostką dwudziestościenną, zapisując wyniki w kolejności rzutów. Ile jest możliwych wyników, w których żadna z wyrzuconych liczb nie jest większa od k (gdzie 1 < k < 20)?

Rozwiązanie. Wystarczy skorzystać z poprzedniego zadania, w którym przyjmujemy, że A = [fc].

32.    Dana jest liczba naturalna m> 2. Definiujemy zbiór A w następujący sposób:

•    zbiór A składa się z par (a, 6) takich, że 1 < a,b < m oraz a b (czyli, inaczej mówiąc, a,b & [m] oraz a ^ b).

Udowodnij, że \A\ = m - (m — 1).

Rozwiązanie. Wykonujemy dwie czynności:

•    pierwsza czynność polega na wybraniu pierwszej liczby ze zbioru [m]; ta czynność kończy się jednym z m wyników,

•    druga czynność polega na wybraniu drugiej liczby ze zbioru [m]; ta czynność, niezależnie od wyniku pierwszej czynności, kończy się jednym z m — 1 wyników, gdyż za drugim razem nie możemy ponownie wybrać liczby, którą już wybraliśmy za pierwszym razem.

Z reguły mnożenia wynika, że łącznie możemy otrzymać m ■ (m — 1) wyników.

Uwaga. Zauważmy, że we wszystkich zadaniach, z wyjątkiem ostatniego, zbiór wyników każdej czynności był zawsze taki sam, niezależnie od wyników poprzednio wykonanych czynności. Wynikało to stąd, że w kolejnych czynnościach mogliśmy wybrać dowolny element tego samego ustalonego zbioru. W ostatnim zadaniu jest inaczej. W zależności od wyniku pierwszej czynności, zbiór możliwych wyników drugiej czynności będzie inny. Popatrzmy na przykład. Niech rra = 5. Pierwsza czynność kończy się jednym z 5 wyników — tymi wynikami są liczby od 1 do 5. A oto możliwy zbiór wyników drugiej czynności, w zależności od wyniku pierwszej:

•    jeśli pierwsza czynność kończy się wynikiem 1, to zbiorem możliwych wyników drugiej czynności jest {2,3,4,5},

Warszawa, 19-20 października 2013 r.