5600235756

6 Metody zliczania zbiorów i funkcji 13

1.    przenosimy n — 1 górnych krążków z A na B posługując się wieżą C, wymaga to a_n-1 ruchów,

2.    przenosimy dolny, największy krążek z A na C, to jest jeden ruch,

3.    przenosimy n — 1 krążków zBnaC posługując się wieżą A, wymaga to a_n-\ ruchów.

Ostatecznie mamy

0-n

dn— 1 + 1 + dji— i — 2(l_n—i + 1,

i w postaci jawnej

Możemy teraz odpowiedzieć na zadane na początku pytanie. Przeniesienie n krążków zajmie ponad 3000000000000 lat. Komputer z procesorem 3GHz wykonywał by to zadanie ponad 1000 lat.

6    Metody zliczania zbiorów i funkcji

Licząc samochody na parkingu, komputery w pracowni, albo studentów na wykładzie, zliczanym elementom „przyczepiamy” etykietki z kolejnymi liczbami naturalnymi zaczynając od 1. Gdy wyczerpiemy Uczone elementy to ostatnia z przyczepionych etykiet mówi ile w zbiorze jest elementów. Ta procedura to nic innego jak konstrukcja bijekcji / z zadanego zbioru X na podzbiór {1,2,... ,n} zbioru N.

Tak więc podstawy formalne do zagadnienia zliczania zbiorów i funkcji już mamy. Zostały one wprowadzone w podrozdziale 3 jako równohcznośś zbiorów. Aby pohczyć ile dany zbiór X zawiera elementów należy wskazać bijekcję / z X na zbiór, którego ilość elementów znamy.

6.1 Zasada mnożenia

Twierdzenie 6.1 (Zasada mnożenia). Dla dowolnych zbiorów skończonych A\, A2,.. •, A_n mamy

|Ai x A₂ x x A_n\ = I/IjI ■ |A₂|.....IA.I-

Przykład 6.2. W turnieju szachowym biorą udział dwie drużyny: czerwonych i niebieskich. Drużyna czerwonych liczy 5 zawodników, natomiast drużyna niebieskich

7    zawodników. Ile różnych indywidualnych pojedynków może być stoczonych, jeśli zawodnicy jednej drużyny nigdy ze sobą nie walczą?

Niech C i N będą zbiorami odpowiednio czerwonych i niebieskich. Każdy pojedynek może być interpretowany jako uporządkowana para (c, n), gdzie c G C, n € N. Zatem liczba pojedynków to liczność zbioru C x N. Z zasady mnożenia 6.1 mamy

\C x N\ = \C\ ■ |JV| = 5 • 7 = 35.