Wydział Matematyki, Informatyki i Mechaniki UW

Zaczniemy od łamigłówki, w której proste reguły podziału łupów pirackich prowadzą do zaskakujących rozwiązań. Potem pochylimy się nad problemem liczby możliwych podziałów zbioru n-elementowego na rozłączne bloki. Dla małych zbiorów to da się jeszcze ręcznie obliczyć, ale czy istnieje ogólny wzór dla dużych n?

Na zajęciach zajmiemy się sprawiedliwym podziałem dóbr. To problem, przed którym stajemy wszyscy: dzieci kłócące się o ostatni kawałek tortu, zbójcy dzielący łup czy ministrowie konstruujący budżet państwa. Trudno o bardziej konfliktogenne zajęcie. Czy matematyka może w tym jakoś pomóc?

Opowiem o problemach z podziałem spadku po Babie Jadze, o tym jak krasnoludki dzielą budyń i kroją makowiec i jak trzy osoby o bardzo trudnym charakterze mogą się podzielić pizzą lub drożdżówką tak, żeby wszystkie były zadowolone (a w każdym razie nie miały żalu do pozostałych).

Rozważać będziemy kolorowania brył i figur geometrycznych, a kolorować będziemy ich wierzchołki, krawędzie lub ściany. Każde takie kolorowanie można utożsamić z funkcją przypisującą każdemu z wierzchołków lub każdej z krawędzi czy ścian element pewnego zbioru kolorów K. Przy takiej definicji trzeba przyjąć, że dwa kolorowania nie są identyczne, innymi słowy – są różne, jeśli pewna ściana, krawędź czy wierzchołek ulegnie pokolorowaniu na inny kolor w jednym kolorowaniu niż w drugim. Liczbę tak rozumianych kolorowań łatwo można policzyć, korzystając z wiedzy szkolnej, ale tak postawiony problem jest mało praktyczny. My jednak przyglądać będziemy się liczbie nie różnych, a rozróżnialnych kolorowań. Za pokolorowane w sposób nierozróżnialny uznamy figury lub bryły, jeśli można jedną z nich przekształcić, na przykład przez pewien obrót, w taki sposób, żeby po tym przekształceniu zobaczyć identyczne kolorowanie jak drugiej. Liczba rozróżnialnych w tym sensie kolorowań jest trudniejsza do znalezienia. Powiemy o kluczowym dla tego problemu pojęciu grupy przekształceń i działaniu tej grupy na zbiorze obiektów podlegających kolorowaniu. Dowiemy się, czym przy działaniu grupy na zbiorze są orbity i dlaczego tworzą one podział interesującego nas zbioru. Przyjrzymy się, dlaczego wskazanie odpowiedniej grupy przekształceń jest konieczne dla ścisłego sformułowania naszego problemu i dlaczego grupa przekształceń, a co za tym idzie i liczba kolorowań, może być inna, gdy rozważamy dziecięcą kolorowankę na papierze, a inna, gdy projekt witraża. Sformułujemy również kluczowe dwa twierdzenia w tej teorii: Twierdzenie Pólyi i prowadzący do niego Lemat Burnside'a, które powiedzą nam, jak liczba orbit wpływa na liczbę kolorowań. Jeżeli czas pozwoli, naszkicujemy dowody tych twierdzeń.