Dołącz do czytelników
Brak wyników

Koło matematyczne

22 października 2018

NR 34 (Wrzesień 2018)

Matematyka w biegu – list z wakacji

0 196

Tak oto dobrnęliśmy do początku kolejnego roku szkolnego. Przed nami zatem znów obowiązki szkolne, tak lekcyjne, jak i te pozalekcyjne; w szczególności zajęcia koła matematycznego. Za nami wakacje – czas wolny, odpoczynek, kanikuła… Jak zwykle, ów czas wolny skończył się o wiele za szybko, być może więc w czasie wakacji nie całkiem powinniśmy ulegać wakacyjnemu nastrojowi, nawet jeżeli obiektywne okoliczności „spiskują” przeciw nam, odbierając nam tak czas (Mistrzostwa Świata w piłce nożnej), jak i ochotę (nieznośny upał) na jakikolwiek poważniejszy wysiłek intelektualny. Zapewne jednak pomimo tych niesprzyjających okoliczności niektórzy z nas trafili na jakąś imprezę wakacyjną typu kolonie, na której trzeba było wziąć udział w organizowaniu czasu młodym uczestnikom tejże imprezy. Jednak wakacje (i kolonie) rządzą się swoimi prawami, należy więc się spodziewać, że dzieci będą chciały robić na nich wszystko, tylko nie zajmować się matematyką czy jakimkolwiek innym przedmiotem szkolnym: będą wolały raczej opalać się, kąpać, grać w piłkę, biegać…, czyli robić klasyczne „nic”.

Zatem, jako nauczyciele matematyki, biorąc udział w takich imprezach, moglibyśmy się spodziewać, że my również będziemy mieć raczej wolne od nauczania i niespecjalnie będziemy angażowani w organizację jakichkolwiek zajęć. Przecież w programie zajęć wakacyjnych niewątpliwą przewagę nad innymi ich rodzajami mają zajęcia typu „wychowanie fizyczne”. Gdzie tu miejsce na matematykę? Nie widać… Hura, rzeczywiście powinniśmy mieć wolne. A jednak… we współczesnym świecie na matematykę natykamy się wszędzie, nawet w czasie wolnym, nawet w sporcie. A ze sportem właśnie możemy mieć do czynienia o wiele częściej w czasie wakacyjnych imprez dla dzieci niż w ciągu roku szkolnego. Choć, co oczywiste, nie znaczy to, że na takie problemy nie natkniemy się również w ciągu roku szkolnego.

Jakiś czas temu, bo w roku 2002, redakcja „Matematyki” przekazała mi list jednego z Czytelników (niestety, nie zachowałem go, więc nie mogę go dokładnie cytować), w którym ten pytał, jak sensownie zorganizować szkolne zawody w biegu tak, żeby mieć pewność, że w zawodach tych każdy uczeń bezpośrednio zmierzy się z każdym. W istocie Czytelnikowi temu chodziło o to, żeby ustalić:

Jaka jest najmniejsza liczba biegów po 10 uczestników każdy, jaką należy zorganizować, żeby spośród 40 uczestników zawodów każdy z nich pobiegł w jakimś biegu z każdym innym uczestnikiem?

Oczywiście, problem nie jest wakacyjny, o czym świadczy samo pochodzenie i sformułowanie zadania – chodzi w nim o zawody szkolne, powstał on bowiem w czasie roku szkolnego. Niemniej, o ile w ciągu roku szkolnego problem taki może się pojawić, a zwłaszcza dotrzeć do nauczyciela matematyki, raczej wyjątkowo, to wydaje się, że w czasie wakacji mamy znacznie większe szanse, żeby z nim się zetknąć, jako że „w programie zajęć wakacyjnych niewątpliwą przewagę nad innymi ich rodzajami mają zajęcia typu WF…”. Dlatego wydaje się, że przełom wakacji i nowego roku szkolnego jest właściwym momentem, aby zająć się takim problemem.

Ale ponieważ Mistrzostwa Świata w piłce nożnej i czerwcowy upał mają wpływ również na piszącego te słowa, pozwolę więc sobie zacytować poniżej bez zmian moją niegdysiejszą odpowiedź (stąd forma listu skierowanego do pojedynczej osoby) na wspomniany wyżej list Czytelnika. Zanim jednak przejdziemy do tej odpowiedzi, zauważmy, że problem sformułowany w liście jest szczególnym przypadkiem następującego, bardziej ogólnego problemu:

Jaka jest najmniejsza liczba biegów po k uczestników każdy, jaką należy zorganizować, żeby spośród n uczestników zawodów każdy z nich pobiegł w jakimś biegu z każdym innym uczestnikiem?

A teraz już zapowiadana odpowiedź:

Problem, którego dotyczy nadesłane przez Pana zadanie, jest, niestety, problemem trudnym i – jak to wydaje się wynikać z przeglądu literatury – dotychczas nie został on rozwiązany w postaci ogólnej. W istocie tylko dla niewielu par (n, k) znana jest najmniejsza liczba wymaganych biegów. Zadanie to wydaje się być kolejnym, dość typowym przykładem zadania-pułapki z kombinatoryki skończonej: łatwo się je formułuje, trudno rozwiązuje.

Oczywiście, w literaturze przedmiotu sam problem formułowany jest najczęściej w postaci abstrakcyjnej, choć zdarzają się ujęcia mniej formalne, a bardziej podobne do Pańskiego, tzn. dotyczące zawodów sportowych, turniejów, zakładów totolotka itp. W swej ogólnej postaci problem ten dotyczy następującego pojęcia:

(n, k, l)–pokryciem nazywamy taką rodzinę K podzbiorów k-elementowych n-elementowego zbioru A, że każdy podzbiór l-elementowy zbioru A zawarty jest w co najmniej jednym zbiorze z rodziny K.

Mimo iż pojęcie to samo w sobie jest już dość ogólne, często spotyka się jego dalsze uogólnienia i warianty. W szczególności zamiast „jednego zbioru z rodziny K” żąda się „m zbiorów z rodziny K” [wtedy mówimy o (n, k, l, m)–pokryciu], a warunek „co najmniej” zastępowany bywa warunkiem „dokładnie” (tzw. układy Steinera).

Powinno być jasne, że organizowanie biegów wśród n zawodników w taki sposób, że w każdym biegu weźmie udział k spośród nich, a każdy zawodnik będzie choć raz biegł z każdym innym, jest w istocie definiowaniem (n, k, 2)–pokrycia.

Podstawowym pytaniem jest tu, oczywiście, pytanie o najmniejszą liczbę elementów danego pokrycia czy układu dla danych n ³ k ³ l (m). Historia tego pytania, w jego różnych możliwych sformułowaniach, może zostać prześledzona wstecz, aż do pracy Steinera Combinatorische Aufgabe z 1853 roku, zamieszczonej w 45 tomie Journal für die reine und angewandte Mathematik. Do dzisiaj ukazało się sporo prac (w tym książek) związanych z tą problematyką, a ona sama stała się dość obszerną, samodzielną dziedziną badań znaną pod angielską nazwą (combinatorial) designs, packings and coverings (konfiguracje, upakowania i pokrycia). Jednak żadna z opublikowanych prac nie wydaje się zawierać ogólnej teorii rozwiązywania tego typu problemów, a w szczególności nie ma w nich ogólnego wzoru wyznaczającego najmniejszą moc odpowiedniego pokrycia. Wzoru takiego nie podaje np. Handbook of Combinatorics z 1995 roku, co pozwala, moim zdaniem, twierdzić, że wzór taki po prostu nie istnieje. Nawet w sw...

Pozostałe 70% treści dostępne jest tylko dla Prenumeratorów.

Co zyskasz, kupując prenumeratę?
  • 6 wydań czasopisma "Matematyka"
  • Dostęp do wszystkich archiwalnych artykułów w wersji online
  • Możliwość pobrania materiałów dodatkowych, testów i zadań
  • ...i wiele więcej!
Sprawdź

Przypisy