Tu jesteś:  START arrow ŁAMIGŁÓWKI arrow Artykuły, teoria, ciekawostki arrow 100 więźniĂłw i ĹźarĂłwka
 

   ŁAMIGŁÓWKI, GRY, KRZYŻÓWKI

 

100 więźniów i żarówka Drukuj Email
Spis treści
100 więźniów i żarówka
Strona 2

3) LIDER i 100 DNI

Jest to nadal metoda lidera. Najważniejszą zmianą jest taka, że liderem, czyli zliczającym więźniów, którzy już odwiedzili świetlicę, zostaje osoba, która jako pierwsza wejdzie po raz drugi do świetlicy i to ona po raz pierwszy zapala światło.

Powiedzmy, że przez pierwsze 35 weszło do świetlicy 35 różnych więźniów. 36 dnia jeden z nich został wylosowany po raz drugi. Wchodząc do świetlicy i widząc ze światło jest nadal zgaszone, od razu wie, ze w świetlicy było już 35 więźniów.

Nie musi więc jak w poprzedni odmianach metody lidera zliczać wizyt w świetlicy 99 lub 98 więźniów ale tylko 64!

Po zapaleniu światła przez lidera po raz pierwszy, dalej, aż do 100 dnia od początku wizyt nic się nie zmienia. Nikt nie gasi światła. Wszyscy którzy odwiedzą świetlicę i zobaczą zapaloną żarówkę, będą wiedzieli że lider jest już wybrany.

100-go dnia lider zaczyna zliczanie tak jak w poprzednich wersjach tej metody.

Setnego dnia będą istniały 4 grupy więźniów:
A - weszli pierwszy raz do świetlicy kiedy światło było zgaszone
B - weszli pierwszy raz do świetlicy kiedy światło było zapalone
C - nie byli w świetlicy
D - lider.

Jeśli osoba, która wchodzi do świetlicy 100-go jest z grupy A lub D to gasi światło. Jeśli jest z grupy B lub C wówczas zostawia je zapalone. Służy to temu aby lider zaczął ja najszybciej zliczać wizyty więźniów w świetlicy. Jeśli bowiem setnego dnia do świetlicy wejdzie więzień z grupy B lub C to ta jego wizyta zostanie policzona przez lidera jako pierwsza.

Tak wiec począwszy od 101 dnia lider zaczyna zliczać następne wizyty więźniów a osoby z poszczególnych grup zachowują się zgodnie z takimi zasadami:
A - nic nie robią, ich wizyty w świetlicy są już przez lidera policzone.
B i C - włączają światło, kiedy wejdę następny raz a światło będzie zgaszone.
D, czyli lider – gasi światło za każdym razem kiedy zastanie je zapalone , zwiększając równocześnie o 1 liczbę osób , o których wie na pewno że już choć raz były w świetlicy.


Forumowicze – programiści natychmiast wzięli się do pracy i obliczyli, że wprowadzone zmiany zmniejszają przeciętny czas oczekiwania na wolność z 28 lat do ok. 25 lat.

Następne 10 dni forumowej dyskusji to znowu drobne ulepszenia metody a także różne bardziej i mniej wesołe sposoby rozwiązania problemu – od odmowy wyjścia kolejnych więźniów ze świetlicy po dokładne wyliczanie szans na przeżycie w przypadku zgłoszenia wizyty wszystkich więźniów w świetlicy metodą „chybił trafił”, jeśli przez pierwszych 10 lat opracowane metody nie odniosą skutku. Tak jest aż do 8 sierpnia – wtedy pojawia się kolejny przebój:

4) LIDER i 10 ASYSTENTÓW

Jedne z więźniów zostaje w czasie zebrania wybrany na lidera, dziewięciu zostaje jego asystentami. Pozostali – są „trutniami”.

Asystenci mają zliczać wizyty więźniów w świetlicy, lider ma pobierać wyniki zliczeń od asystentów, a trutnie po prostu maja być zliczani.

Są dwa etapy zliczania wizyt więźniów w świetlicy:
- w pierwszym wizyty więźniów zliczają asystenci
- w drugim wyniki uzyskane przez asystentĂłw zlicza lider.

Etap 1 trwa 2 600 dni.
W czasie jego trwania obowiązują następujące zasady:

- jeśli w tym etapie truteń wchodzi do świetlicy po raz pierwszy a światło jest wyłączone wtedy włącza je do i  końca tego etapu nie dotyka juĹź wyłącznika;
- jeśli asystent lub lider wejdzie do świetlicy, światło jest zapalone a on sam nie zliczył jeszcze 9 wizyt więźni wówczas dodaje 1 do swojej liczby i gasi światło. Jeśli zaś doliczył już do 9 nie robi nic.
- ostatniego dnia tego etapu po wizycie każdego, za wyjątkiem asystentów którzy doliczyli do 9, światło w świetlicy musi pozostać wyłączone, natomiast po wizycie asystenta który doliczył do 9 światło musi zostać zapalone

Etap 2 trwa 2 700 dni.
W tym etapie lider zlicza wszystkich asystentów, którzy w 1-szym etapie doliczyli do 9. Nazwijmy ich Dziewiątkami.

Tylko Dziewiątki maja prawo zapałać światło w tym etapie. Pozostali więźniowie nie mają prawa dotykać wyłącznika w tym etapie.
Jeśli Dziewiątka wejdzie do świetlicyw tym etapie po raz pierwszy a światło będzie zgaszone zapala je – i do końca etapu nic nie robi.
Jeśli Lider wejdzie do świetlicy w tym etapie wtedy gdy światło będzie zapalone, gasi je a do liczby zliczonych Dziewiątek dodaje 1.
Jeśli przed upływem ostatniego dnia Lider zliczy wszystkie Dziewiątki wówczas zgłasza do strażników fakt iż wszyscy byli już w świetlicy .
Jeśli to mu się nie uda – wówczas po 5 300 dniach liczenie zaczyna się od początku.

 
Metoda z asystentami okazała się rewelacją – skróciła średni czas oczekiwania na wolność do mniej niż 3900 dni czyli mniej niż 11 lat! Liczba systentów i czas trwania etapów zostały dobrane przy pomocy komputerowych symulacji. Ani asystentów ani lidera tej metodzie nie trzeba zliczać – zliczani są tylko trutnie.

Uczestnicy dyskusji zaczęli wprowadzać dalsze ulepszenia. Główna idea – przekazywania sobie zliczonych wizyt została zachowana – już nie zmieniono. Na forum zaczęły pojawiać się fragmenty programów komputerowych, a poziom dyskusji coraz bardziej wędrował ku informatyczno- matematycznym rozwiązaniom.
Z on-linowa symulacją komputerową jednej z tych metod można zapozna się na wspomnianej już internetowej stronie Ulfa Göranssona.
Można sobie trochę poeksperymentować i zapoznać się z kodem źródłowym programu.

 
Kiedy jeszcze na forum Wu trwała gorąca dyskusja nad ulepszaniem metody lidera i asystentów,
ZAGADKA PRZYWĘDROWAŁA DO POLSKI
.
Na łamigłówkowe forum Gazety Wyborczej wprowadził ją Cardemon – legenda tego forum, człowiek dostarczający polskim miłośnikom łamania głowy nieustannych atrakcji – czy jak kto woli problemów do rozwiązania.

Polscy forumowicze pracowali szybciej sprawniej i metodę przekazywania sobie zliczonych wizyt wypracowali w ciągu zaledwie tygodnia kończąc rozważania na poziomo ok. 3 800 dni oczekiwania na wolność. Ostatnia wypowiedź na polskim forum pochodzi z 22 września 2002 roku.

5 grudnia Wiliam Wu opublikował w internecie teoretyczne rozważania na temat problemu 100 więźniów i jednej żarówki. Na jego forum co i raz pojawiają się nowe wypowiedzi. Problem ciągle czeka na nowe, jeszcze lepsze, rozwiązania. Może ktoś się skusi?