100 więźniów i 1 żarówka

0

W nawiązaniu do zagadki: http://www.rozgrywka.pl/content/view/26/5/
Chciałem napisać symulacje rozwiązania 1 (Studniówka). Według autora tekstu, średni czas wyjścia z więzienia to 260 lat. W mojej symulacji doszli już do ponad 12 mln lat i dalej siedzą. Gdzieś popełniłem błąd?

PS. mój pierwszy kod w Scali, za wszelkie uwagi co do jego konstrukcji będę wdzięczny.

 
object Prisoners {

    def run() {
        
        var day = 0;
        var prisoners = ArrayBuffer.fill(100)(0)
        var lampOff = true
        
        while(true) {
            
            day += 1
            var choosen = Math.abs(Random.nextInt() % 100);
            
            if (day % 100 == 0) {
                if (lampOff && prisoners(choosen) == 0) {
                    println("Koniec. Dzień: " + day)
                    return
                }
                else {
                    var present = 0
                    prisoners.foreach(present += _)
                    var absent = 100 - present

                    prisoners = ArrayBuffer.fill(100)(0)
                    lampOff = true
                    
                    println("Niestety. Dni: " + day + " Byli: " + present + " Nie byli: " + absent)
                }
            }
            else {
                if (lampOff && prisoners(choosen) == 1) {
                    lampOff = false
                }
                else {
                    prisoners(choosen) = 1
                }
            }
            
        }
    }

}
1

Jaki zestaw znaków należy ustawić w przeglądarce, żeby dało się to zadanie odczytać?

1

Nie mam pojęcia :P. Pozmieniałem znaki.

100 więźniów jest umieszczonych w jednoosobowych celach.
Cele są dźwiękoszczelne nie ma w nich okien. W więzieniu jest świetlica z jedną żarówką (początkowo wyłączoną). Z żadnej celi nie widać, czy żarówka świeci się czy nie.
Każdego dnia, strażnik będzie prowadził jednego, losowo wybranego, więźnia do świetlicy i odprowadzał go z powrotem do celi.
W świetlicy więzień będzie mógł, włączyć lub wyłączyć znajdującą się tam żarówkę. Będzie mógl również złożyć oświadczenie, że już każdy ze 100 więźniów był w świetlicy choć jeden raz. Jeśli bedzie to nieprawda wówczas wszyscy więźniowie zostaną rozstrzelani. Jeśli jednak oświadczenie będzie zgodne z rzeczywistością to wszyscy więźniowie zostaną uwolnieni. Zanim cala procedura się rozpocznie, więźniowie zgromadzą się na dziedzińcu więzienia i aby opracować plan postępowania.

Jaki plan działania powinni opracować więźniowie, aby jak najszybciej wyjść na wolność nie narażając się na rozstrzelanie?

  1. Studniówka
    Zaczynając od pierwszego dnia każdy więzień liczy dni. Kiedy w ciągu pierwszych stu dni wchodzi do świetlicy po raz pierwszy nie zapala światła. Jeśli wejdzie w ciągu tych dni po raz drugi, wówczas zapala światło.

Od tej chwili aż do końca pierwszych stu dni światło zostaje zapalone. Będzie to oznaczać, że ktoś w ciągu tych stu dni wszedł co najmniej dwa razy a tym samym, że ktoś inny nie wszedł ani razu. Więzień, który wejdzie setnego dnia gasi światło i zabawa zaczyna się od nowa.
Jeśli pod koniec którejś setki dni światło nadal pozostanie zgaszone, będzie to oznaczać, że nikt w ciągu ostatnich stu dni nie wszedł do świetlicy więcej niż jeden raz co oznacza ze wszyscy na pewno byli w świetlicy. I ostatni więzień w cyklu 100 dni, w którym nie zapalono światła zgłasza strażnikowi ze 100 % pewnością, że wszyscy już byli w świetlicy.

Zaproponowana metoda wymagała niezwykłego zbiegu okoliczności, aby w ciągu konkretnych 100 dni żadnego więźnia nie wylosowano dwukrotnie. Jak wyliczył jeden z forumowiczów, przeprowadzając tysiące komputerowych symulacji, średni czas oczekiwania na wolność wynosi przy zastosowaniu tej metody... 260 lat!

4

Moim zdaniem, średni czas oczekiwania na wolność wynosi \frac{100}{p}, gdzie p oznacza prawdopodobieństwo tego, że wśród 100 kolejno wylosowanych więźniów nikt sie nie powtarza p=\frac{100!}{100^{100}}. Po prostych rachunkach otrzymujemy, że średni czas wynosi
107151028812546692318354675951919152201154064.9292709804836865813095970266876236
47608592593162010122290249132102183378553014415185941097918299473132712250088204
56731160034783787800383645599287328517728185921868974786966006233102681561203372
91395845437416943592256952307400045514012214062926650355501020485904027535636016
77983050917337609922900794505307964866930668803071664365226515744665847885812231
92214152068454085387715673622159827847366500615694259702366079902730084196895616
97832837699062057966807914640101618351661939476552945968933736803393967026838922
64540383087147040493145870029606260732650863279025071087893281492978389535816015
93253111975246253350973944066144258969364380454216110117204909588748280995751610
40594457413031630650506540250203074324976870176379343532377945079053181623317791
74346362037789222622459705824879455505665128415949586519352163029759821476665207
19945464671059462744488256206014120132023010518906092721264723871543190428866369
73756652368633549990792406559201447125053 dni.

0

Dokładnie, jak nie patrzyłem prawdopodobieństwo wynosiło 100!/100^100 . Stąd moje zdziwienie co do tych 260 lat. Dzięki za potwierdzenie.

0

Nie chodzi o odwiedzenia w ciągu jednego cyklu tylko ogólnie
Czyli jeżeli żarówka zapaliła się w 99 dzień to tylko jeden więzień nie odwiedził świetlicy - tym samym prawdopodobieństwo że wszyscy odwiedzą stołówkę w kolejnej turze jest nie mniejsze niż 1%, a po stu turach niemal stuprocentowe

Średni czas na pewno nie wyniesie aż tyle

0

Przepraszam, źle zrozumiałem pytanie i to co jest w zadaniu, a co napisał autor posta

2

Wyobraziłem sobie, że jestem jednym z więźniów i chciałbym opuścić więzienie przed końcem Wszechświata, nawet ryzykując rozstrzelanie. Wyszło mi, że prawdopodobieństwo iż wszyscy więźniowie odwiedzili świetlicę przekroczy 0,999999 po 1833 dniach (w przybliżeniu 5 lat). Niezależnie od tego co ustaliliśmy na zebraniu, gdybym został wylosowany po upływie 5 lat, to bez chodzenia do świetlicy złożyłbym deklarację, że wszyscy byli w świetlicy.

5

Znalazłem dużo wydajniejszy algorytm dla więźniów.
Jeden z więźniów jest rzecznikiem - tylko on może wygłosić oświadczenie.
"Zwykły" więzień przy pierwszej okazji gasi żarówkę, robi to tylko raz. Nigdy też żarówki nie zapala.
Rzecznik zapala żarówkę jeśli jest ciemno, nigdy nie gasi. Liczy też ile razy wystąpiła taka sytuacja: jak ostatnio wychodziłem było jasno, teraz jest ciemno. Po 99 takiej sytuacji wygłasza oświadczenie. Wystąpiło 99 zgaszeń, a ponieważ więzień gasi tylko raz, to musiało w świetlicy być 99 różnych więźniów.

0

Można wprowadzać dalszą hierarchię, w której jest główny szef, kilku pomocników i reszta, są też rozkminy z binarnym kodowaniem numeru więźnia i tego, jak przekazuje informację dalej. Szczegółów nie podam, bo rozgryzałem tę zagadkę parę lat temu na kole matematycznym, ale w internecie jest to spokojnie do wyszukania.

0
bogdans napisał(a):

...

widać że ta zagadka nie dawała Ci spokoju i chodziła po głowie przez 1,5 roku :D lepiej późno niż wcale, ale nie wiem czy na dziedzińcu mieliby tyle czasu na rozkminy ;)

0

@Afish Jest zaznaczone, że z żadnej celi nie widać światła ze stołówki.
Jedynie wiadomość mogą przesłać bitem, a tak mogli by przesyłać sobie informacje bajtami.

0
Losowy grajek napisał(a):

@Afish Jest zaznaczone, że z żadnej celi nie widać światła ze stołówki.
Jedynie wiadomość mogą przesłać bitem, a tak mogli by przesyłać sobie informacje bajtami.

Ja tę zagadkę rozumiem, jak już wspominałem, rozwiązywałem ją parę lat temu i doszedłem o wiele dalej, niż w tym temacie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1