7090996915

W. Guzicki: Zadania z kombinatoryki

ZADANIA Z KOMBINATORYKI

czyli o sztuce zliczania Wojciech Guzicki

Wykłady z kombinatoryki, które tu przedstawiam, są przeznaczone dla nauczycieli. Nie są natomiast podręcznikiem dla ucznia. Gdy uczę kombinatoryki w szkole, staram się nie nadużywać formalizmu i symboliki teoriomnogościowej. Definicje pojęć kombinatorycznych i podstawowe zasady kombinatoryczne podaję uczniom i zapisuję na tablicy słowami, bez odwoływania się do zapisu bardziej formalnego. Tak też formułuję większość zadań. W tym wykładzie w wielu miejscach będę postępował tak samo. Jednak — jak napisałem na początku — jest to wykład dla nauczycieli, do których można (a może nawet należy) mówić także językiem bardziej formalnym. Dobrze jest, by nauczyciel zobaczył, w jaki sposób można nieformalne rozumowania kombinatoryczne zapisać w języku, który poznał w czasie studiów wyższych. Tym językiem jest oczywiście język teorii mnogości.

Chcę jednak podkreślić, że formalizm na ogół utrudnia, a nie ułatwia zrozumienie — chyba, że jesteśmy z tym formalizmem bardzo dobrze oswojeni. Dla ucznia — niezależnie od tego, czy jest to uczeń gimnazjum czy liceum — formalizm teoriomnogościowy jest raczej nowością. Używanie formalizmu stawia zatem ucznia wobec podwójnej trudności: odczytania, o co naprawdę chodzi w zadaniu czy rozwiązaniu zadania i zrozumienia toku rozumowania zapisanego w niecodzienny (dla niego) sposób. Kombinatoryka jest takim działem matematyki, w którym prawie niepotrzebna jest bogata teoria. Rozumowania kombinatoryczne nie wykorzystują skomplikowanych pojęć matematycznych i wymagają właściwie tylko sprytnych pomysłów — inaczej mówiąc, zgodnie z nazwą tej dziedziny matematyki, kombinowania. Dlatego na ogół nie jest potrzebny żaden skomplikowany formalizm. Starajmy się przedstawić problemy kombinatoryczne w sposób jak najprostszy, językiem codziennym, najbardziej zrozumiałym dla ucznia, i oczekujmy od niego rozumowań wyrażonych w takim samym języku.

W niektórych sytuacjach formalizm staje się bardziej potrzebny. Dotyczy to nielicznych zadań pokazanych w tych wykładach. W tych zadaniach będę zatem takiego formalizmu używał. Pamiętajmy jednak, że są to zadania trudne, nieraz znacznie wykraczające ponad program szkolny, nierzadko są to zadania o trudnościach olimpijskich. Przytaczam je tutaj głównie po to, by pokazać nauczycielom, że w dość prosty sposób można uzyskać niebanalne rezultaty.

1. Podstawowe oznaczenia i terminologia

Wszystkie zbiory, z którymi w tych wykładach będziemy mieli do czynienia, są zbiorami skończonymi. Inaczej mówiąc, w tych wykładach będę pokazywać, na czym polega sztuka zliczania elementów zbiorów skończonych. Oczywiście nie tłumaczę uczniom, co to są zbiory skończone; zakładam, że istnieje coś takiego jak nasza wspólna intuicja skończoności. Skończone jest to, co daje się policzyć. Jeśli A jest zbiorem skończonym, to symbolem \A\ oznaczam liczbę elementów zbioru A. Nie będę używał określenia moc zbioru. Dla dowolnej liczby naturalnej n > 1 symbolem [n] będę oznaczał zbiór wszystkich liczb naturalnych od 1 do n. Ponadto [0] jest zbiorem pustym:

[n] = {1,..., n} dla n > 1,    [0] = 0.

Podstawową zasadą kombinatoryki, na której opierają się wszystkie dalsze rozważania, jest:

Inaczej mówiąc, zbiór [n] jest wzorcowym przykładem zbioru n-elementowego.

Ciągiem zerojedynkowym nazywam ciąg skończony (aj.,..., a„), którego każdy wyraz jest zerem lub jedynką, czyli taki, że

ai,...,a„ € {0,1}.

Zbiór wszystkich ciągów zerojedynkowych długości n będę oznaczał symbolem S(n). Symbolem Sfc(n) oznaczam zbiór wszystkich ciągów zerojedynkowych, w których jest dokładnie k wyrazów równych 1:

Sk{n) = {{cn,...,a_n) € S{n) \ |{i : Oj = 1}| = k}.

Warszawa, 19-20 października 2013 r.