Pokój z lampą. Ćwiczenie na przekazywanie informacji. Cz. 0

W naqnaq, w grupie "Zagadki", niejaki Witzar podał szereg świetnych zadań kombinatoryczno-informatycznych, które nazwał logicznymi. Jego scenariusz więzienny zastąpię szkolnym, żeby zadanie brzmiało mniej ponuro.

---

ZADANIE   [;n;] zdolnych uczniów zebrano razem, żeby ustalili optymalną strategię prowadzenia wspólnej gry. Każdy uczeń za ten honor i możliwość wpłacił 300zł na pewne konto. Do wygrania mają wspólną podróż dookoła świata i stypendium dla każdego z nich do końca studiów. Po zebraniu, już do końca gry, nie wolno się im komunikować. Otóż po zebraniu, każdego dnia losowo wybrany uczeń uda się do pewnego pokoiku, w którym lampa będzie zapalona lub zgaszona. Po sobie zostawi lampę zgaszoną lub zapaloną według swojego życzenia (według wspólnie ustalonej strategii). Może też oświadczyć, że wraz z nim każdy student już w tym pokoiku był co najmniej jeden raz. Jeżeli pomyli się, to wpłaty uczniów przepadną, oraz będą nici z podróży i stypendium. Jeżeli oświadczenie będzie poprawne, to wszyscy uczniowie wygrają, zgodnie z obietnicą.

Podpowiedz uczniom jak najlepszą strategię.

---

Dla n=1, przy jednym uczniu, uczeń wchodzi do pokoiku i woła wygrałem! - i rzeczywiście wygrał. Koniec.

---

Przy n=2 uczniowie mogą się umówić, że

1. będą zapalać lampkę albo nie, byle jak;


2. początkowego dnia uczeń w pokoiku będzie cicho (nie zawoła, że wygrał);


3. każdego następnego dnia, jeżeli uczeń w pokoiku nie był w nim poprzedniego dnia, to zawoła "wygraliśmy!".

Jest to absolutnie najlepsza strategia. Szybciej wygrać jest niemożliwym.

---

Przy n=3 następująca umowa jest optymalna (lepszej nie ma):

1. uczeń, który do danego dnia włącznie, od początkowego, był w pokoiku za każdym razem, pozostawia za sobą światło zgaszone;


2. gdy dzień nie jest początkowy, a w czasie przynajmniej jednego z poprzednich dni był w pokoiku inny uczeń od danego, to:
   
   1. zastawszy światło zgaszone, uczeń pozostawia po sobie światło zapalone;
   
   
   2. jeżeli uczeń był w pokoiku także poprzedniego dnia, i pozostawił światło zapalone, to znowu zostawia po sobie światło zapalone;
   
   
   3. jeżeli poprzedniego dnia był inny uczeń od danego, i pozostawił światło zapalone, to obecny uczeń woła "wygraliśmy!".
   
   

Znowu opisana strategia jest optymalna. Za każdym razem wygrywa jak tylko najszybciej można. Już dla n=4 tak dobrej strategii nie ma, co wykażę w następnej nocie. Teraz podam jeszcze definicje kilku pojęć, by dało się rozmawiać o zadaniu ściśle. W szczegółności ściśle zdefiniuję strategię.

---

Uczniów numerujemy:  [;0\ \ldots\ n-1;].   Podobnie numerujemy od zera, ale w nieskończoność, dni w pokoiku:  [;0\ 1\ 2\ \ldots;].

---

Przebiegiem (losowania) nazywamy dowolny ciąg

[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]

UWAGA Chociaż gra, aż po okrzyk "zwycięstwo!" może trwać skończoną liczbę dni, to teoretycznie wygodnie jest zakładać, że losowanie uczniów powtarza się każdego dnia w nieskończoność (po zakończeniu gry nikogo to już nie obchodzi, nikomu to nie przeszkadza).

Poniższe funkcje za swój argument mają także przebieg, co będziemy często pomijać, żeby za bardzo nie piętrzyć notacji.

---

Zapisem ucznia [;u;] w dniu gry [;d;] nazywamy strukturę

[;\bullet\quad\quad \ker_{u\ d} := (v_{u\ d}\ \ \delta_{u\ d}\ \ b_{u\ d});]
następujących danych:

• [;v_{u\ d};]  jest liczbą wizyt ucznia [;u;] w pokoiku, w czasie dni  [;0\ \ldots\ d;];


• [;\delta_{u\ d} : \{0\ \ldots\ v_{u\ d}-1\} \rightarrow \{0\ 1\ \ldots\};]  jest funkcją, która informuje nas o dniach wizyt  [;\delta_{u\ d}(0)\ \ldots\ \delta_{u\ d}(v-1);],  ucznia [;u;];


• [;b_{u\ d} : \{0\ \ldots\ v_{u\ d}-1\} \rightarrow \{0\ 1\};]  jest funkcją, która informuje nas o zastanym stanie lampy,  [;b_{u\ d}(t);] na początku wizyty w dniu  [;\delta_{u\ d}(t);]; gdy uczeń zastał ciemność, to zapisze wartość funkcji [;b;] jako [;0;]. a jeżeli lampa świeciła się, to zapisze [;1;]; dla ustalenia uwagi (to zupełnie nieważne) zakładamy, że na samym początku dnia [;0;] lampa była zgaszona .

---

Strategią nazywamy dowolną funkcję [;S;] która każdemu a priori możliwemu zapisowi [;\ker;] przypisuje wartość  [;S(\ker);],  będącą równą 0 (lampę przed opuszczeniem pokoju gasimy lub pozostawiamy zgaszoną) albo 1 (lampę przed opuszczeniem pokoju zapalamy lub zostawiamy zapaloną) albo 2 (wołamy wtedy: zwycięstwo!).

W praktyce, pełna definicja uczniowskiej strategi powinna dać się opisać w notesiku, który uczeń będzie miał przy sobie - strategia powinna dać się opisać jako skonczony algorytm. Teoretycznie prościej jest mówić o strategiach będących dowolnymi funkcjami, jak wyżej.

Uczeń po wejściu do pokoiku uaktualnia swój zapis [;\ker;], po czym stosuje do niego funkcję strategiczną,  [;S(\ker);].

---

Dla liczby uczniów n=1 lub 2 lub 3 podane wyżej strategie dają najszybszą wygraną - nawet granie na szczęście, bez żadnej strategii, też nigdy nie da szybszej wygranej. Takie strategie nazwijmy natychmiastowymi. Zdefiniuję je teraz ściśle, a nawet całe spektrum różnych klas strategii.

Najpierw z każdym przebiegiem

[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]

zwiążmy jego stopień zaawansowania  [;\deg_w;]  :

[;\bullet\quad\quad \deg_w(d)\ :=\ \min_{u=0\ \ldots\ n-1}\ v_{u\ d};]

Ponadto zdefiniujmy końce cykli,  [;C_w(q);],  jako numer pierwszego dnia, w którym każdy uczeń wszedł do pokoiku minimum [;q;] razy:

[;\bullet\quad\quad C_w(q) := min_{\deg_w(d) = q}\ d;]

a gdy takiego dnia nie ma (gdy pewien uczeń nigdy nie był wylosowany aż [;q;] razy), to przyjmujemy  [;C(q) := \infty;].

---

Gdy dla pewnego [;q;] strategia [;S;] zapewnia zwycięstwo nie później niż w dniu [;C_w(q);], to powiemy, że jest opieszała rzędu [;q;].

Strategie opieszałę rzędu 1 są absolutnie najlepsze, są natychmiastowe. Istnieją jednak tylko dla liczby uczniów n=1 2 3. Już dla n=4, i dla wszystkich większych n, strategia natychmiastowa nie istnieje.

Prawdopodobnie uzyskanie strategii, której opieszałość jest rzędu  [;\sqrt{n};]  (gdzie n jest liczbą uczniów), jest całkiem dobrym wynikiem.