262080416

MATEMATYKA DYSKRETNA 2010

2.3.1.    Zasada włączania-wyłączania (metoda sita).

Twierdzenie 2. (Formuła Sita¹ lub Zasada Włączania i Wyłączania) Niech Ai,A2,...,A_n będą zbiorami skończonymi. Wówczas zachodzi wzór

\A₁ u a₂ u ... u An\ = Y. (-i)^fc+1!^i₁ n At₂ n...n A_ik\.

1<*i<*2 <-..<ik <n

Formułę sita wykazaliśmy metodą indukcji matematycznej.

2.3.2.    Miasta Parzyste i Nieparzyste. W mieście P o 32 mieszkańcach kluby są tworzone według następujących zasad.

(i)    Każdy klub ma parzystą liczbę członków.

(ii)    Przecięcie dowolnych dwóch klubów ma parzystą liczbę elementów. Natomiast w mieście N (także o 32 mieszkańcach) kluby są tworzone według tak,

by

(a)    Każdy klub miał nieparzystą liczbę członków.

(b)    Przecięcie dowolnych dwóch klubów miało parzystą liczbę elementów. Problem. Jaka jest maksymalna liczba klubów w P, a jaka w N?

Wykazaliśmy, że w P można utworzyć co najmniej 2¹⁶ > 65536 klubów, podczas gdy w N co najwyżej 32.

Bardzo się zdziwiliśmy!

Oszacowanie liczby klubów w P znaleźliśmy stosując metody czysto kombinato-ryczne. Dla oszacowania liczby klubów w N stosowaliśmy podstawowe wiadomości dotyczące wymiaru pewnej przestrzeni liniowej. Przydała się więc algebra liniowa.

^Dokładniej: "sita Eratostenesa”. Eratostenes, (276-194 p.n.e) był kustoszem Biblioteki Aleksandryjskiej i jednym z największych umysłów starożytności. Sito Eratostenesa służyło do "odsiewania” liczb pierwszych od "plew” innych liczb. Jego innym, wielkim osiągnięciem była próba zmierzenia promienia Ziemi przez zmierzenie długości cieni rzucanych w południe przez dwie tyczki: jednej ustawionej w Aleksandrii, drugiej zaś w Syene (dzisiejszy Asuan). Wynik jaki otrzymał różnił sie tylko o 1% od nam znanego, a było to w czasach kiedy w kulistość Ziemi wierzył mało kto!