7090996906

10 W. Guzicki: Zadania z kombinatoryki

Rozwiązanie. Mamy dwa sposoby rozwiązania zadania. W sposobie pierwszym definiujemy pomocniczy zbiór B, tak jak w zadaniu 12. Wówczas z zadania 12 wynika, że |i4| = |B| i z zadania 9 wynika, że \B\ = \S_k(n + k-l)\.

Drugi sposób rozwiązania zadania polega na uogólnieniu rozumowania pokazanego w rozwiązaniach zadań 10 i 11. Mamy znów n — 1 zer rozdzielających n ponumerowanych miejsc. Ciąg (ai,... , a*) łączymy w parę z ciągiem zerojedynkowym utworzonym w ten sposób, że w miejsca o numerach ai,..., a* wpisujemy jedynkę; w przypadku, gdy któreś wyrazy rozpatrywanego ciągu są równe, to w miejsce o tym numerze wpisujemy obok siebie odpowiednią liczbę jedynek. Szczegóły pozostawię jako ćwiczenie.

4. Reguła dodawania

Z reguły dodawania łatwo wynikają dwa ważne wzory (są to szczególne przypadki tzw. zasady włączeń i wyłączeń):

\AUB\ = \A\ + \B\-\AnB\

oraz

\A U B U C\ = |j4| + \B\ + \C\ — \A n B\ - \A Cl C| — \B n C\ + \A n B n C\.

Podobny wzór można napisać także w przypadku większej liczby zbiorów (ze wzoru na liczbę elementów sumy 4 zbiorów skorzystam w jednym z dalszych zadań; wzór na liczbę elementów sumy 5 zbiorów był wykorzystywany w zadaniu 4 z zawodów I stopnia XLVI Olimpiady Matematycznej). Popatrzmy teraz na kilka zadań, w których można zastosować regułę dodawania.

14.    Na ile sposobów można wybrać przedstawiciela parlamentu, którym ma być poseł lub senator? Dla przypomnienia: Sejm składa się z 460 posłów, Senat ze 100 senatorów i żaden senator nie może jednocześnie być posłem.

Rozwiązanie. Możemy wykonać dwie czynności: pierwsza czynność polega na wybraniu posła, druga czynność polega na wybraniu senatora. Pierwsza czynność kończy się jednym z 460 wyników, druga kończy się jednym ze 100 wyników. Żaden wynik jednej czynności nie jest wynikiem drugiej. Teraz wykonujemy jedną z tych dwóch czynności. Mamy zatem 560 możliwych wyników i tyle jest sposobów wybrania przedstawiciela.

15.    W klasie liczącej 30 uczniów wielu uczniów gra w brydża lub szachy (lub w obie gry razem). W brydża gra 23 uczniów, w szachy 14 uczniów, w obie gry razem gra 9 uczniów. Ilu uczniów nie gra w żadną z tych gier?

Rozwiązanie. Zastosujemy zasadę włączeń i wyłączeń. Niech B oznacza zbiór uczniów grających w brydża i niech S oznacza zbiór uczniów grających w szachy. Mamy zatem:

\BuS\ = \B\ + \S\-\BnS\.

Wiemy, że \B\ = 23, |Sj = 14 oraz \B n S| = 9. Zatem

\B U S\ = 23 + 14 — 9 = 28,

skąd wynika, że w żadną z tych gier nie gra dwóch uczniów.

16.    W klasie liczącej 30 uczniów każdy uczeń gra w brydża lub szachy (lub w obie gry razem). W brydża gra 19 uczniów, w szachy 14 uczniów. Ilu uczniów gra w obie gry?

Rozwiązanie. Zastosujemy zasadę włączeń i wyłączeń. Niech B oznacza zbiór uczniów grających w brydża i niech 5 oznacza zbiór uczniów grających w szachy. Mamy zatem:

|BuSj = |B| + |$|-|Bn5|.

Z założenia wiemy, że \B U £| = 30, bo każdy uczeń gra w którąś z tych gier. Ponadto |B| = 19 oraz |5| — 14. Zatem

30 = 19 + 14 — |B Cl S|,

skąd wynika, że \B fi S| = 3. Zatem w obie gry gra trzech uczniów.

Warszawa, 19-20 października 2013 r.