SKRZYNKA Z NARZĘDZIAMI MŁODEGO KOMBINATORYKA

Paweł Naroski

Wykład „Skrzynka z narzędziami młodego kombinatoryka" składa się z trzech niezależnych części. Omówione są w nich narzędzia kombinatoryczne takie jak zasada szufladkowa Dirichleta, zasada dwoistości oraz zasada włączeń i wyłączeń. Każde z nich mimo swej prostoty i „oczywistości" jest wysoce skutecznym środkiem przy rozwiązywaniu problemów natury kombinatorycznej, czyli skończonej.

Część pierwsza poświęcona jest zasadzie szufladkowej Dirichleta, która głosi, że jeśli n + 1 par skarpetek zostanie umieszczonych w n szufladkach, to będzie istnieć szufladka zawierająca co najmniej dwie pary skarpetek.

Zasada szufladkowa jest omówiona na przykładzie dwóch problemów. Pierwszym z nich jest twierdzenie z teorii liczb, które mówi, iż w każdym zbiorze n +1 liczb naturalnych, z których każda należy do zbioru {1,... , 2n}, znajdują się dwie takie, że jedna z nich dzieli drugą. Drugi to słynne twierdze­nie Erdősa-Szekeresa głoszące, iż w każdym różnowartościowym ciągu (tzn. takim, którego żadne dwa wyrazy nie są równe) długości n² + 1 znajduje się ściśle monotoniczny podciąg długości co najmniej n.

Następnie zasada szufladkowa jest wykorzystana do udowodnienia szcze­gólnego przypadku innego twierdzenia Erdősa-Szekeresa mówiącego, że dla każdej liczby naturalnej n istnieje liczba naturalna M(n) taka, że w każdym zbiorze punktów płaszczyzny mającym M(n) elementów, z których żadne trzy nie są współliniowe, istnieje n punktów, które tworzą n-kąt wypukły. W ogólności to twierdzenie należy do teorii Ramseya, której pierwszym za­rodkiem jest zasada szufladkowa Dirichleta. Uczniom zainteresowanych tą tematyką można zaproponować wykład prof. Jarosława Grytczuka nagrany również w ramach projektu „Szukając Einsteina - akademia umysłów ścisłych", który omawia te zagadnienia dokładniej. Tutaj prezentujemy jedynie przypadek n = 4, który jest ładnym przykładem zastosowania zasady szu­fladkowej w geometrii.

Wszystkie pojęcia występujące w wykładzie są raczej powszechnie znane, niemniej w celu uniknięcia nieporozumień zdefiniujemy te najważniejsze.

Podciąg. Niech L = (a₁,... ,a_n) będzie ciągiem. Podciągiem ciągu L nazywamy każdy ciąg (a_i1,... ,a_ik), gdzie i₁ < ... < i_k.

Podzielność. Mówimy, że liczba naturalna d dzieli liczbę naturalną n, jeśli istnieje liczba naturalna l taka, że n = l • d.

Ścisła monotoniczność. Ciąg (a₁,... , a_n) nazywamy ściśle rosnącym, jeśli a_i<aj dla i < j. Ciąg (a₁,... , a_n) nazywamy ściśle malejącym, jeśli a_i>aj dla i < j. Ciąg ściśle rosnący lub ściśle malejący nazywamy ciągiem ściśle monotonicznym.

Wypukłość. Wielokąt nazwiemy wypukłym, jeśli odcinek łączący każde dwa punkty tego wielokąta jest w nim zawarty.

W ramach pracy z wykładem można omówić uogólnioną zasadę szufladkową, która głosi, że jeśli n par skarpetek rozmieścimy w m szufladkach, to będzie istnieć szufladka zawierająca co najmniej n/m par skarpetek oraz będzie istnieć szufladka zawierająca co najwyżej n/m par skarpetek. Pierwszym ciekawym zadaniem może być wykazanie prawdziwości tego twierdzenia. Inne można znaleźć w zeszycie ćwiczeń przygotowanym do tego wykładu.

Należy zwrócić uwagę, żeby uczeń za każdym razem świadomie korzystał z zasady szufladkowej. Narzędzie to jest tak intuicyjnie „oczywiste", że stosowane jest na zasadzie argumentu zdroworozsądkowego, co do pewnego stopnia zaawansowania jest akceptowalne, ale od pewnego miejsca, gdzie poziom abstrakcji przekracza codzienną intuicję, prowadzi zazwyczaj do błędów. Zwracanie uwagi przez ucznia na powody, dzięki którym każdy krok rozumowania jest poprawny, przygotowuje go do wkraczania na kolejne poziomy abstrakcji, co jest bardzo pożądane dla kandydata do studiowania nauk ścisłych (nie tylko matematyki, ale także informatyki, fizyki, chemii itp.).

Druga, najkrótsza, część wykładu poświęcona jest zasadzie dwoistości, która jest niczym innym jak szczególnymi sformułowaniami prawa wyłączonego środka.

Na początku opisane są trudności występujące przy dowodzeniu nieistnienia obiektów o żądanych własnościach. Zrobione jest to na przykładzie twierdzenia mówiącego, że n nie jest liczbą algebraiczną. Następnie zaprezentowane są dwa problemy pokrywania szachownicy kostkami domina.

Zasada dwoistości może być punktem wyjścia do zapoznania uczniów z innymi prawami logiki klasycznej.

Trzecia i ostatnia część wykładu traktuje o zasadzie włączeń i wyłączeń, czyli wzorze podającym liczność sumy mnogościowej danej rodziny zbiorów w języku liczności przecięć (części wspólnych) tychże zbiorów. (Czasem wzór ten nazywa się wzorem Sylvestera, a zasadą włączeń i wyłączeń nazywa się analogiczny wzór na liczbę elementów zadanej przestrzeni leżących poza sumą danych zbiorów.)

Na początku pokazany jest przykład zagadnienia, w którym potrzeba narzędzia takiego jak zasada włączeń i wyłączeń ujawnia się w sposób naturalny, a mianowicie problem roztargnionej sekretarki. Mamy n listów skierowanych do n różnych ludzi. Roztargniona sekretarka wkłada listy zupełnie losowo do zaadresowanych wcześniej kopert. Jakie jest prawdopodobieństwo zdarzenia, iż żaden adresat nie dostanie właściwego listu?

Następnie omawiane są proste przykłady ukazujące trudność leżącą w problemie ustalania liczby elementów sumy zbiorów oraz prezentowane jest jego rozwiązanie dla n = 2, 3, 4. W dalszej kolejności rozwiązane jest przy użyciu zasady włączeń i wyłączeń zadanie polegające na zbadaniu ile liczb naturalnych mniejszych od 1000 nie dzieli się ani przez 2, ani przez 3, ani przez 11.

W końcu podane jest rozwiązanie problemu roztargnionej sekretarki z dyskusją rozwiązania.

Prawdopodobieństwo. Chodzi o klasyczną definicję prawdopodobieństwa, tzn. jeśli Ω jest zbiorem zdarzeń elementarnych, a A ∈ Ω, to prawdopodobieństwo zdarzenia A wynosi P(A) = |A|/|Ω|.

Podłoga. Podłogą liczby rzeczywistej x nazywamy największą liczbę całkowitą nie większą niż x, czyli zaokrąglenie x „w dół", funkcję podłogi oznaczamy symbolem [x].

Na problem roztargnionej sekretarki można spojrzeć zarówno jak na problem kombinatoryczny, jak i probabilistyczny. Może to stać się przyczynkiem do wprowadzenia uczniów w bardziej zaawansowane tajniki rachunku praw­dopodobieństwa. Pomocą w tym może być wykład dra Krzysztofa Brysia nagrany również w ramach projektu „Szukając Einsteina - akademia umysłów ścisłych".

Wykład dotyczy podstawowych, wręcz fundamentalnych, narzędzi matematycznych. W związku z tym ich stosowanie nie ogranicza się jedynie do rozwiązywania problemów matematycznych, ale występuje w wielu rozumowaniach, dedukcjach, które każdy z nas przeprowadza każdego dnia w życiu codziennym. W większości przypadków stosowane są one bezwiednie. Pożądanym jest jednak, aby uczeń, który ma w przyszłości studiować nauki ścisłe, zaczynał powoli stosować świadomie narzędzia matematyczne zarówno w po­znawaniu nauk ścisłych w szkole, jak i we wszelkich rozumowaniach, które przeprowadza.

Jeśli chodzi o zastosowania zaprezentowanych w wykładzie narzędzi, to jako już się rzekło, są one powszechnie wykorzystywane we wszelakich rozumowaniach kombinatorycznych i wszędzie tam, gdzie kombinatoryka znajduje zastosowanie, tam można mówić o zastosowaniach zasady szufladkowej Dirichleta, zasady dwoistości czy zasady włączeń i wyłączeń. A kombinatoryka znajduje zastosowanie przede wszystkim w informatyce w jej rozmaitych przejawach jak teoria automatów i obliczeń (gdzie np. zasada szufladkowa wykorzystana jest w dowodzie jednego z podstawowych wyników tej dziedziny, tzw. lematu o pompowaniu), teoria kodów (gdzie poza kombinatoryką stosuje się w jeszcze większym stopniu algebrę i teorię liczb, a ten temat stanowi przedmiot wykładu dr Barbary Roszkowskiej-Lech, który również został nagrany w ramach projektu „Szukając Einsteina - akademia umysłów ścisłych") czy w końcu przy projektowaniu i analizie algorytmów. Jednym z niedawnych sukcesów tej ostatniej dziedziny jest szybki algorytm (w stosunku do algorytmów konkurencyjnych) kolorowania wierzchołkowego grafów, którego zasada działania opiera się na zasadzie włączeń i wyłączeń. (Kolorowanie wierzchołkowe polega na przypisaniu wierzchołkom danego grafu pewnych etykiet (kolorów) w taki sposób, aby sąsiednie wierzchołki otrzymały różne etykiety. Więcej szczegółów można znaleźć w książce Wilsona, której dane podane są niżej.) Problemy kolorowania pojawiają się w wielu aspektach przemysłu, jak problemy przydziału zadań czy projektowanie planów.

Pomocna przy pracy z wykładem oraz przy wielu innych okazjach pracy z uczniami może być również poniższa literatura.

1. Aigner, Ziegler, Dowody z Księgi, PWN, 2004

2. Piegat, Zadania Hugona Steinhausa, GiS, 2005

3. Ross, Wright, Matematyka dyskretna, PWN, 1996

4. Palka, Ruciński, Wykłady z kombinatoryki, WNT, 1998

5. Wilson, Wprowadzenie do teorii grafów, PWN, 1985

Podręcznik dla nauczyciela

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

4

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

---