7090996916

W. Guzicki: Zadania z kombinatoryki 19

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

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

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

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

Zbiory możliwych wyników są różne, ale mają tyle samo elementów. To właśnie pozwala skorzystać

z reguły mnożenia.

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

•    zbiór A składa się z trójek (a, b, c) takich, że 1 < a, b, c < m oraz żadne dwie z tych trzech liczb nie są równe (czyli, inaczej mówiąc, a, 6, c 6 [m] oraz a ^ b, a ^ c, b ^ c).

Udowodnij, że |^4| = m • (m — 1) • (m — 2).

Rozwiązanie. Wykonujemy trzy czynności:

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

•    druga czynność polega na wybraniu drugiej liczby b 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 (a więc tak naprawdę w drugiej czynności wybieramy liczbę b ze zbioru [m] \ {a}),

•    trzecia czynność polega na wybraniu trzeciej liczby c ze zbioru [m]; ta czynność, niezależnie od wyników pierwszych dwóch czynności, kończy się jednym z m — 2 wyników, gdyż za trzecim razem nie możemy ponownie wybrać liczby, którą już wybraliśmy za pierwszym lub za drugim razem (czyli wybieramy liczbę c ze zbioru [m] \ {o, b}).

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

34.    Rzucamy 5 razy kostką dwudziestościenną, zapisując wyniki w kolejności rzutów. Ile jest możliwych wyników, w których żadna liczba się nie powtórzy?

Rozwiązanie. Wykonujemy pięć czynności:

•    pierwsza czynność polega na wybraniu pierwszej liczby; ta czynność kończy się jednym z 20 wyników,

•    druga czynność polega na wybraniu drugiej liczby; ta czynność, niezależnie od wyniku pierwszej czynności, kończy się jednym z 19 wyników, gdyż druga liczba nie może być równa pierwszej,

•    trzecia czynność polega na wybraniu trzeciej liczby; ta czynność, niezależnie od wyników pierwszej i drugiej czynności, kończy się jednym z 18 wyników, gdyż trzecia liczba musi być różna od pierwszych dwóch,

•    czwarta czynność polega na wybraniu czwartej liczby; ta czynność, niezależnie od wyników pierwszych trzech czynności, kończy się jednym z 17 wyników, gdyż czwarta liczba musi być różna od pierwszych trzech,

•    piąta czynność polega na wybraniu piątej liczby; ta czynność, niezależnie od wyniku pierwszych czterech czynności, kończy się jednym z 16 wyników, gdyż piąta liczba musi być różna od pierwszych czterech.

Z reguły mnożenia wynika, że łącznie możemy otrzymać 20 • 19 • 18 • 17 • 16 = 1860480 wyników.

35.    Dane są liczby naturalne n i m (takie, że 1 < n < m). Definiujemy zbiór A w następujący sposób:

•    zbiór A składa się z ciągów (ai,...,a_n) takich, że 1 < ai,..., On < m oraz żadne dwa wyrazy ciągu nie są równe (czyli, inaczej mówiąc, oi,..., On £ [m] oraz ai aj dla dowolnych i oraz j takich, że 1 < i < j < n).

Udowodnij, że |^4| = m • (m — 1) •... • (m — n + 1).

Rozwiązanie. Wykonujemy n czynności:

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

•    druga czynność polega na wybraniu drugiej liczby <22 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

Warszawa, 19-20 października 2013 r.