Kombinatoryka. Matematyka olimpijska

SERIA Matematyka olimpijska

autorzy: Beata Bogdańska, Adam Neugebauer

Książka prezentuje podstawowe pojęcia i metody z zakresu teorii mnogości i matematyki dyskretnej. Niemal cała zawartość skryptu (poza pojęciami i metodami całkowicie elementarnymi) wykracza poza zakres programu nauczania szkolnego. Tematyka ta była jednak inspirowana zadaniami z narodowych i międzynarodowych olimpiad matematycznych. Szczególnie ciekawe, a rzadko spotykane w szkole są zadania o rozstrzyganiu niepustości zbiorów za pomocą dowodów egzystencjalnych lub dowodów nie wprost. Tomik zawiera też chronologiczne zestawienie nazwisk, indeks nazw oraz krótką bibliografię. Wiadomości i zadania zebrane są w pięciu działach.

• Zbiory, funkcje, moc, porządki – tu znajdziemy szkolne wiadomości o działaniach na zbiorach i funkcjach, typach funkcji i charakterystycznych dla nich pojęciach, mocach zbiorów, równoliczności i przeliczalności, w szczególności znajdziemy tu dowód twierdzenia Cantora o nieprzeliczalności liczb rzeczywistych. Dalej możemy powtórzyć wiadomości szkolne o symbolu dwumiennym Newtona, poszerzając je o własności symboli wielomiennych. Ostatnia część dotyczy różnych typów relacji (równoważności, porządku pełnego i częściowego), pojęć takich jak przedziały, łańcuchy i antyłańcuchy, twierdzeń Dilwortha, Spernera, Tarskiego oraz pewnika wyboru. Rozwiązane jest tu zadanie o kolorowych czapeczkach więźniów.

• Podstawowe zasady – należą do nich zasada szufladkowa Dirichleta w różnych wariantach i jej zastosowania w arytmetyce, algebrze, geometrii i zadaniach szachowych, zasada włączeń i wyłączeń dla zbiorów skończonych i mierzalnych, zasada łat na kapocie i jej zastosowania w dowodach twierdzeń Birkhoffa i Minkowskiego.

• Grafy – to wielki nieobecny polskiego programu nauczania od zawsze (co dziwi w dobie rozwoju metod dyskretnych i numerycznych). Tu znajdziemy opis i własności grafów prostych, podstawowe typy grafów, terminy i własności, twierdzenia o kolorowaniu, o spłaszczalności grafów o kolorowaniu map oraz elementy teorii Ramseya o kolorowaniu kostek i szukaniu w nich monochromatycznych klik.

• Jeszcze parę pytań i odpowiedzi – opisywane tu zagadnienia dotyczą liczb Catalana, dwumianu Newtona i szeregów potęgowych, ciągów rekurencyjnych i funkcji tworzących, problemów podziałów liczb, rozbić zbiorów i własności liczb Stirlinga, permutacji i ich rozkładaniu na cykle, twierdzenia Halla o kojarzeniu małżeństw oraz ich zastosowań w zadaniach.

• Niezmienniki i gry – pojawiają się tutaj układy pseudodynamiczne, ich niezmienniki i półniezmienniki, gry jednoosobowe, dwuosobowe i strategie wygrywające, opisano gry typu Nim i twierdzenie Richardsona.