Afiliacja: Student, Wydział Matematyki i Informatyki, Uniwersytet Warszawski
Na pewien przedmiot zapisanych było 100 studentów. Po zakończeniu sesji miły wykładowca, będąc nierad z wyników uczestników kursu, chciał im dać jeszcze jedną szansę. Po opublikowaniu progu zaliczenia zaproponował im układ: udostępni każdemu studentowi oceny całej grupy z pominięciem oceny zainteresowanego. To znaczy, że każdy z uczniów będzie znał oceny pozostałych, a swojej nie. W następnej kolejności zostaną oni poproszeni o odpowiedź na bardzo proste pytanie:
CZY PAN(i) ZDAŁ(a)?
Jeśli odpowiedź przynajmniej połowy osób na to pytanie będzie prawidłowa, to wykładowca wstawi wszystkim zaliczenie. W przeciwnym wypadku… nikogo nie przepuści. Przed tym całym procederem studenci mają możliwość się naradzić, aby uzgodnić strategię. Pytanie brzmi: czy studenci mogą mieć pewność zaliczenia?
Okazuje się, że odpowiedź jest twierdząca. Na naradzie studenci dzielą się na dwie równoliczne grupy. Pierwsza połowa studentów zakłada, że liczba osób, które zaliczyły, była parzysta, a druga połowa studentów zakłada przeciwnie: że nieparzyście wiele spośród wszystkich osób zdało. Takie założenie o parzystości liczby tych, którzy zaliczyli, daje studentowi jednoznaczną informację o jego własnym zaliczeniu na podstawie wiedzy o zaliczeniach innych. Oczywistym jest, że któraś grupa ma rację, więc dokładnie połowa udzieli poprawnej odpowiedzi. To oznacza, że warunek prowadzącego będzie spełniony!
W ogólności, gdyby \(n\) studentów miało odgadnąć swoją dokładną ocenę, mogącą przyjąć \(k\) możliwych wartości, mogliby analogiczną strategią zagwarantować prawidłowość co najmniej \(\lfloor\frac{n}{k}\rfloor\) odpowiedzi. Polecamy zastanowić się, dlaczego liczby tej nie można zwiększyć (odpowiedź podana na końcu artykułu). W szczególności, gdyby w oryginalnym zadaniu (\(k=2\)) było nieparzyście wielu studentów, to nie mogliby oni zagwarantować spełnienia warunku prowadzącego.
Znajomy tego prowadzącego usłyszał o tej sytuacji w uczelnianej stołówce i wpadł na jeszcze lepszy pomysł – swoim studentom (których miał całkiem sporo, bo aż nieskończenie wielu) zaproponował podobną, choć znacznie trudniejszą grę.
Powiedział, że student o numerze \(k\) w dzienniku będzie miał dostęp do ocen osób o numerach \(k+1,\) \(k+2,\) \(\dots,\) i znowu każdy zgaduje, czy zdał. Tylko że tym razem warunkiem zaliczenia jest to, że pomyli się tylko skończenie wielu studentów. Czyli prawie wszyscy muszą mieć rację, aby spełnić warunek prowadzącego, a jeśli im to nie wyjdzie, to wszyscy oblewają! Czy i tym razem istnieje strategia studentów, która może ich uratować? Czytelnicy, którzy chcieliby sami zmierzyć się z tym pytaniem, powinni zaprzestać lektury w tym miejscu.
Odpowiedź znowu jest pozytywna! Będziemy patrzeć na wyniki studentów jak na ciąg nieskończony, składający się z samych \(0\) (niezaliczone) i \(1\) (zaliczone), czyli pełna informacja o ich zaliczeniu to pewien element zbioru \(\{0,1\}^{\mathbb N}.\)
Symbol \(\{ 0,1 \}^{\mathbb N}\) oznacza zbiór wszystkich funkcji ze zbioru liczb naturalnych \({\mathbb N}\) w zbiór \(\{ 0,1 \},\) czyli właśnie zbiór wszystkich ciągów o wartościach 0 lub 1.
Zacznijmy od uzasadnienia tego, że jeśli dwa takie ciągi różnią się tylko na skończonej liczbie indeksów, to dowolna strategia studentów da przy tych ciągach taki sam efekt. Rzeczywiście, od momentu, w którym ciągi te się pokrywają, studenci będą widzieli „to samo”, będą zatem udzielać w obu przypadkach tych samych – w równym stopniu poprawnych – odpowiedzi. Z punktu widzenia studentów dwa takie ciągi są zatem równie dobre – będziemy pisać równoważne. W ten sposób dzielimy cały zbiór \(\{0,1\}^{\mathbb N}\) na tzw. klasy równoważności, w ramach których wszystkie jego elementy są równoważne (a między którymi nie są).
Podczas narady studenci wybierają dokładnie jednego reprezentanta z każdej klasy równoważności. Dla przykładu, z klasy ciągów, które od pewnego momentu są równe zero, mogli wybrać reprezentanta będącego ciągiem samych zer.
Czytelnik Wykształcony w Teorii Mnogości może dostrzec, że strategia studentów ma pewien słaby punkt – zakłada bowiem prawdziwość aksjomatu wyboru. Jako ciekawostkę dodam, że usłyszałem o tym zadaniu od dwóch prowadzących zajęcia: jeden podał ją po prostu jako trudną zagadkę, drugi zaś jako argument za absurdalnością przyjmowania wspomnianego aksjomatu.
Przy odpowiedzi na pytanie prowadzącego każdy student porównuje widziany przez siebie fragment ciągu ze zbiorem reprezentantów i próbuje znaleźć takiego, który na tym fragmencie „pasuje” – tzn. różni się tylko w skończonej liczbie miejsc. Uda mu się znaleźć takiego reprezentanta, bo ciąg, który widzi (z dokładnością do skończenie wielu elementów, których nie widzi) należy do którejś klasy, czyli różni się od jej reprezentanta na skończenie wielu indeksach. Następnie student udziela takiej odpowiedzi, jaka przypadła mu w znalezionym reprezentancie.
O powodzeniu strategii decyduje to, że wszyscy studenci, niezależnie od swojego numeru w dzienniku, znajdą tego samego reprezentanta! To dlatego, że każdy widzi ten sam „ogon” prawdziwego ciągu – a inni reprezentanci są w innych klasach, czyli różnią się od tego ciągu w nieskończenie wielu miejscach. Widać teraz, że odpowiedzi studentów odtworzą owego reprezentanta, znajdowanego przez każdego z nich. A skoro cały ciąg jest w klasie równoważności wybranego przez wszystkich reprezentanta, to tylko skończenie wielu studentów się pomyli (na tych miejscach, na których te ciągi się różnią). Reszta zgadnie poprawnie. I voilà – warunek wykładowcy zostaje spełniony, studenci zaliczają!
Zacznijmy od wytłumaczenia, dlaczego studenci mogą zagwarantować \(\lfloor\frac{n}{k}\rfloor\) prawidłowych odpowiedzi. Bez straty ogólności przyjmijmy, że oceny są liczbami całkowitymi \(1,2,\ldots,k.\) Studenci dzielą się na \(k\) możliwie równolicznych grup, tzn. każda grupa ma liczyć co najmniej \(\lfloor\frac{n}{k}\rfloor\) osób. Studenci z grupy o numerze \(i\) zakładają, że reszta z dzielenia sumy wszystkich ocen przez \(k\) jest równa \(i\) (\(k\)-ta grupa przyjmuje oczywiście resztę 0). Takie założenie oraz znajomość ocen pozostałych jednoznacznie wskazuje każdemu studentowi odpowiedź na pytanie o jego ocenę. Ponieważ któraś grupa musiała przyjąć słuszne założenie, warunek zostaje spełniony.
Zauważmy teraz, że każdy student podejmuje decyzję na podstawie jednego z \(k^{n-1}\) możliwych ciągów ocen, jaki ów student „widzi”. W tej sytuacji dla każdego studenta istnieje \((k-1)k^{n - 1}\) konfiguracji wszystkich ocen (w tym jego), przy których podejmuje on złą decyzję. Ponieważ wszystkich studentów jest \(n\) oraz mamy \(k^n\) możliwych ciągów wszystkich ocen, więc pewien ciąg ocen jest na liście „złych ciągów” u co najmniej \(\big\lceil \frac{n(k-1)k^{n -1}}{k^n} \big\rceil=\lceil \frac{k-1}{k}n \rceil\) studentów. Oznacza to, że przy takim ciągu ocen prawidłowej odpowiedzi udziela co najwyżej \(n-\lceil \frac{k-1}{k}n \rceil=\lfloor \frac{n}{k} \rfloor\) studentów.