Dodaj do ulubionych

100 wiezniow i zarowka

16.08.02, 23:17
Zapowiadalem juz wczoraj te zagadke. Jest to kolejny ciezki orzech do
zgryzienia, ale skoro na tym forum jest tak wiele tegich umyslow, to mysle,
ze sobie wspolnie jakos z jej rozwiazaniem poradzimy. A oto ona:

100 Wiezniow siedzi w pojedynczych celach w wiezieniu. W tym samym wiezieniu
jest pewien osobny pokoj, nazwijmy go "swietlica", w ktorym znajduje sie
jedna zarowka, poczatkowo wylaczona. Zaden z wiezniow nie moze zobaczyc
swiatla zarowki ze swej celi. Kazdego dnia straznik wiezienny wybiera losowo
jednego wieznia i zaprowadza go do swietlicy, gdzie wiezien moze w zaleznosci
od swej woli wlaczyc lub wylaczyc zarowke. Kazdy wiezien ma mozliwosc zlozyc
w dowolnym dniu oswiadczenie, ze juz kazdy z setki wiezniow odwiedzil
swietlice. Jesli jego oswiadczenie bedzie falszywe (czyli niektorzy
wiezniowie jeszcze nie byli w swietlicy), to wszyscy zostana rozstrzelani.
Ale jesli jego twierdzenie bedzie sluszne i rzeczywiscie kazdy z setki
osadzonych przynajmniej raz goscil juz w swietlicy, to wszyscy zostana
wypuszczeni na wolnosc. Ten ktory oswiadczy wiec, ze wszyscy juz byli w
swietlicy, musi byc tego pewien na 100%.
Wiezniom pozwolono jednego dnia naradzic sie wspolnie, po czym wsadzono ich
do pojedynczych cel, gdzie nie maja juz szans komunikowac sie ze soba i od
jutra zacznie sie wyprowadzanie do swietlicy.

Jaki plan dzialania opracowali wiezniowie? Jaka jest optymalna strategia
pozwalajaca im na wydostanie sie z wiezienia?

Kilka objasnien:

1) Zarowka sie nigdy nie przepali, ani nikt procz wiezniow nie ma prawa
dotykac przelacznika.
2) Zaden z wiezniow nie umrze.
3) W swietlicy nie mozna bazgrac, ani ryc po scianach itp. (poza tym raz na
jakis czas przychodzi ekipa malarzy i wszystko odmalowuje).
4) Nie ma mowy, by zostawic gdzies w swietlicy wlasnego wlosa itp.
(sprzataczka jest bardzo solidna).

To chyba wszystko. Jesli ktos juz ma jakis pierwszy pomysl, jak ruszyc
zagadke z miejsca, to jest bardzo proszony o przedstawienie go.

Zycze powodzenia!

Car de Mon
Obserwuj wątek
    • reptar Re: 100 wiezniow i zarowka 16.08.02, 23:21
      pierwszy pomysł na ruszenie: mogą sobie dawać znaki tylko za pomocą żarówki

      przychodzisz, widzisz że włączona - coś to oznacza
      widzisz, że wyłączona - oznacza coś innego

      Będę myślał.
    • mesquaki Re: 100 wiezniow i zarowka 16.08.02, 23:32
      Więźniów można brać wielokrotnie, tak?
      Na przykład 1,5,5,3,5,67 ?
      • reptar Re: 100 wiezniow i zarowka 16.08.02, 23:34
        to nie moja zagadka, ale rozumiem, że tak. W przeciwnym razie wystarczyłoby
        poczekać 100 dni...
        • mesquaki Re: 100 wiezniow i zarowka 16.08.02, 23:36
          No chyba, że niekoniecznie brano jednego dziennie - jedno z dwoch.
    • cardemon Re: 100 wiezniow i zarowka 16.08.02, 23:37
      Przypominam, ze wiezniowie brani sa ze swych cel losowo.
    • cardemon Re: 100 wiezniow i zarowka 16.08.02, 23:40
      Przypominam, ze kazdego jednego dnia, czyli codziennie, straznik kogos prowadzi
      do swietlicy.
      • mesquaki Re: 100 wiezniow i zarowka 16.08.02, 23:43
        A ile więźniowie mają lat?
        Statystycznie rzecz biorąc, po jakichś paru latach możn by było zaryzykować ;)
    • ydorius Re: 100 wiezniow i zarowka 17.08.02, 01:27

      A może komuś wpadnie do głowy pomysł w oparciu o:
      - jeżeli jesteś pierwszy raz w świetlicy, zmień stan żarówki. Wtedy wiemy, że
      jeżeli żarówka jest zapalona, to w świetlicy była nieparzysta liczba więźniów,
      zaś zgaszona oznacza parzystą.
      Jeżeli jakiś więzień jest n-ty raz w świetlicy, to nie zmienia stanu żarówki,
      by nie psuć modelu :-)))

      Nie wiem, czy to, co napisłaem ma jakieś znaczenie. Idę spać, może mi się coś
      przyśni :-)

      .y.

      ----------------------------------
      What is home without Plumtree's Potted Meat?
      Incomplete.
    • mesquaki Re: 100 wiezniow i zarowka 17.08.02, 01:51
      Pomysł niezbyt mądry i absolutnie sprawy nie rozwiązuje, ale może kogoś do
      czegoś konstruktywnego natchnie :)
      Każdy więzień, jeśli jest w świetlicy(hehe) pierwszy raz, zostawia po sobie
      zapalone światło. Jeśli po raz kolejny, nic nie zmienia. Dni dzielimy po 100
      dla ułatwienia, może być jakaś inna liczba. W każdym razie, przez te 100 dni
      zbiera się nowicjuszy. Więzień z dnia będącego wielokrotnością setki widzi, czy
      przez te ostatnie 100 dni był w świetlicy ktoś nowy, czy nie. Jeśli tak, zeruje
      licznik-gasi światło i zabawa toczy się dalej. Jeśli nie, (ciemno) , idzie
      zameldować, że już wszyscy byli....i odmawia zdrowaśki ;)
      • musztarda_po_obiedzie Re: 100 wiezniow i zarowka 17.08.02, 09:04
        mesquaki napisała:

        > Pomysł niezbyt mądry i absolutnie sprawy nie rozwiązuje, ale może kogoś do
        > czegoś konstruktywnego natchnie :)

        Ciężko w ogóle coś supermądrego wymyślić, jeśli jedyny sygnał, jaki mamy do
        dyspozycji, to "włącz/wyłącz" światło. Na dodatek każdy więzień, który będzie
        chciał zostawić w ten sposób jakąć informację o sobie, musi skasować sygnał
        swojego poprzednika :(

        > Każdy więzień, jeśli jest w świetlicy(hehe) pierwszy raz, zostawia po sobie
        > zapalone światło. Jeśli po raz kolejny, nic nie zmienia. Dni dzielimy po 100
        > dla ułatwienia, może być jakaś inna liczba. W każdym razie, przez te 100 dni
        > zbiera się nowicjuszy. Więzień z dnia będącego wielokrotnością setki widzi,
        czy
        >
        > przez te ostatnie 100 dni był w świetlicy ktoś nowy, czy nie. Jeśli tak,
        zeruje
        >
        > licznik-gasi światło i zabawa toczy się dalej. Jeśli nie, (ciemno) , idzie
        > zameldować, że już wszyscy byli....i odmawia zdrowaśki ;)

        Rzeczywiście, nie rozwiązuje sytuacji w 100%. Na przykład nie rozwiązuje
        układu, gdy podczas którejś setki dni wziętych do świetlicy zostało 90 różnych
        więźniów (niektórzy dwukrotnie), którzy już wcześniej tam byli - żaden nie
        zapali światła. Jeśli ktoś z pozostałej dziesiątki nie był tam również
        wcześniej, to... klops.

        Jedyne rozwiązanie z gwarancją meldowania, jakie wymyśliłem, to:

        (A)
        każdy więzień (oprócz jednego) zapala światło WYŁĄCZNIE wtedy, gdy pierwszy raz
        zastał w świetlicy ciemność.

        Jak łatwo zrozumieć, każdy może zapalić światło tylko raz (choć niekoniecznie
        przy pierwszej wizycie w świetlicy)

        (B)
        Tym jednym 'wykluczonym' z zabawy jest więzień z dnia 2. Jego rola
        to 'przetwarzanie danych'. Za każdym razem, gdy znajdzie się w świetlicy,
        sprawdza stan żarówki. Jeśli jest zapalona, oznacza to, że od ostatniego pobytu
        więźnia 2 kolejny więzień zastosował procedurę (A). Jeśli zaś jest zgaszona,
        oznacza to, że wszyscy którzy byli tu w międzyczasie, mieli okazję do zapalenia
        światła już wdcześniej. Tak czy owak, więzień 2 po swojej wizycie zostawia
        światło zgaszone.

        (C)
        Gdy więzień zastanie w świetlicy zapalone światło po raz 99-ty, może iść
        meldować do strażnika (on sam jest setną osobą).

        No cóż, daje to gwarancję, że więźniowie się nie podłożą strażnikowi.
        Jedyny szkopuł to... prawdopodobieństwo :(

        Więzień 'meldujący' będzie się zjawiać w świetlicy mniej więcej co 100 dni. Z
        każdą swoją wizytą może odhaczyć najwyżej jednego nowego gościa w świetlicy - a
        musi ich odhaczyć.. 99. Co to oznacza? Że -teoretycznie- wszyscy zostaną
        odhaczeni po jakichś... 9900 dniach! Cholera, to jest 27 lat :(

        Może da się szybciej??
        pozdrawiam,
        m<p>o


    • reptar Metoda dla mniejszej liczby więźniów 17.08.02, 10:19
      Wymyśliliśmy (my wife and me) strategię dla mniejszej liczby więźniów.
      W zasadzie dla 100 też można stosować, ale bez większej nadziei.
      Przedstawię ją tutaj, bo może kogoś natchnie, może ktoś ją rozwinie
      (z ostatniej chwili: widzę, że od wczoraj przybyło postów; zaraz się biorę
      za czytanie).


      Przedstawię ją dla pięciu więźniów (dla 3, 4, 6, 7 itd. strategia jest taka
      sama, różni się tylko prawdopodobieństwem):

      Pierwszego dnia wchodzi więzień i zostawia zaświecone światło.
      Przez drugi, trzeci, i czwarty dzień codziennie ktoś wchodzi.
      Jeśli wchodzi po raz drugi, gasi światło.
      Piątego dnia wchodzi więzień do pokoju z żarówką i ma takie możliwości:
      a) żarówka jest zgaszona
      b) żarówka się świeci, a ten z piątego dnia jest tu po raz pierwszy
      c) żarówka się świeci, a ten z piątego dnia jest tu po raz drugi


      Przypadek b oznacza, że każdego dnia w żarówce był ktoś inny, a więc piątego
      dnia więzień zgłasza, że to już i eksperyment się kończy.

      Przypadki a i c oznaczają, że ktoś był dwa razy, czyli nie wszyscy byli. W tych
      przypadkach więzień z piątego dnia nie kończy eksperymentu, lecz zaczyna nowy
      cykl. Dzień piąty (ostatni pierwszego cyklu) staje się równocześnie dniem
      pierwszym cyklu drugiego. Kolejne cykle obejmują okresy:
      1, 2, 3, 4 i 5 dzień
      5, 6, 7, 8 i 9 dzień
      9, 10, 11, 12 i 13 dzień
      13, 14, 15, 16 i 17 dzień

      Uwaga - ta metoda nie wyłapie pięciu kolejnych dni nie stanowiących cyklu, np.
      od 8 do 11. Decyzję można podejmować tylko w dni 5, 9, 13, 17... czyli (n-1)
      *c+1, gdzie n jest liczbą więźniów, a c kolejnym numerem cyklu.

      Ta metoda daje dość duże nadzieje tylko dla małych n. Przy n=100 kolejne
      decyzje można będzie podejmować w dniach: 100, 199, 298, 397 itd., przy czym
      prawdopodobieństwo sukcesu jest tak nikłe, że w praktyce można mówić o pewnym
      rodzaju nieśmiertelności.



      Mieliśmy też parę innych pomysłów, ale zawsze coś gdzieś nie pasowało.

      I jeszcze jedno: trzeba wziąć pod uwagę, że losowo MOŻE oznaczać, że NIGDY
      nie nastąpi taka sytuacja, która pozwoli na podjęcie decyzji "wszyscy już byli".
      • reptar Re: Metoda dla mniejszej liczby więźniów 17.08.02, 10:25
        reptar napisał:

        > Przypadki a i c oznaczają, że ktoś był dwa razy, czyli nie wszyscy byli. W
        > tych przypadkach więzień z piątego dnia nie kończy eksperymentu, lecz zaczyna
        > nowy cykl.

        ...oczywiście niezależnie od tego, czy zastał żarówkę zaświeconą (przypadek c),
        czy zgaszoną (przypadek a) - tego dnia pozostawia po sobie zaświeconą żarówkę,
        żeby kolejny cykl mógł przebiegać tak samo jak pierwszy.
    • reptar Brawo, musztarda_po_obiedzie! 17.08.02, 11:59
      Brawo, musztarda_po_obiedzie!
      Pomysł z jednym zliczającym jest genialny, prosty i co najważniejsze skuteczny.

      Mogłeś tylko ująć to prościej ;)
      Spróbuję Twoje rozwiązanie wyrazić w postaci skondensowanej:

      - jeden więzień zlicza akty zaświecenia (i zawsze pozostawia po sobie zgaszone
      światło)
      - każdy z 99 pozostałych więźniów ma tylko jedno zadanie: jeden jedyny raz
      zaświecić światło.



      I to już wszystko. Niepotrzebnie skomplikowałeś sprawę taką wstawką:

      -
      • musztarda_po_obiedzie Re: Brawo, musztarda_po_obiedzie! 17.08.02, 12:19
        reptar napisał:

        > I to już wszystko. Niepotrzebnie skomplikowałeś sprawę taką wstawką:
        > -
        • reptar Czy na pewno skrócenie??? 17.08.02, 13:57
          musztarda_po_obiedzie napisał:

          > OK, już tłumaczę, skąd wziął się pomysł *więźnia-dnia-drugiego*:
          > To miało skrócić czas oczekiwania


          Tak, ale skrócenie o kilka dni wobec 27 lat... i czy na pewno skrócenie?

          Oto przykładowa (tendencyjna) sytuacja: w ciągu pierwszych czterystu dni dwaj
          więźniowie A i B wchodzą tak:
          A - 2, 38, 390 dnia
          B - 111, 115, 119, 137, 182, 222, 283 dnia

          Czy nie lepiej postawić na tego drugiego? Ale może dalej więzień A nadrobi
          stratę między dniami 500 a 700 i znowu wyprzedzi więźnia B o kilka odhaczeń?

          To oczywiście przypadek szczególny spośród kroci możliwości, i niczego nie
          udowadnia - zresztą sprawę pozostawiłem otwartą, nie stwierdzając, który byłby
          lepszym koniem. Ale przy dużych liczbach należy się raczej spodziewać
          stosunkowo równomiernego rozkładu, więc zarówno więzień A, jak i więzień B
          (ogólnie: każdy więzień) będąc zliczającym, zużyłby na 99 odhaczeń mniej więcej
          tyle samo czasu, powiedzmy z dokładnością do kilkuset dni.

          W ogóle trzeba by znać całkowitą rozpiskę (kto którego dnia wchodzi), żeby
          określić, który więzień byłby najoptymalniejszy (dałoby się ich uszeregować w
          takim "pofaktycznym" rankingu na miejscach od 1 do 100). Intuicyjnie wyczuwam,
          że miejsce w takim rankingu nie będzie wcale zależeć od czasu pierwszego
          odhaczenia.

          Swoją drogą ciekaw jestem, czy da się moją intuicję potwierdzić (lub obalić)
          metodami rachunku prawdopodobieństwa, czy da się wyliczyć, czy taki zryw na
          starcie skróci wartość oczekiwaną. Nie podejmuję się obliczenia, bo to dla mnie
          za trudne. Ja jednak obstawiałbym tezę, że czas pierwszego i czas
          dziewięćdziesiątego dziewiątego odhaczenia to dwie zupełnie niezależne sprawy.
          • musztarda_po_obiedzie Re: Czy na pewno skrócenie??? 17.08.02, 19:14
            reptar napisał:

            > Tak, ale skrócenie o kilka dni wobec 27 lat... i czy na pewno skrócenie?
            >
            > Oto przykładowa (tendencyjna) sytuacja: w ciągu pierwszych czterystu dni dwaj
            > więźniowie A i B wchodzą tak:
            > A - 2, 38, 390 dnia
            > B - 111, 115, 119, 137, 182, 222, 283 dnia
            >
            > Czy nie lepiej postawić na tego drugiego?

            No cóż, zajmowanie się jakąkolwiek konkretną sytuacją na pewno nie doprowadzi
            nas do niczego. Jak sam zauważyłeś, przykłądy można dobierać tendencyjnie, w
            zależności od tego, co chce się udowodnić. Postanowiłem pójść trochę inną
            drogą, żeby dowieść skuteczności (choćby tylko teoretycznej) metody "więźnia
            dnia trzeciego".

            Napisałem króciutki program, który symuluje losowanie kolejności więźniów,
            którzy wchodzą do świetlicy. Dla danej kolejności sprawdzałem, po ilu dniach
            będziemy mieli pewność odhaczenia wszystkich w dwóch przypadkach:
            a) gdy odhacza więzień dnia drugiego
            b) gdy odhacza więzień dnia trzeciego

            Przeanalizowałem 10000 różnych układów. Oto wyniki:
            W 4292 przypadkach pewność osiągał szybciej więzień 2, natomiast w 5708
            przypadkach - więzień dnia 3.

            więzień dnia 2 odhaczał wszystkich średnio po 10222 dniach,
            więzień dnia 3 odhaczał wszystkich średnio po 9972 dniach.

            Czy 10000 przeanalizowanych przypadków jest liczbą reprezentatywną?? nie wiem,
            na tyle miałem czas. Puszczę program dalej, zobaczymy czy ta tendencja się
            utrzyma.

            A póki co, teoria 'więźnia dnia trzeciego' chyba się sprawdza, co? Spójrz też
            na średnią odhaczenia wszystkich - różnica 250 dni jest już dość znacząca, nie
            uważasz? To już nie jest kilka dni :)

            Mam pomysł na ulepszenie 'zrywu na starcie' - jeśli wypali, to tę teoretyczną
            liczbę dni oczekiwania (9972) będzie można - być może znacząco - zmniejszyć :)

            pozdrawiam,
            m<p>o

            • reptar Re: Czy na pewno skrócenie??? 17.08.02, 20:19
              musztarda_po_obiedzie napisał:

              > Napisałem króciutki program, który symuluje losowanie kolejności więźniów,
              > którzy wchodzą do świetlicy. Dla danej kolejności sprawdzałem, po ilu dniach
              > będziemy mieli pewność odhaczenia wszystkich w dwóch przypadkach:
              > a) gdy odhacza więzień dnia drugiego
              > b) gdy odhacza więzień dnia trzeciego
              >
              > Przeanalizowałem 10000 różnych układów. Oto wyniki:
              > W 4292 przypadkach pewność osiągał szybciej więzień 2, natomiast w 5708
              > przypadkach - więzień dnia 3.



              Metoda (symulacja komputerowa) zasadniczo mi się podoba, a i próbka wydaje się
              duża, choć muszę to sobie jeszcze przemyśleć, zanim się ostatecznie ustosunkuję.

              Ale na razie zajmujesz się tylko porównaniem dwóch więźniów:
              więźnia_dnia_drugiego i więźnia_dnia_trzeciego, jak zrozumiałem?
              No a co z następnymi (i jednym poprzednim)? Skoro 3 empirycznie dał lepszy
              efekt niż 2, to może 4 da jeszcze lepszy wynik, a 8 jeszcze lepszy? Czy
              tendencja się utrzyma czy osiągnie jakieś maksimum i zacznie spadać? I czy
              empirycznie wyznaczona krzywa ilustrująca interesującą nas funkcję będzie
              miała kształt sugerujący rzeczywisyą zależność, czy raczej będzie przypominała
              grzbiet koziołkującego stegozaura? Nie próbuję kwestionować Twojego wyniku,
              ale ciekawość pcha mnie do zadawania tych wszystkich kolejnych pytań. Widzę,
              że Ciebie też to zaintrygowało, więc próbuję Cię jak najbardziej zmobilizować
              (czytaj: podpuścić) do dalszych dociekań ;)
              • musztarda_po_obiedzie Re: Czy na pewno skrócenie??? 17.08.02, 23:54
                reptar napisał:

                > Ale na razie zajmujesz się tylko porównaniem dwóch więźniów:
                > więźnia_dnia_drugiego i więźnia_dnia_trzeciego, jak zrozumiałem?
                > No a co z następnymi (i jednym poprzednim)? Skoro 3 empirycznie dał lepszy
                > efekt niż 2, to może 4 da jeszcze lepszy wynik, a 8 jeszcze lepszy? Czy
                > tendencja się utrzyma czy osiągnie jakieś maksimum i zacznie spadać?

                Metoda WD-2 i WD-3 nie wynika z przypadku ani
                lenistwa_czyli_niechęci_do_sprawdzania_kolejnych_dni. Zająłem się tymi dwoma
                wariantami, ponieważ tylko one dają nam *realne* korzyści:

                W przypadku WD-2 mamy "na dzień dobry" odhaczonego 1 więźnia, a w przypadku WD-
                3 możemy ustalić, czy można odhaczyć jednego, czy dwóch.

                Czy można przesunąć 'testera' na inny dzień? Stosując taki tok myślenia, jak
                przy WD-2 i WD-3, nie można! Nie będziesz w stanie ustalić na podstawie stanu
                żarówki, ilu więźniów zajrzało do świetlicy przed więźniem 4: 1, 2, czy 3??
                Tym bardziej bez sensu wydaje się przesuwanie testera na jeszcze późniejszy
                dzień...

                ... chyba że przyjmie się troszkę inną zasadę na początku :) Wtedy będzie można
                przesunąć testera na późniejszy dzień. Właśnie nad tym myślę. Mam nadzieję, że
                wkrótce będę się mógł pochwalić jakimiś wnioskami...

                A póki co, wyniki symulacji komputerowej dla WD-2 i WD-3 dla ponad 250.000
                układów potwierdzają wcześniejszy rozkład:

                WD-2 szybciej odhacza wszystkich w ok. 42% przypadków (średnio po ok. 10218
                dniach)
                WD-3 szybciej odhacza wszystkich w 58% przypadków (średnio po ok. _9940 dniach)

                > Nie próbuję kwestionować Twojego wyniku,
                > ale ciekawość pcha mnie do zadawania tych wszystkich kolejnych pytań. Widzę,
                > że Ciebie też to zaintrygowało, więc próbuję Cię jak najbardziej zmobilizować
                > (czytaj: podpuścić) do dalszych dociekań ;)

                Owszem, jestem bardzo zaintrygowany - żal mi tych biedaków, bo znając
                Cardemona, to to więzienia wtrącił ich zły Król ot tak sobie, za nic ;)
                A 27 lat to bardzo dłuuuuugo, więc będę dalej myśleć :)

                Pozdrawiam,
                m<p>o
                • cardemon Re: Czy na pewno skrócenie??? 18.08.02, 04:21
                  musztarda_po_obiedzie napisał:

                  > A póki co, wyniki symulacji komputerowej dla WD-2 i WD-3 dla ponad 250.000
                  > układów potwierdzają wcześniejszy rozkład: (...)

                  Sposob, w jaki sie zabrales za te zagadke, bardzo mi sie podoba. W jakim jezyku
                  napisales swoj programik symulacyjny i czy bylbys sklonny go udostepnic?

                  pzdr. CdM
                • reptar Re: Czy na pewno skrócenie??? 18.08.02, 16:16
                  musztarda_po_obiedzie napisał:

                  > Metoda WD-2 i WD-3 nie wynika z przypadku ani
                  > lenistwa_czyli_niechęci_do_sprawdzania_kolejnych_dni. Zająłem się tymi dwoma
                  > wariantami, ponieważ tylko one dają nam *realne* korzyści:


                  Sprawdzenie dla Wd4, Wd5, Wd8 mogłoby uwiarygodnić symulację komputerową jako
                  wiarygodną (właściwą) metodę. Założenie: "tylko te dwa warianty dają nam realne
                  korzyści" brzmi trochę dogmatycznie i psuje całe rozumowanie. Nie kupuję tego,
                  jeśli nie będzie sprawdzone :(

                  Bo ja, mimo wszystko, z dużą rezerwą podchodzę do wyników symulacji
                  komputerowej, choć muszę przyznać, że próbka jest imponująco duża.


                  Ale jeśli Twój WD-2 osiąga sukces po 10218 dniach, a Twój WD-3 po 9940,


                  to ja proponuję takie postępowanie:

                  - wykorzystuję wszystkie Twoje sekwencje i gwałcąc prawa autorskie robię z nich
                  moje sekwencje poprzez obcięcie dnia pierwszego; wolno mi to zrobić, bo skoro
                  wszystko jest przypadkowe, to sekwencje

                  *=> Wd1, Wd2, Wd3, Wd4, Wd5, Wd6 ... Wd-ileś-tam
                  *=>       Wd2, Wd2, Wd3, Wd4, Wd5, Wd6 ... Wd-ileś-tam+1

                  są tak samo przypadkowe.

                  Twój dzień trzeci jest moim dniem drugim. W moim modelu więzień, który u ciebie
                  jest Wd3, u mnie jest Wd2 i osiąga sukces średnio po... 9939 dniach.


                  Na pewno dostrzegasz w moim rozumowaniu pewną nieścisłość. Jeśli w Twojej
                  sekwencji Wd2=Wd3 (i jest różny od Wd1), to Twój Wd3 dokona odhaczenia, a mój
                  Wd2 w paralelnej sekwencji odhaczenia nie zrobi. Zaraz to uwzględnię.

                  Taka sekwencja trafia się średnio raz na sto razy (tu nie trzeba symulacji,
                  zależność jest oczywista). Chcąc więc tę nieścisłość usunąć, trzeba by dodać
                  do mojego wyniku dla mojego Wd2 jeszcze wartość 1/100 * D, gdzie:

                  1/100 - bierze się z tego, że rzecz ma miejsce raz na sto razy
                  D - średni czas, jaki mija od przedostatniego do ostatniego odhaczenia.


                  Żeby wyszło 10217 (jak w Twojej symulacji dla Twojego Wd2), D musiałoby wynieść
                  28100 dni. Doszedłem do absurdu, a przecież nic nie naciągałem.
                  • reptar sorry m<p>o 18.08.02, 16:21
                    sorry m<p>o

                    za powyższe teoretyzowanie, co to było już musztardą po obiedzie wobec Twojego
                    postu niżej (=Twojego dementi)

                    ;)


                    Czytałem i odpisywałem od góry, jak leci.
    • musztarda_po_obiedzie WD-2 i WD-3: dementi wyników symulacji 18.08.02, 12:44
      Napędzany dociekliwością Reptara oraz własnym zaintrygowaniem, postanowiłem
      dopisać do programu jeszcze jeden moduł sprawdzający nieco inną sytuację. Wtedy
      zauważyłem, że w przypadku WD-3 popełniłem błąd, który wypaczył wyniki
      symulacji....

      No cóż, przyznaję ze skruchą, że porównania z moich powyższych postów są
      niewłaściwe. Po poprawieniu programu i dokonaniu nowej symulacji okazuje się,
      że chyba jednak nie ma znaczącej różnicy między WD-2 a WD-3... Oto *prawdziwy*
      rozkład szans (analiza 51000 sytuacji):

      WD-2 szybciej odhacza wszystkich w 25133 przypadków (średnio po 10222 dniach)
      WD-3 szybciej odhacza wszystkich w 25423 przypadków (średnio po 10220 dniach)

      444 pozostałe przypadki to sytuacje, gdy w drugim i trzecim dniu wybrany został
      ten sam więzień.

      Jak widać, różnica jest praktycznie żadna.

      Sorry za zamieszanie. Tym bardziej, że już kombinuję, jak mimo wszystko
      poprawić szanse więźniów i jedynym sposobem udowodnienia moich racji będzie
      znów symulacja komputerowa. Zdaję sobie sprawę, że poprzednią pomyłką
      nadszarpnąłem wiarygodność ewentualnych wyników, które będę chciał przedstawić
      w przyszłości.

      Do Car de Mona - program jest napisany w Visual Basicu. Oczywiście służę nim w
      każdej chwili, daj mi tylko troszkę czasu na wygładzenie jego wyglądu tak, żeby
      był czytelniejszy i upewnienie się, że wszystko liczone jest tak jak należy :)

      Pozdrawiam,
      skruszony_m_p_o
    • Gość: Baton Re: 100 wiezniow i zarowka IP: *.psi-net.pl 18.08.02, 21:51
      Zanim zajrze co tam wymysliliscie sprobuje sam odpowiedziec.... ;-)))

      Wiezien nr 1 (ten, ktory trafi do sali pierwszego dnia)
      pozostawia swiatlo zgaszone....
      Od tej pory postepuja nastepujaco:
      - wiezien, ktory wchodzi do sali po raz pierwszy
      ZAPALA swiatlo jesli bylo zgaszone lub NIC nie robi
      jesli bylo zapalone....
      - wiezien, ktory wchodzi do sali po raz 2, 3, itd.
      NIC nie robi....
      - wiezien nr 1 wchodzi do sali i GASI swiatlo, jesli bylo
      zapalone i zapamietuje, ktory to juz raz, albo nic nie robi,
      jesli swiatlo bylo zgaszone
      Jedynym wiezniem, ktory moze rozstrzygnac kiedy wszyscy byli juz
      w sali jest oczywiscie wiezien nr 1. Zgalsza sie do straznikow,
      gdy wejdzie do sali i po raz 99 bedzie musial zgasic swiatlo..... ;-)))

      Wydaje mi sie, ze jest jeszcze mala mozliwosc ulepszenia algorytmu,
      ale nie chce mi sie juz teraz o tym myslec... "ide" sprawdzic
      co Wy napisaliscie..... :-)))
      • musztarda_po_obiedzie Re: 100 wiezniow i zarowka 18.08.02, 22:34
        Gość portalu: Baton napisał(a):
        > Wydaje mi sie, ze jest jeszcze mala mozliwosc ulepszenia algorytmu,

        Rzeczywiście, można go ulepszyć tak:

        Przez pierwsze 101 dni obowiązuje zasada:
        Jeśli wchodzisz pierwszy raz, nic nie robisz.
        Jeśli wszedłeś drugi raz, a żarówka jest zgaszona, to jest to znak, że jesteś
        pierwszą osobą, która pojawiła się na świetlicy po raz drugi. Zostajesz
        testerem, i możesz odhaczyć już D-2 więźniów (D to dzień, w którym odwiedziłeś
        świetlicę drugi raz). Zapalasz światło - to znak dla wszystkich, którzy się
        pojawią tu aż do 101 dnia, że tester jest już wybrany. Stąd każdy kto się
        pojawi do 101 dnia i zobaczy zapaloną żarówkę, nie może już nic robić.

        Osoba w dniu 101 gasi światło. Od tej pory zasada wygląda tak:
        Ci, którzy byli w świetlicy w dniach 1-101 i zastali za pierwszym razem
        zgaszone światło są już odhaczeni, więc nic nie robią. Pozostali zachowują się
        tak, jakby ich tam jeszcze nigdy nie było, i stosują zasadę jednorazowego
        zapalenia zgaszonej żarówki. No, a tester oczywiście gasi żarówkę i odhacza
        kolejnych więźniów.

        Oczywiście, im póżniej nastąpią pierwsze powtórne odwiedziny więźnia w
        świetlicy w okresie 'testowym' (pierwsze 101 dni), tym więcej będzie więźniów
        odhaczonych 'na dzień dobry'. W wersji super-optymistycznej wszystko będzie
        jasne już w 101 dniu :) (gdy przez 100 dni przez świetlicę przewinie się cała
        setka więźniów, a w 101 dniu jeden z nich wejdzie i zobaczy wciąż zgaszone
        światło). Ale to tylko teoria :(

        Oczywiście korzyści płynące z tego systemu są daleko większe (i chyba bardziej
        oczywiste) niż z porównywania wersji WD-2 i WD-3. Chyba nawet Reptar da się
        przekonać, że możliwość odhaczenia kilku-do-kilkunastu więźniów na samym
        początku wpłynie znacząco na przewidywany czas oczekiwania... Reptar, daj znać
        co o tym myślisz??

        A swoją drogą, testuję to znowu za pomocą symulacji komputerowej. Tym razem
        ogłoszę wyniki, jak się upewnię na 100%, że nie popełniłem błędu pisząc
        program :-p. Ale muszę mieć na to więcej czasu niż miałem dzisiaj :) Może jutro
        będzie u mnie lepiej z czasem??

        Pozdrawiam
        m<p>o
        • cardemon Re: 100 wiezniow i zarowka 19.08.02, 00:07
          musztarda_po_obiedzie napisał:

          > Przez pierwsze 101 dni obowiązuje zasada:
          > Jeśli wchodzisz pierwszy raz, nic nie robisz.
          > Jeśli wszedłeś drugi raz, a żarówka jest zgaszona, to jest to znak, że jesteś
          > pierwszą osobą, która pojawiła się na świetlicy po raz drugi. Zostajesz
          > testerem, i możesz odhaczyć już D-2 więźniów (D to dzień, w którym
          > odwiedziłeś świetlicę drugi raz). Zapalasz światło - to znak dla wszystkich,
          > którzy się pojawią tu aż do 101 dnia, że tester jest już wybrany. Stąd każdy
          > kto się pojawi do 101 dnia i zobaczy zapaloną żarówkę, nie może już nic robić.
          (...)

          Brawo!!! Jest wyrazny postep, ale nadal nie jest to optymalna strategia (tzn.
          zebysmy sie zle nie zrozumieli, ja nie wiem jaka jest optymalna strategia, ale
          czuje, ze jestem juz blisko). W kazdym badz razie tez juz piszę programiki
          symulujace rozne strategie i liczace przecietna ilosc dni do uwolnienia. Bez
          tego sie raczej nie obejdziemy. :(
          Jest to po prostu KAWAL CIEZKIEJ ZAGADY. :)

          Pozdrawiam i zycze wytrwalosci, CdM
        • cardemon Re: 100 wiezniow i zarowka 19.08.02, 03:22
          musztarda_po_obiedzie napisał:

          > A swoją drogą, testuję to znowu za pomocą symulacji komputerowej. Tym razem
          > ogłoszę wyniki, jak się upewnię na 100%, że nie popełniłem błędu pisząc
          > program :-p.

          Moje wyniki symulacji generalnie pokrywaja sie z Twoimi. Dla metody z wybranym
          rachmistrzem, ktory od razu pierwszego dnia zaczyna liczyc, wychodzi mi okolo
          10300 dni, natomiast Twoj ostatni pomysl, ze rachmistrzem staje sie wiezien,
          ktory pierwszy pojawia sie powtornie w swietlicy, daje przecietnie jakies 9450
          dni.

          pzdr. CdM
        • reptar JESTEM POD WRAŻENIEM 19.08.02, 09:20
          musztarda_po_obiedzie napisał:

          > Rzeczywiście, można go ulepszyć tak:
                              (...)
          > Oczywiście korzyści płynące z tego systemu są daleko większe (i chyba
          > bardziej oczywiste) niż z porównywania wersji WD-2 i WD-3. Chyba nawet
          > Reptar da się przekonać...



          Napiszę krótko, ale głośno: JESTEM POD WRAŻENIEM!
        • Gość: Baton Re: 100 wiezniow i zarowka IP: 213.17.216.* 19.08.02, 11:13
          > > Wydaje mi sie, ze jest jeszcze mala mozliwosc ulepszenia algorytmu,
          >
          > Rzeczywiście, można go ulepszyć tak:

          Wiedzialem.... ;-)))
          Moje rozwazania tez zmierzaly w tym kierunku, ale niestety
          nie mialem czasu ich dokladnie przeanalizowac, wiec pozostaje
          pogratulowac m<p>o pomyslu.... :-)))

          Mam tylko drobne uwagi..... ;-)))

          > Przez pierwsze 101 dni obowiązuje zasada:

          Chyba wystarczy 100 dni, bo jesli wiezien do "ciemnicy" wejdzie
          100 dnia i bedzie to jego pierwsze wejscie, to znaczy,
          ze nikt nie byl tutaj po raz drugi i idziesz z ta rewelacja
          do straznika.... :-)))

          > Jeśli wchodzisz pierwszy raz, nic nie robisz.
          > Jeśli wszedłeś drugi raz, a żarówka jest zgaszona, to jest to znak, że jesteś
          > pierwszą osobą, która pojawiła się na świetlicy po raz drugi. Zostajesz
          > testerem, i możesz odhaczyć już D-2 więźniów (D to dzień, w którym
          odwiedziłeś

          Tutaj drobna poprawka..... Tester "odhacza" D-1 wiezniow!!!
          W koncu tylko on jest tutaj ponownie.....
          Przy zalozeniu D-2 wchodzac z rzedu w dzien 1 i 2 nie odhaczylbyl
          mikogo, a to jest przeciez bzdura... ;-)))

          > świetlicę drugi raz). Zapalasz światło - to znak dla wszystkich, którzy się
          > pojawią tu aż do 101 dnia, że tester jest już wybrany. Stąd każdy kto się
          > pojawi do 101 dnia i zobaczy zapaloną żarówkę, nie może już nic robić.

          W niczym nie przeszkodzi tutaj moje ograniczenie do 100 dni....

          > Osoba w dniu 101 gasi światło. Od tej pory zasada wygląda tak:
          > Ci, którzy byli w świetlicy w dniach 1-101 i zastali za pierwszym razem
          > zgaszone światło są już odhaczeni, więc nic nie robią. Pozostali zachowują
          się
          > tak, jakby ich tam jeszcze nigdy nie było, i stosują zasadę jednorazowego
          > zapalenia zgaszonej żarówki. No, a tester oczywiście gasi żarówkę i odhacza
          > kolejnych więźniów.

          Momentem drazliwym jest ponowne wejscie do sali w dniu 100....
          Jesli wowczas wiezien "zobaczy ciemnosc", to:
          - wie, ze lacznie z nim bylo juz w sali 99 wiezniow
          - POZOSTAWIA swiatlo zgaszone!!!
          - czeka az brakujacy wiezien swiatlo zapali i.... biegnie do straznika.. :-))

          Pasuje?
          Ja mysle, ze tak..... ;-)))
          Moze jednak jeszcze ktos to udoskonali???
          • reptar Re: 100 wiezniow i zarowka 19.08.02, 11:34
            Gość portalu: Baton napisał(a):

            > Przy zalozeniu D-2 wchodzac z rzedu w dzien 1 i 2 nie odhaczylbyl
            > mikogo, a to jest przeciez bzdura... ;-)))


            Odhaczenie samego siebie to nieistotna formalność. Można odhaczyć siebie i
            liczyć do 100, albo nie odhaczać siebie i liczyć do 99.
          • musztarda_po_obiedzie Re: 100 wiezniow i zarowka 19.08.02, 12:16
            Postaram się odnieść tutaj do tego co napisali Car de Mon z Batonem:


            Gość portalu: Baton napisał(a):

            > Mam tylko drobne uwagi..... ;-)))
            > > Przez pierwsze 101 dni obowiązuje zasada:
            >
            > Chyba wystarczy 100 dni, bo jesli wiezien do "ciemnicy" wejdzie
            > 100 dnia i bedzie to jego pierwsze wejscie, to znaczy,
            > ze nikt nie byl tutaj po raz drugi i idziesz z ta rewelacja
            > do straznika.... :-)))

            Przyznaję rację. Setka dni wystarczy. Zauważ jednak, że różnica w naszych
            pomysłach będzie tylko w tym szczególnym przypadku, gdy przez pierwsze 100 dni
            każdy wejdzie tylko raz :) U mnie po prostu poszedłby meldować Sto-pierwszy
            zamiast Setnego :) Niemniej jednak przyznaję rację Twojej poprawce.

            > Tutaj drobna poprawka..... Tester "odhacza" D-1 wiezniow!!!
            > W koncu tylko on jest tutaj ponownie.....
            > Przy zalozeniu D-2 wchodzac z rzedu w dzien 1 i 2 nie odhaczylbyl
            > mikogo, a to jest przeciez bzdura... ;-)))

            To kwestia sposobu liczenia. Tak jak zauważył już reptar, 'tester' liczy do 99 -
            siebie nie liczy, bo wie, że był :) Stąd u mnie D-2.

            cardemon napisał:

            > Moje wyniki symulacji generalnie pokrywaja sie z Twoimi.

            OK, doskonale, że też równolegle robisz symulację - to pomoże weryfikować
            wyniki - jeśli będą podobne, to znaczy że dobrze kombinujemy, jeśli znacząco
            różne, to znaczy że ktoś popełnia błąd w obliczeniach (tak jak ja poprzednio).

            > Dla metody z wybranym
            > rachmistrzem, ktory od razu pierwszego dnia zaczyna liczyc, wychodzi mi okolo
            > 10300 dni,

            A to przypomina mi moje obliczenia dla WD-2 i WD-3 (ok. 10222 dni).

            > natomiast Twoj ostatni pomysl, ze rachmistrzem staje sie wiezien,
            > ktory pierwszy pojawia sie powtornie w swietlicy, daje przecietnie jakies
            > 9450 dni.

            Co sugeruje, że znowu popełniłem błąd w programie - mnie wychodzi znacznie
            mniej... Zaraz wszystko posprawdzam.

            Tak czy owak, na pewno lepiej na testera wybrać więźnia który jako pierwszy
            pojawi się po raz drugi w świetlicy, niż zakładać, że będzie to pierwszy,
            drugi, czy jakiś-tam.
            Pozdrawiam,
            m<p>o
    • musztarda_po_obiedzie Re: 100 wiezniow i zarowka 19.08.02, 22:56
      Krótkie podsumowanie tego co wiem (na podstawie symulacji - tym razem
      bezbłędnej :) :

      Wybranie więźnia dnia 2 lub 3 daje średni czas oczekiwania rzędu 10220 dni.

      Metoda "ruchomego testera" - gdzie okres pierwszych stu dni jest okresem
      testowym, a testerem zostaje więzień, który pierwszy odwiedzi świetlicę
      dwukrotnie - daje średni czas oczekiwania 9380 dni. Car de Mon podawał 9450 dni
      dla tej sytuacji. Czy 70 dni mieści się w granicach błędu statystycznego, czy
      raczej jest to błąd któregoś z nas? (Jeśli to drugie, to pewnie mój :)

      Co ważne: wybranie metody 'ruchomego testera' jest korzystne (daje najkrótszy
      czas oczekiwania) w 57% przypadków, natomiast metoda WD-2 lub WD-3 daje lepszy
      efekt w 45,5% sytuacji (to nie błąd - dodatkowe 2.5 procent przypadków to
      sytuacje, gdzie i WD-x i ruchomy tester kończą odhaczanie w tym samym dniu :)
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

      To tyle. Czy można wymyślić coś lepszego??

      Ja mam tylko jeden pomysł, ale raczej kosmetyczny:

      Czy warto czekać z okresem testowym aż 100 dni? Zwykle 'ruchomy tester'
      odnajduje się znacznie wcześniej - potem trzeba czekać 'bezproduktywnie' aż
      upłynie te 100 dni... Chętnie bym więc skrócił ten czas rozruchu... tylko do
      ilu dni?? 75?? 50?? 25?? Jeszcze mniej??

      Hmm, chyba zaczną się kolejne symulacje na komputerze :) Tylko czy warto?? Na
      intuicję widać, że korzyść będzie jedynie wielkości tych zaoszczędzonych dni z
      pierwszej setki...

      Myślmy, myślmy - 9380 (lub 9450) dni to wciąż cholernie dużo !!

      Pozdrawiam,
      Robert (aka m<p>o)
      • cardemon Re: 100 wiezniow i zarowka 20.08.02, 04:50
        musztarda_po_obiedzie napisał:

        > Wybranie więźnia dnia 2 lub 3 daje średni czas oczekiwania rzędu 10220 dni.
        >
        > Metoda "ruchomego testera" - gdzie okres pierwszych stu dni jest okresem
        > testowym, a testerem zostaje więzień, który pierwszy odwiedzi świetlicę
        > dwukrotnie - daje średni czas oczekiwania 9380 dni.

        Mam bardzo podobne wyniki obliczen, mozna wiec uznac, ze symulacje sa
        przeprowadzone poprawnie. Roznice w obliczeniach moga byc wina generatora liczb
        losowych. Napisalem krotki programik, generujacy losowo 100 liczb od 1 do 100 i
        okazalo sie, ze za kazdym uruchomieniem programiku, generowane sa takie same
        ciagi liczb. A moze Ty masz jakis dobry algorytm na "bardziej losowa" liczbe
        losowa?

        > To tyle. Czy można wymyślić coś lepszego??

        Tak, jest lepszy algorytm!!! :)

        > Ja mam tylko jeden pomysł, ale raczej kosmetyczny:
        > Czy warto czekać z okresem testowym aż 100 dni?

        Wiadomo, ze nie warto czekac do setnego dnia. Prawdopodobienstwo, ze w ciagu
        tych stu dni kazdego dnia bedzie w celi inny wiezien, rowna sie 100!/(100^100)
        (sto silnia dzielone przez sto do potegi setnej), jesli ktos chce, niech
        policzy. Jest to tak nikla szansa, ze nie warto nia sobie zaprzatac glowy.
        Predzej sto razy pod rzad wypadnie orzel w rzucie moneta (prawdopodobienstwo =
        1/2^100) (czy dobrze oszacowalem te prawdopodobienstwa?). Ile dni wiec czekac?
        Zrobilem symulacje. Na 10 tys. prob nie zdarzylo sie ani razu, zeby trwalo
        dluzej niz 50 dni, az trafil sie wiezien, ktory jako pierwszy zawital powtornie
        do swietlicy. I tylko w dwoch przypadkach na te 10 tys. zdarzylo sie tak, ze
        trwalo to dluzej niz 40 dni, zanim nastapila pierwsza ponowna wizyta jakiegos
        wieznia. Przecietnie po 13 dniach nastepuje rewizyta i wylonienie 'ruchomego
        testera'.

        > Hmm, chyba zaczną się kolejne symulacje na komputerze :) Tylko czy warto?? Na
        > intuicję widać, że korzyść będzie jedynie wielkości tych zaoszczędzonych dni
        > z pierwszej setki...

        Pobawilem sie troche w inne symulacje i wyszlo tam kilka innych ciekawych
        rzeczy. Mianowicie przy metodzie "zliczajacy dnia 1", wiezien liczacy jest w
        swietlicy przecietnie 104.23 razy w ciagu tych 10300 dni. Natomiast przy
        metodzie "zliczajacy dnia D", wiezien liczacy sklada przecietnie 96.33 wizyty,
        zanim oglasza zakonczenie liczenia. Ciekawe sa tez liczby wizyt innych
        wiezniow, bowiem kazdy z nich sklada wizyte w swietlicy najczesciej od 90 do
        110 razy, rzadziej od 70-120, a sporadycznie mniej niz 60 i wiecej niz 130.
        Te obliczenia wskazuja, ze w rozwiazaniu "zliczajacy dnia D" tkwi jeszcze spory
        zapas. ;)

        > Myślmy, myślmy - 9380 (lub 9450) dni to wciąż cholernie dużo !!

        Tez wszystkich bardzo zachecam, nawet tych, ktorzy nie moga przeprowadzic
        symulacji. Podawajcie wszystkie pomysly, nawet gorsze od tego, na czym dzisiaj
        tu stanelismy. Nawet niepelne. Kazdy pomysl moze byc przydatny.

        pzdr. CdM
        • reptar Re: 100 wiezniow i zarowka 20.08.02, 10:23
          cardemon napisał:

          > Napisalem krotki programik, generujacy losowo 100 liczb od 1 do 100 i
          > okazalo sie, ze za kazdym uruchomieniem programiku, generowane sa takie same
          > ciagi liczb. A moze Ty masz jakis dobry algorytm na "bardziej losowa" liczbe
          > losowa?


          W czym piszesz tę symulację?
          Nie wiem, jak to wygląda w innych językach, ale w Pascalu oprócz funkcji random
          (liczba losowa) jest jeszcze procedura randomize (uruchomienie generatora liczb
          losowych). Jeśli pominiesz randomize, a używasz random, efekt jest właśnie taki.
          Te same losowe liczby przy kolejnych uruchomieniach programu.
          • cardemon Re: 100 wiezniow i zarowka 20.08.02, 18:07
            reptar napisał:

            > Nie wiem, jak to wygląda w innych językach, ale w Pascalu oprócz funkcji
            > random (liczba losowa) jest jeszcze procedura randomize (uruchomienie
            > generatora liczb losowych). Jeśli pominiesz randomize, a używasz random,
            > efekt jest właśnie taki.

            Wielkie dzieki! Juz nanioslem poprawki. Teraz wreszcie to wszystko sensownie
            chodzi. :)

            pzdr.
      • cardemon Re: 100 wiezniow i zarowka 20.08.02, 06:32
        musztarda_po_obiedzie napisał:

        > (...) Czy można wymyślić coś lepszego??
        >
        > Ja mam tylko jeden pomysł, ale raczej kosmetyczny:
        >
        > Czy warto czekać z okresem testowym aż 100 dni? (...)
        > Chętnie bym więc skrócił ten czas rozruchu... tylko do
        > ilu dni?? 75?? 50?? 25?? Jeszcze mniej??

        Postscriptum do tego co napisalem w poprzednim poscie.
        Zrobilem zalozenie, ze wylonienie "wieznia zliczajacego" nastepuje w okresie do
        50 dni. Skracam wiec okres wylonienia "wieznia zliczajacego" ze 100 do 50 dni.
        Zysk dzieki temu osiagniety przekracza 50 dni. Symulacja wykazała bowiem, ze
        mozna dzieki temu prostemu zabiegowi skrocic czas potrzebny do uwolnienia
        wiezniow przecietnie o prawie 150 dni.

        CdM
        • musztarda_po_obiedzie Re: 100 wiezniow i zarowka 20.08.02, 21:23
          cardemon napisał:
          > Zrobilem zalozenie, ze wylonienie "wieznia zliczajacego" nastepuje w okresie
          do
          >
          > 50 dni. Skracam wiec okres wylonienia "wieznia zliczajacego" ze 100 do 50
          dni.
          > Zysk dzieki temu osiagniety przekracza 50 dni. Symulacja wykazała bowiem, ze
          > mozna dzieki temu prostemu zabiegowi skrocic czas potrzebny do uwolnienia
          > wiezniow przecietnie o prawie 150 dni.

          No nie wiem, czy tak jest na pewno. Ja też skracałem czas testowania. Oto
          wyniki:

          okres testowy :100 dni --> średni czas oczekiwania 9385 dni
          okres testowy : 80 dni --> średni czas oczekiwania 9362 dni
          okres testowy : 40 dni --> średni czas oczekiwania 9320 dni

          wszystkie wyniki na podstawie symulacji ok. 1.000.000 (miliona) układów.

          A więc średni czas oczekiwania zmniejsza się, ale właściwie tylko o tyle, o ile
          skracamy okres testowy.

          A teraz pytanie: do ilu dni można skracać okres testowy z korzyścią?? Bo w
          pewnym momencie trend się odwróci i średni czas oczekiwania zacznie się znowu
          wydłużać, prawda? Przykładowo, dla okresu 15 dni czas oczekiwania wyniósł w
          mojej symulacji aż 9434 dni! Te dane są nieoficjalne, symulacja objęła niewiele
          wyników, ale wzrost widać wyraźnie.

          No więc jaka liczba dni testowych jest najoptymalniejsza??

          pozdrawiam,
          m<p>o
    • mesquaki Re: 100 wiezniow i zarowka 20.08.02, 17:56
      Zastanawiam się, jakie szanse mieliby więźniowie, gdyby nie stosowali żadnej
      strategii i zameldowali się w ciemno, po, dajmy na to, 10 latach?
      • cardemon Re: 100 wiezniow i zarowka 20.08.02, 18:03
        mesquaki napisała:

        > Zastanawiam się, jakie szanse mieliby więźniowie, gdyby nie stosowali żadnej
        > strategii i zameldowali się w ciemno, po, dajmy na to, 10 latach?

        Zapewne dosc wysokie, ale takie rozwiazanie nie spelnia warunkow zadania.
        Wiezniowie bowiem uzgodnili miedzy soba, ze nie beda strzelac w ciemno, tylko
        ida na pewniaka.

        pzdr.
        • mesquaki Re: 100 wiezniow i zarowka 20.08.02, 18:46
          Nie, no oczywiście żadne rozwiązanie. Czysta ciekawość, jaki procent Waszych
          symulowanych zestawów więźniów poszłaby pod mur po 10 latach.
          Ale, jak zwykle, dywagacja nie na temat :). Przepraszam.
          • musztarda_po_obiedzie Re: 100 wiezniow i zarowka 20.08.02, 20:19
            mesquaki napisała:

            > Nie, no oczywiście żadne rozwiązanie. Czysta ciekawość, jaki procent Waszych
            > symulowanych zestawów więźniów poszłaby pod mur po 10 latach.
            > Ale, jak zwykle, dywagacja nie na temat :). Przepraszam.

            Mes, obiecuję stosowną symulację specjalnie dla Ciebie :)
            Pozdrawiam,
            m<p>o
            • mesquaki Re: 100 wiezniow i zarowka 20.08.02, 20:50
              ??? Co to bylo, Robert?? Czy wyrażona niecenzuralnie radość z wynalezienia
              nowego rozwiązania??
              W tym miejscu mam tylko "wiadomosc zostala usunieta ze wzgledu na zlamanie
              regulaminu".

              Poza tym, już sobie, ciemna masa marsjańska, policzyłam.:)
              Po 9450 dniach wychodza mi szanse na rozstrzelanie (.99)^9449 (czy dobrze???)
              co wynosi ok 5e-42. To niewiele więcej niż prawdopodobieństwo, że przez
              pierwsze 100 dni każdego dnia w celi będzie kto inny. Wedlug wzoru Cardemona
              wychodzi mi ok 9e-43.
              Oj, czuję, że zostanę wykopana z tego forum :(.
    • musztarda_po_obiedzie Re: 100 wiezniow i zarowka 20.08.02, 20:52
      Obśmiałem się okropnie widząc swój ostatni post na forum. Ha-ha.

      Niniejszym ogłaszam, że żadnego prawa ani regulaminu nie złamałem.

      Sprostowanie niniejsze zamieszczam celem zapobieżenia sytuacji, że w swej
      kolejnej zagadce Car de Mon umieści mnie w jednej celi z groźnymi bandziorami ;)

      pozdrawiam,
      musztardek_niewinny

      PS. W poprzednim poście napisałem: "Mes, obiecuję specjalną symulację
      specjalnie dla Ciebie" jako odpowiedź na pytanie co się stanie po 10 latach...

      • mesquaki Re: 100 wiezniow i zarowka 20.08.02, 21:30
        musztarda_po_obiedzie napisał:

        > PS. W poprzednim poście napisałem: "Mes, obiecuję specjalną symulację
        > specjalnie dla Ciebie" jako odpowiedź na pytanie co się stanie po 10 latach...

        Dziękuję, dziękuję uprzejmie! :)).

        > Sprostowanie niniejsze zamieszczam celem zapobieżenia sytuacji, że w swej
        > kolejnej zagadce Car de Mon umieści mnie w jednej celi z groźnymi
        > bandziorami ;

        No nie! Choć nie wątpię, że wyciągnąłbyś się stamtąd...

        pozdrawiam
        mes
        • musztarda_po_obiedzie W ciemno po 10 latach (dla Mesquaki) 21.08.02, 14:53
          Kolejna symulacja komputerowa: analizowałem różne układy, sprawdzając po jakim
          czasie świetlicę odwiedzają wszysscy więźniowie (tzn. po ilu dniach już cała
          setka zajrzała do świetlicy).

          Analiza objęła 4 miliony losowych sytuacji. W ŻADNYM PRZYPADKU nie zdarzyło
          się, żeby po 4 latach jeszcze któregoś więźnia nie było w świetlicy !!!
          Niesamowite!!

          Mes, myślę, że meldując w ciemno po 10 latach, jak sugerowałaś, nie ma
          praktycznie szans na stracenie głowy :).

          No, chyba że strażnik jest złośliwy będzie losował tak, aby pominąć jednego z
          więźniów przez pierwsze 10 lat :) Wtedy mamy problem...

          Pozdrawiam,
          Robert
          m<p>o
          • reptar Losowo znaczy losowo 21.08.02, 15:06
            musztarda_po_obiedzie napisał:

            > No, chyba że strażnik jest złośliwy będzie losował tak, aby pominąć jednego z
            > więźniów przez pierwsze 10 lat :) Wtedy mamy problem...



            Nie mamy problemu. W treści zadania jest powiedziane wyraźnie:

            Kazdego dnia straznik wiezienny wybiera *losowo* jednego wieznia...

            Jeśli strażnik jest złośliwy i jego złośliwość wpływa na wybór, wtedy nie jest
            losowo!

            Losowość jest tak samo gwarantowana jak to, że żaden więzień nie zemrze
            i jak to, że żarówka się nigdy nie przepali ;)
            • Gość: Baton Re: Losowo znaczy losowo IP: 213.17.216.* 21.08.02, 15:10
              Pewne jest tez, ze cyt.:

              "Ten ktory oswiadczy wiec, ze wszyscy juz byli w
              swietlicy, musi byc tego pewien na 100%."

              Wiec nawet przy SUPER optymistycznym podejsciu
              ten sposob nam odpada... :-(((
              • reptar Re: Losowo znaczy losowo 21.08.02, 15:17
                Gość portalu: Baton napisał(a):

                > Pewne jest tez, ze cyt.:
                >
                > "Ten ktory oswiadczy wiec, ze wszyscy juz byli w
                > swietlicy, musi byc tego pewien na 100%."
                >
                > Wiec nawet przy SUPER optymistycznym podejsciu
                > ten sposob nam odpada... :-(((

                Rzeczywiście. Stwierdzenie, że ten, który oświadczy, musi być tego pewien -
                wziąłem raczej za psychologiczny komentarz niż za warunek. Ale po zastanowieniu
                przyznaję - to jest konstrukcyjny warunek zadania (podobnie jak losowość etc.).

            • marchewa4 Re: Losowo znaczy losowo (ale z jakim prawd.?) 21.08.02, 15:31
              reptar napisał:

              > musztarda_po_obiedzie napisał:
              >
              > > No, chyba że strażnik jest złośliwy będzie losował tak, aby pominąć jedneg
              > o z
              > > więźniów przez pierwsze 10 lat :) Wtedy mamy problem...
              >
              > Nie mamy problemu. W treści zadania jest powiedziane wyraźnie:
              >
              > Kazdego dnia straznik wiezienny wybiera *losowo* jednego wieznia...
              >
              > Losowość jest tak samo gwarantowana jak to, że żaden więzień nie zemrze
              > i jak to, że żarówka się nigdy nie przepali ;)

              W zadaniu brakuje oczywiscie zalozenia, ktore wszyscy poczyniliscie, a
              mianowicie, ze rozklad losowy jest rownomierny. To tylko tak, dla porzadku,
              wiem, ze to umknelo Autorowi i powinno tam byc.

              Bo *losowo* wcale nie oznacza tego, ze kazdy wiezien trafia do swietlicy z
              jednakowym prawdopodobienstwem.

              Pozdrawiam wszystkich

              M.
              • reptar Re: Losowo znaczy losowo (ale z jakim prawd.?) 21.08.02, 15:39
                marchewa4 napisał:

                > Bo *losowo* wcale nie oznacza tego, ze kazdy wiezien trafia do swietlicy z
                > jednakowym prawdopodobienstwem.


                Losowo oznacza tylko:
                ewentualna złośliwość klawisza nie może wpłynąć na proces losowania.
                Nic więcej nie miałem na myśli.

                Ale swoją drogą to chyba każdy więzień trafia do świetlicy z jednakowym
                prawdopodobieństwem? Jednak?
                • marchewa4 Takie tam dywagacje (prawie nie na temat) 21.08.02, 15:54
                  reptar napisał:

                  > marchewa4 napisał:
                  >
                  > > Bo *losowo* wcale nie oznacza tego, ze kazdy wiezien trafia do swietlicy z
                  > > jednakowym prawdopodobienstwem.
                  >
                  >
                  > Losowo oznacza tylko:
                  > ewentualna złośliwość klawisza nie może wpłynąć na proces losowania.

                  Chyba, ze decyduje on o sposobie losowania, a co za tym idzie rozkladzie
                  losowym. ;-)
                  Np. wezmy 100 kartek z numerami wiezniow. Jedna losowo odlozmy na 10 lat na
                  bok, a z pozostalych z rownym pr. losujmy codziennie jedna (ze zwracaniem
                  oczywiscie). Po 10 latach dajemy odlozona karteczke z powrotem do puli,
                  losujemy jedna i odkladamy na nastepne 10 lat itd. Ten proces jest losowy, co
                  wiecej, kazdy wiezien jest losowany z jednakowym prawdopodobienstwem, ale jest
                  to proces "zlosliwy" (zwlaszcza wobec propozycji Mesquaki ;-)).

                  > Ale swoją drogą to chyba każdy więzień trafia do świetlicy z jednakowym
                  > prawdopodobieństwem? Jednak?

                  Dla rozwiazania zadania nie ma to znaczenia, skoro wiezien meldujacy musi byc
                  pewien. Dla symulacji, ktore pare osob tu przeprowadza (a i ja sam sie tym w
                  wolnych chwilach zabawiam) ma to znaczenie kolosalne. Przyjmuje, ze ten rozklad
                  jest rownomierny w takim sensie, jak to wszyscy tu rozumieja, tzn. codziennie z
                  puli wszystkich wiezniow losowany jest z jednakowym prawdopodobienstwem 1/100
                  jeden z nich.

                  Pozdrawiam

                  M.
                  • reptar Przyznaję: bardzo cenne spostrzeżenie 21.08.02, 15:58
                    marchewa4 napisał:

                    > Chyba, ze decyduje on o sposobie losowania, a co za tym idzie rozkladzie
                    > losowym. ;-)


                    Muszę przyznać, że w ogóle mi to nie przyszło do głowy. Bardzo cenne
                    spostrzeżenie.

                    Wprawdzie, jak sam zauważasz, nie ma to znaczenia dla metody, która ma dać
                    pewność, niemniej wciągnął mnie nie tylko ścisły aspekt tego zadania ;)
              • musztarda_po_obiedzie Re: Losowo znaczy losowo (ale z jakim prawd.?) 21.08.02, 15:42
                Ojej, ojej, ale się zrobiła wrzawa!

                Przede wszystkim - badałem, czy warto meldować w ciemno, bo mesquaki podrzuciła
                pomysł i mnie to też ciekawiło. Nie uznaję tego podejścia za lepsze od tego co
                do tej pory wymyśliliśmy, bo... chodzi o tę 100% pewność.

                Oczywiste jest, że w ramach rozwiązania trzeba znaleźć metodę dającą 100%
                pewność.

                Mój post z 14.53 był tylko dygresją od głównego nurtu poszukiwań :)

                pozdrawiam,
                Robert
                • reptar Re: Losowo znaczy losowo (ale z jakim prawd.?) 21.08.02, 15:50
                  musztarda_po_obiedzie napisał:

                  > Ojej, ojej, ale się zrobiła wrzawa!
                  > Przede wszystkim - badałem, czy warto meldować w ciemno, bo


                  Hej hej,
                  przyczyny Twojego zaangażowania w to obliczenie są dla wszystkich jasne.
                  My sobie tylko tak dywagujemy.
    • mesquaki Re: 100 wiezniow i zarowka 21.08.02, 04:30
      Hehe, mam jeszcze jeden pomysł, ale jako że średni czas oczekiwania tak na oko
      wygląda mi na porównywalny z wiekiem wszechświata, to zachowam tę przegenialną
      ideę dla siebie :)))
      • cardemon Re: 100 wiezniow i zarowka 21.08.02, 18:18
        mesquaki napisała:

        > Hehe, mam jeszcze jeden pomysł, ale jako że średni czas oczekiwania tak na
        > oko wygląda mi na porównywalny z wiekiem wszechświata, to zachowam tę
        > przegenialną ideę dla siebie :)))

        Mes, nie badz samolubna i podziel sie z nami. W tej zagadce bedzie tez
        przydzielna nagroda za strategie na najdluzszy czas uwolnienia wiezniow. :)
        Swoja droga chyba domyslam sie Twojego rozwiazania i w skrocie powiem tylko, ze
        trwa ono o jakies 2000-3000 razy krocej niz wiek wszechswiata. Nie jest wiec
        tak zle! ;)

        pozdr. CdM
        • mesquaki Re: 100 wiezniow i zarowka 21.08.02, 18:56
          cardemon napisał:


          > Mes, nie badz samolubna i podziel sie z nami. W tej zagadce bedzie tez
          > przydzielna nagroda za strategie na najdluzszy czas uwolnienia wiezniow. :)
          > Swoja droga chyba domyslam sie Twojego rozwiazania i w skrocie powiem tylko,
          ze
          >
          > trwa ono o jakies 2000-3000 razy krocej niz wiek wszechswiata. Nie jest wiec
          > tak zle! ;)
          >
          > pozdr. CdM

          Cardemon, domyslic sie nietrudno i chyba wiesz, ze nie ma sie czym chwalic.:)
          Nagrode to juz pozwole sama sobie przyznac ;).
          Natomiast zastanawia mnie co innego. Chodzilo mi po glowie jakies
          zsynchronizowanie liczby zaliczonych wiezniow z kolejnym dniem no i jak tak sie
          wszyscy zsynchronizowali to i mamy czas 10^44 dni. A jak patrze na ostatni
          pomysl Musztardy to wyglada jakby synchronizowali sie do czterech. To wieksza
          ich liczba nie moze?
          Coz, podejrzewam ze to kompletna bzdura i slepy zaulek ;)
    • musztarda_po_obiedzie Strategia 'ruchomego testera' - podsumowanie 21.08.02, 16:02
      'Podsumowanie' w temacie to może za duże słowo, bo ktoś może jeszcze chcieć
      drążyć tę metodę postępowania, ale ja już chyba sobie daruję. Oto moje ostatnie
      wnioski:

      okres testowy : 40 dni --> SCO (średni czas oczekiwania) = 9320 dni
      okres testowy : 35 dni --> SCO (średni czas oczekiwania) = 9317 dni

      Jak już pisałem, być może można skrócić okres testowy jeszcze o kilka dni
      uzyskując analogiczne skrócenie SCO również o kilka dni. Ale nie będę już tego
      sprawdzać. Ta ścieżka jest dla mnie już wyczerpana. Że tak powiem, nic więcej z
      żarówki nie wyciśniemy.

      Ogłaszam za to nową strategię. Jest tak pokrętna, że szczegóły napiszę chyba
      dopiero wieczorem. Ale podam ideę w skrócie:

      1. Zaczynamy tak samo, od okresu testowego (35 dni), żeby wybrać testera.
      2. Tester zlicza wizyty, ale inni więźniowie pośrednio też to robią.
      3. W zależności od dnia wizyty, zapalona żarówka oznacza wizytę 1, 2, 3, lub 4
      więźniów (tak!!)

      Bardzo to skomplikowane, ale najważniejsze, że skuteczne!
      Analiza 86.000 przypadków (na razie :) wskazuje ŚCO rzędu... 6700 dni. A więc
      znaczne skrócenie. Dodam, że algorytm działania, jaki wymyśliłem dla tej
      strategii nie jest z pewnością optymalny, więc być może bedzie się dało coś
      jeszcze uszczknąć z tej liczby.

      Na razie znikam,
      i pozdrawiam,
      robert (m<p>o)
      • cardemon Re: Strategia 'ruchomego testera' - podsumowanie 21.08.02, 17:41
        musztarda_po_obiedzie napisał:

        > Ogłaszam za to nową strategię. Jest tak pokrętna, że szczegóły napiszę chyba
        > dopiero wieczorem. Ale podam ideę w skrócie:
        >
        > 1. Zaczynamy tak samo, od okresu testowego (35 dni), żeby wybrać testera.
        > 2. Tester zlicza wizyty, ale inni więźniowie pośrednio też to robią.
        > 3. W zależności od dnia wizyty, zapalona żarówka oznacza wizytę 1, 2, 3, lub
        > 4 więźniów (tak!!)

        Cieplo, cieplo...!!! :)
      • Gość: Baton Re: Strategia 'ruchomego testera' - podsumowanie IP: 213.17.216.* 23.08.02, 11:23
        musztarda_po_obiedzie napisał:
        > 'Podsumowanie' w temacie to może za duże słowo, bo ktoś może jeszcze chcieć
        > drążyć tę metodę postępowania, ale ja już chyba sobie daruję. Oto moje
        [...]

        No to jeszcze cos mi przyszlo do glowy.....
        Zalozmy, ze okres testowy wynosi 33 dni (A co! Tak ladnie to wyglada.) ;-))
        Rozumiem, ze zgodnie z naszymi zalozeniami WD-33:
        - widzi wlaczone swiatlo i je gasi (nie jest testerem);
        - widzi swiatlo zgaszone i nic nie robi (zostaje testerem; licznik=33)?
        Od tej pory kazdy, kto nie byl jeszcze w sali, albo byl w okresie
        testowym, ale swiatlo bylo juz zapalone teraz sam je zapala,
        natomiast gasi je tyko testeri zwieksza licznik o 1.

        > Jak już pisałem, być może można skrócić okres testowy jeszcze o kilka dni
        > uzyskując analogiczne skrócenie SCO również o kilka dni. Ale nie będę już
        tego
        > sprawdzać. Ta ścieżka jest dla mnie już wyczerpana. Że tak powiem, nic więcej
        z
        > żarówki nie wyciśniemy.

        No i chyba jeszcze uda sie nieco wycisnac zmieniajac pierwszy
        z warunkow dla WD-33 na:
        - widzi wlaczone swiatlo i je gasi jesli byl w sali PRZED wyborem
        testera albo sam jest testerem lub tez pozostawia wlaczone jesli
        nie byl w sali albo w niej byl PO wyborze testera a sam nim nie jest

        Co to da?
        Albo WD-33 swiatlo zgasi i bedzie mogl je zapalic inny wiezien,
        albo WD-33 SAM pozostawi swiatlo jako sygnal dla testera.
        W ten sposob eliminujemy przypadki, gdy WD-33 powinien swiatlo
        zapalic, a od dnia 33 do pierwszej wizyty testera nikt inny tego nie
        moze zrobic (wszyscy pozostawia swiatlo zgaszone).
        Nie wiem czy m<p>o zrobi jakas symulacje, ale wydaje sie, ze SCO
        minimalnie sie zmniejszy...
    • cardemon Re: 100 wiezniow i zarowka 21.08.02, 19:11
      mesquaki napisała:

      > Chodzilo mi po glowie jakies
      > zsynchronizowanie liczby zaliczonych wiezniow z kolejnym dniem no i jak tak
      > sie wszyscy zsynchronizowali to i mamy czas 10^44 dni.

      Hmm, za to rzeczywiscie bedzie nagroda za nadluzszy algorytm. ;)
      Ja myslalem o innym, "troche" krotszym rozwiazaniu, chociaz tez z
      gatunku "modulo 100"...

      > A jak patrze na
      > ostatni pomysl Musztardy to wyglada jakby synchronizowali sie do czterech.
      > To wieksza ich liczba nie moze?

      Oni sie nie "synchronizuja", to licznik bije inaczej w pewnych dniach, ale nie
      bede zdradzal rozwiazania...

      > Coz, podejrzewam ze to kompletna bzdura i slepy zaulek ;)

      Eee tam od razu bzdura. W kazdym pomysle cos jest i warto nad kazdym sie
      zastanowic... :)

      pzdr. CdM
    • cardemon Re: 100 wiezniow i zarowka 22.08.02, 08:21
      Jak juz wczesniej napomknalem, kazdy algorytm prowadzacy do rozwiazania tej
      zagadki jest cenny. Jak na razie mamy dwa. Pozwolcie, ze je przedstawie, choc
      na poczatku chcialbym przede wszystkim ustalic pewna prosta regule, zgodnie z
      ktora kazdemu wiezniowi na wstepie przypisany jest jeden "mandat",
      ktory "oddaje" on poprzez zapalona zarowke. Przejdzmy teraz do rozwiazan.

      Pierwszy algorytm przedstawiony przez Musztardka polega na jednym zliczajacym
      wiezniu. W tym rozwiazaniu kazdy wiezien posiadajacy mandat oddaje go wlaczajac
      swiatlo w swietlicy (o ile te swiatlo jest zgaszone). Natomiast wybrany
      arbitralnie lub w pewien scisle okreslony sposob jeden wiezien, zwany wiezniem
      zliczajacym (lub rachmistrzem albo testerem), zlicza te zapalone swiatla
      powiekszajac swoj licznik o jeden, za kazdym razem po tym gaszac swiatlo w
      swietlicy. Jesli licznik osiagnie 100, to wszyscy wiezniowie byli juz w
      swietlicy. Optymalizacja tej metody polega na wylonieniu wieznia zliczajacego
      poprzez pierwsza powtorna wizyte w swietlicy. W skrocie chodzi o to, ze dnia
      pierwszego pierwszy wiezien zapala swiatlo. Kazdy nastepny po nim wiezien
      zostawia swiatlo zapalone (odhaczajac sie, ze oddal swoj mandat), az do chwili,
      gdy po raz wtory ktorys z nich zawita w swietlicy. W tym momencie wiadomo, ze
      przed wiezniem, ktory jest powtornie w swietlicy bylo D-1 wiezniow, jacy
      oddali swoje "mandaty". Wiezien powtornie goszczacy w swietlicy staje sie wtedy
      rachmistrzem, ustawia swoj licznik na D-1, gasi swiatlo i dalej zliczanie toczy
      sie wg wyzej opisanych regul.

      Drugi algorytm, jaki mamy to rozwiazanie zaproponowane przez Mesquaki.
      Koncepcja oparta jest tutaj na zupelnie innym zalozeniu (o ile moja
      interpretacja jest wlasciwa :)). Owszem tez mamy tutaj wylonionego na samym
      poczatku rachmistrza dnia powtorego, czyli tak jak w wyzej opisany sposob:
      jesli dany wiezien wchodzi powtornie do swietlicy w dniu D, to ustawia licznik
      na D-1, gasi swiatlo. Teraz jesli pojawi sie znow w swietlicy w dniu D-1 modulo
      100*, zapala swiatlo, przekazuje w ten sposob zliczanie kolejnemu wiezniowi,
      jaki znajdzie sie w swietlicy dnia nastepnego. Jesli ten kolejny jeszcze nie
      oddal swojego mandatu, to zostawia swiatlo zapalone, dzieki czemu licznik znow
      rosnie, az do chwili gdy w swietlicy znajdzie sie ponownie jakis wiezien, ktory
      juz wczesniej oddal swoj mandat. W takim przypadku ten wlasnie wiezien
      przejmuje i ustawia licznik na D-1 (modulo 100), gasi swiatlo i czeka na
      kolejny dzien D-1 modulo 100, w jakim musi pojawic sie w swietlicy, by ponownie
      zapalic swiatlo, itd. Gdy licznik osiagnie wartosc 100, wiadomo ze wszyscy
      wiezniowie byli w swietlicy, a stanie sie tak w przypadku, gdy w dniu 99
      (modulo 100) wchodzi do swietlicy wiezien, ktory widzi zapalona zarowke, a ma
      jeszcze swoj nieoddany "mandat". Bardzo dlugotrwala procedura, choc rownie
      skuteczna. Jak tylko znajde troche wolnego czasu to chetnie zapuszcze symulacje
      i policze ile przecietnie trzeba na to dni (a moze ktos by mnie wyreczyl).

      Jest jeszcze wiele innych algorytmow, gorszych i lepszych, ale moim zdaniem
      wszystkie one sa rozna kompilacja wyzej przedstawionych dwoch. Dajcie swoje
      propozycje! No i oczywiscie przypominam, ze czekamy na najlepszy algorytm.

      CdM

      *Modulo 100 oznacza dzien po odjeciu calkowitej wielokrotnosci 100. Czyli: 101
      modulo 100=1, 254 modulo 100=54, a 19267 modulo 100=67, proste prawda?!
    • musztarda_po_obiedzie Strategia (multi)mandatów 22.08.02, 21:40
      (Ciekawe czy się zmieści w jednym poście... ? ;)

      Obiecałem przedstawienie nowej strategii - oto ona.
      Wybaczcie, jeśli coś będzie niezrozumiałe - ostatnie dni to nienajlepszy dla
      mnie okres na myślenie, a poza tym sama strategia jest okropnie pokrętna. W
      razie czego pytajcie, a będę uściślał.

      Do CdM: pozwolisz, że wykorzystam Twoją terminologię?? Słowo 'mandat' idealnie
      mi tu pasuje :)

      0. Każdy więzień zaczyna 'zabawę' (he-he) z jednym mandatem, symbolizującym
      wizytę w świetlicy.

      1. Zaczynamy tradycyjnie, od okresu testowego (35 dni), aby wyłonić
      rachmistrza. (Niezorientowani znajdą dokładny opis w postach powyżej).
      Rachmistrz odnotowuje D-2 mandatów (lub D-1 = 34, jeśli wszedł do świetlicy w
      35 dniu i światło było nadal zgaszone).

      2. Okres 1-mandatowy (M1): dni 36-300 (a potem po 100 dni)

      Więzień bez mandatu nic nie robi.
      Więzień posiadający mandat, który zastanie zgaszone światło, zapala je (oddaje
      mandat).
      Więzień z mandatem GASI ŚWIATŁO (=zabiera kolejny mandat !!). To oznacza, że
      taki więzień ma na koncie dwa mandaty.

      Oto pierwsza - najważniejsza - zmiana w dotychczasowym podejściu: inni
      więźniowie (nie tylko rachmistrz) mogą zbierać mandaty.

      2a. Więzień dnia 300 zabiera ewentualny mandat (= gasi zapalone światło) nawet
      jeśli sam na koncie nie ma żadnego.

      3. Okres 2-mandatowy (M2): dni 301-500 ( potem też po 200 dni)
      Każde zapalenie/zgaszenie światła warte jest 2 mandaty. A więc:
      Zapalają światło tylko ci, którzy mają na koncie 2 mandaty (albo ponad 5 :) -
      wyjaśnienie za chwilę). Gaszą tylko Ci, którzy mają 1, 2 lub 3 mandaty (lub
      rachmistrz). Oczywiście zapalający odejmują z konta 2 m., a gaszący dodają 2 m.

      3a. Więzień dnia 500 zabiera ewentualne mandaty (= gasi zapalone światło) nawet
      jeśli sam na koncie nie ma żadnego.

      4. Okres 3-mandatowy (M3): dni 501-800 (potem też po 300 dni)
      Każde zapalenie/zgaszenie światła warte jest 3 mandaty. A więc:
      Zapalają światło tylko ci, którzy mają na koncie 3 mandaty (albo ponad 5 :).
      Gaszą tylko Ci, którzy mają 1 lub 2 mandaty (lub rachmistrz). Zapalający
      odejmują 3 m., gaszący dodają 3 m.

      4a. Więzień dnia 800 zabiera ewentualne mandaty (= gasi zapalone światło) nawet
      jeśli sam na koncie nie ma żadnego.

      5. Okres 4-mandatowy (M4): dni 801-1300 (potem też po 500 dni)
      Analogicznie, tyle że światło warte jest 4 mandaty. Gaszą tylko Ci, którzy mają
      1 mandat (lub rachmistrz).

      5a. dzień 1300 - analogicznie dla dni granicznych.

      6. Okres 5-mandatowy (M5): dni 1301-1900 (potem też po 600 dni)
      Analogicznie, tyle że światło warte jest 5 mandaty. Gasi tylko rachmistrz.

      6a. dzień 1900 - analogicznie dla dni granicznych.

      Znowu wyjaśnienie: skąd bierze się więcej niż 5 mandatów u jednego więźnia?? Z
      sytuacji, gdy miał już coś na moncie i w dniu granicznym przyszło mu gasić
      światło.

      Dalsze postępowanie:
      powtarzamy cykl 3 - 6a dwukrotnie (dni 1901 - 3500 i 3501 - 5100).

      Jeśli rachmistrz nie doliczył jeszcze do 99, to od tego momentu wykonujemy cykl
      2 - 6a (uwaga, w tych cyklach okres M1 to 100 dni)

      Dzień, w którym rachmistrz ma na koncie 99 mandatów, jest dniem, w którym można
      zameldować komplet gości na świetlicy.
      ----------------------------------------------------------------------------

      Uffffff. Bardzo pokrętne, co? A teraz ocena skuteczności:

      Symulacja komputerowa (300.000 losowych układów) dała SCO = 5413 dni. (dla
      zainteresowanych: najszybszy układ miał 1723 dni, najwolniejszy - 51078 :)

      W porównaniu z SCO dla 'ruchomego testera' (9317), poprawa jest znacząca,
      prawda? (wiem, wiem, Car de Mon powie: tak-tak, ale NIE OPTYMALNA :[)

      Pozdrawiam,
      Musztardek :)
      • musztarda_po_obiedzie Re: Strategia (multi)mandatów 22.08.02, 21:54
        Zanim pojawi się fala krytyki i pytań, napiszę od razu:

        Długości okresów M1, M2, M3, M4, M5 są wynikiem prób i błędów. Nie twierdzę, że
        są one optymalne. Tyle że inne długości, które testowałem, dają gorsze wyniki.

        Dłuższe SCO wychodzą również gdy zastosuje się wersję skróconą (bez okresu M5)
        lub rozszerzoną (+ okres M6).

        Acha, i jeszcze jedno: Nie będę chyba drążył tej ścieżki dalej - Chyba, że ktoś
        podsunie pomysł, jak to usprawnić. Ale mnie już chodzi po głowie metoda
        zupełnie inna ;-p. Może jeszcze uda się skrócić bidulom czas spędzony w
        więzieniu?

        Pozdrawiam,
        Musztardek :)
        • cardemon Re: Strategia (multi)mandatów 22.08.02, 23:42
          musztarda_po_obiedzie napisał:

          > Zanim pojawi się fala krytyki i pytań, napiszę od razu:
          > Długości okresów M1, M2, M3, M4, M5 są wynikiem prób i błędów. Nie twierdzę,
          > że są one optymalne. Tyle że inne długości, które testowałem, dają gorsze
          > wyniki.

          Napisalem juz to wyzej. Mozna to troche usprawnic, ale to tylko kosmmetyka.
          Najwazniejsza jest sama idea!

          > Acha, i jeszcze jedno: Nie będę chyba drążył tej ścieżki dalej - Chyba, że
          > ktoś podsunie pomysł, jak to usprawnić. Ale mnie już chodzi po głowie metoda
          > zupełnie inna ;-p. Może jeszcze uda się skrócić bidulom czas spędzony w
          > więzieniu?

          No to teraz, zes mnie zastrzelil!!! :o
          Coz, to juz taka tradycja, ze Cardemon zamieszcza zagadke, a rozwiazanie jakie
          posiada, jest gorsze od optymalnego. ;)
          Ale nalezy sie z tego tylko cieszyc, bo swiadczy to bardzo dobrze o
          uczestnikach tego forum. :)

          pozdr. CdM
      • cardemon Re: Strategia (multi)mandatów 22.08.02, 23:35
        musztarda_po_obiedzie napisał:


        > Obiecałem przedstawienie nowej strategii - oto ona.
        (...)
        (...)

        > Symulacja komputerowa (300.000 losowych układów) dała SCO = 5413 dni. (dla
        > zainteresowanych: najszybszy układ miał 1723 dni, najwolniejszy - 51078 :)
        >
        > W porównaniu z SCO dla 'ruchomego testera' (9317), poprawa jest znacząca,
        > prawda? (wiem, wiem, Car de Mon powie: tak-tak, ale NIE OPTYMALNA :[)

        Swietnie! Brawo! Strategia moim zdaniem optymalna. Natomiast oczywiscie
        pewnego "dostrojenia" (chyba wlasnie tylko poprzez symulacje komputerowa)
        wymaga okreslenie ilu "mandatowe" maja byc poszczegolne okresy zliczajace(Ty
        wybrales 1,2,3,4,5,1-mandatowe, ale mozna inaczej), oraz ile dni przeznaczyc na
        kazdy okres zliczania, by osiagnac jak najleszy koncowy efekt, czyli jak
        najkrotszy czas do uwolnienia wiezniow. Mnie na razie wychodzi cos kolo 4800
        dni.

        Jeszcze raz gratuluje rozwiazania!

        pzdr. CdM

        • musztarda_po_obiedzie Re: Strategia (multi)mandatów 23.08.02, 22:25
          Wróciłem do domu umęczony okrutnie, więc dziś tylko info, a jutro szczegóły:

          cardemon napisał:

          > Natomiast oczywiscie
          > pewnego "dostrojenia" (chyba wlasnie tylko poprzez symulacje komputerowa)
          > wymaga okreslenie ilu "mandatowe" maja byc poszczegolne okresy zliczajace(Ty
          > wybrales 1,2,3,4,5,1-mandatowe, ale mozna inaczej)

          Owszem - lepiej wybrać okresy M1, M2, M4 i M8.

          > oraz ile dni przeznaczyc na kazdy okres zliczania, by osiagnac jak najleszy
          > koncowy efekt, czyli jak
          > najkrotszy czas do uwolnienia wiezniow. Mnie na razie wychodzi cos kolo 4800
          > dni.

          Długości poszczególnych okresów też pozmieniałem. Wynik: 4895.

          Szczegóły jutro.

          Btw, całkiem nowa strategia, o której wspominałem, okazała się niewypałem :(

          pozdrawiam,
          Musztardek :)
          • musztarda_po_obiedzie Re: Strategia (multi)mandatów 24.08.02, 08:52
            Rzeczywiście można było znacznie usprawnić strategię wielu mandatów.

            Samą ideę już przedstawiałem, więc teraz zajmę się tylko konkretami.

            Wersja 1

            Rachmistrzem zostaje wybrany jeden z więźniów jeszcze przed 'zabawą' (losowo??;)

            Cykl okresów:
            ------> M1 (200 dni) - M2 (300) - M4 (300) - M8 (400) ---->
            (cyfra przy M oznacza liczbę mandatów oddawanych/zbieranych poprzez
            zapalenie/zgaszenie żarówki)

            Szczegóły (ważne!)
            W okresie M1 zabrać mandat może tylko więzień z 1 mandatem lub Rachmistrz (RM),
            zostawić zaś wszyscy, którzy mają jakiś mandat, oprócz Rachmistrza (RM) i
            więźniów z 2, 4 lub 8 mandatami.

            Analogicznie:
            W okresie M2 - zbiera więzień z 2 mandatami lub RM; oddaje każdy z min. 2
            mandatami, oprócz RM i więźniów z 4 lub 8 mandatami.
            W okresie M4 - zbiera więzień z 4 mandatami lub RM; oddaje każdy z min. 4
            mandatami, oprócz RM i więźniów z 8 mandatami.
            W okresie M8 - zbiera wyłącznie RM; oddaje tylko ten, który ma min. 8 mandatów.

            I jeszcze jedno: W ostatnim dniu okresu M1, jeśli więzień zobaczy zapalone
            światło (warte 1 mandat), a sam ma na koncie jakieś mandaty, pozostawia żarówkę
            zapaloną, jednocześnie odliczając 1 mandat ze swojego konta (bo od tej pory
            żarówka jest warta 2 mandaty). To takie małe usprawnienie. Co dziwne,
            zapomniałem o tym przy innych dniach granicznych :( Może jeszcze poprawię
            program i trochę skrócę SCO??

            Wyniki (220.000 prób):
            SCO = 4895 dni (najszybciej 1978; najwolniej 16999)
            ---------------------------------------------------------------------------

            Wersja 2.

            Wersję 1 przygotowywałem bez okresu testowego. Potem pierwsze 35 dni zamieniłem
            na standardowy okres testowy (pierwsza rewizyta oznacza RM). Tak więc w
            pierwszym cyklu okres M1 wynosi tylko 165 dni, a potem już normalnie, czyli 200.

            Wyniki (215.000 prób):
            SCO = 4669 dni (najszybciej 1921; najwolniej 18175)
            ----------------------------------------------------------------------------

            Wersja 3.
            Baton sugerował skrócenie okresu testowego - skróciłem go do 30 dni.

            Wyniki (280.000 prób):
            SCO = 4660 dni (najszybciej 1912; najwolniej 21645)
            ----------------------------------------------------------------------------

            Wersja 4.
            Zauważyłem, że w wielu układach RM zebrał wszystkie mandaty oprócz jednego, i
            bardzo długo trwało, zanim trafił na ten jeden brakujący (bo to się może
            zdarzyć tylko w okresie M1). Stąd mała poprawka, która okazała się dość
            skuteczna:

            Jeśli w okresie M1 do świetlicy wejdzie RM i światło jest zgaszone, a RM ma na
            koncie parzystą liczbę mandatów (nie licząc siebie!), to ZOSTAWIA jeden mandat
            (czyli zapala światło). Tym samym daje szansę więźniowi z jednym mandatem na
            zwiększenie konta do 2 (a dwójkę łatwiej trafić, bo M2 trwa 300 dni). Efekt
            jest niezły:

            Wyniki (260.000 prób):
            SCO = 4621 dni (najszybciej 2044; najwolniej 17201)
            --------------

            I to na razie najlepszy wynik. Być może można jeszcze skrócić nieco okres
            testowy, zastosować poprawkę Batona dla ostatniego dnia testowego i poprawkę
            dla dni granicznych M2/M4 i M4/M8. Ile oszczędności to przyniesie? Nie wiem,
            ale chyba nie za wiele. Mimo to sprawdzę.

            Acha, jeśli ktoś ma jeszcze pomysł na usprawnienie, to piszcie - wykorzystam co
            się tylko da :)

            Pozdrawiam,
            Musztardek :)

            • cardemon W odpowiedzi MRe: Strategia (multi)mandatów 25.08.02, 03:58
              Moj algorytm jest bardzo zblizony do Twojego, tzn. tez przyjalem okresy
              zliczania kolejno 1,2,4,8,1 mandatow. Nawet zastanawialem sie nad 1,2,4,8,2,1,
              ale bez wiekszych sukcesow...
              Jak sam widzisz calosc koncepcji zasadza sie teraz na tym by
              odpowiednio "dostroic" poszczegolne okresy zliczen. Mozna rowniez stosowac
              rozne "triki", co tez sam robisz.

              W chwili obecnej natomiast ugrzezlem beznadziejnie w pisaniu programu, ktory
              by wyszukiwal sam najoptymalniejsze wartosci omawianych parametrow. Chyba
              jednak wroce do "recznego strojenia" i jak tylko zbiore odpowiednia ilosc
              danych to je tu przedstawie.

              Mam tez pewna ciekawostke. Pisalem wyzej, ze prawdopodobienstwo zdarzenia, ze w
              ciagu stu pierwszych dni trafi do swietlicy stu roznych wiezniow jest rowne
              100!/100^100 (sto silnia dzielone przez 100 do potegi setnej), co jest szansą
              zdecydowanie mniejszą niz wyrzucenie pod rzad stu reszek w rzucie moneta.
              Okazuje sie, ze nie pomylilem sie, bowiem pierwsze prawdopodobienstwo jest rowne
              w przyblizeniu 1/10^42 (jeden dzielone przez 10 do potegi 42), a drugie
              1/10^30, wyrzucenie 50 razy pod rzad szostki w rzucie kostka to 1/10^39,
              trafienie szostki w totolotku to 1/10^7 (wszystkie liczby sa podane z
              przyblizeniem). :)

              Pozdrawiam, CdM
              • cardemon W odpowiedzi MRe: Strategia (multi)mandatów 25.08.02, 05:25
                Jak juz sie bawic w prawdopodobienstwa, to jeszcze jedno na koniec.
                Prawdopodobienstwo, ze pojdziemy z jedna zlotowka do kasyna i pomnozymy ja w
                ruletce w czterech obstawieniach do 1.5 mln zl wynosi okolo 1/10^6. Okazuje sie
                wiec, ze bardziej oplaca sie pojsc do kasyna i cztery razy pod rzad postawic na
                zwycieska liczbe (za kazdym razem obstawiajac cala kwote uprzednio wygraną),
                niz grac w toto-lotka... :)))
                • cardemon Do Musztardka - Re: Strategia (multi)mandatów 26.08.02, 04:41
                  To jeszcze raz ja. Tak jak wczesniej napisalem, zrezygnowalem z komputerowego
                  zestrojenia okresow zliczen i zabralem sie za reczne dobieranie liczb. No i
                  cale szczescie! W tym komputerowym algorytmie juz sie uwiklalem na dobre, a i
                  tak trwaloby to cale lata, zanim komputer dobralby optymalne parametry.
                  Tak wiec moj komp teraz caly czas chodzi i po moim recznym wprowadzeniu danych
                  wylicza te przecietne ilosci dni potrzebne do uwolnienia wiezniow. Ograniczylem
                  sie do 10 tys. prob, bo inaczej rzeczywiscie trwaloby to jeszcze z miesiac, a
                  wyniki po 10 tys. symulacji sa moim zdaniem calkiem miarodajne. Jak juz wyzej
                  napisalem, przyjalem podobnie jak Ty okresy zliczen 1,2,4,8,1 mandatowe ale w
                  jednym cyklu (!), i musze Ci powiedziec, ze udalo mi sie zejsc jak na razie do
                  okolo 4100 dni (wartosc przecietna z 10 tys. zliczen).
                  Mam tez do Ciebie prosbe, bys zamiescil te strategię, w ktorej pokladales takie
                  nadzieje. Domyslam sie, ze jest ona typu Modulo 100. Ja tez mam jedna taka w
                  zanadrzu i chcialbym na koniec tego watku zamiesic wszystko, co tu sie znalazlo
                  z odpowiednimi obliczeniami.

                  pzdr. CdM
                  • musztardek Od Musztardka - Re: Strategia (multi)mandatów 26.08.02, 07:15
                    tak, tak, to ja - skróciłem sobie trochę adres :)

                    CdM, Twoja wieść o przekroczeniu bariery 4000 dni jest imponująca! Ale nie
                    dziwi mnie, ponieważ rzeczywiście manipulowanie długościami poszczególnych
                    okresów daje dosyć duże możliwości. Ja zbiłem swój wynik do 4480 dni.

                    Niestety, nie mogę już spędzać tyle czasu nad modyfikacjami długości okresów,
                    co do tej pory, z jednego prostego powodu - skończyły mi się wakacje :(
                    (Wiem, jeszcze trwają, ale tylko dla uczniów - a ktoś musi w końcu przygotować
                    szkołę do 2 września, prawda? :) Dziś mamy już zgrupowanie; z pewnością czasu
                    na zabawę żarówką będę miał znacznie mniej).

                    Co do strategii-niewypału:
                    Pomyślałem, żeby na początku zastosować kilka kolejnych okresów testowych. W
                    pierwszym - najdłuższym, np. 20 dni - wybierany byłby rachmistrz, natomiast
                    kilka kolejnych, krótszych, miałoby za zadanie szybciej pozbierać pojedyncze
                    mandaty i zbić je w grupy. Niestety, takie okresy testowe (nawet krótkie, 6-, 5-
                    , czy 4-dniowe) zostają szybko przerwane przez więźniów, którzy zostawili swój
                    mandat już w poprzednim okresie. Pewne nadzieje dawały jeszcze takie okresy 4-
                    dniowe, ale korzyść wydawała się praktycznie żadna. Szybko ten pomysł
                    zarzuciłem.

                    To na razie tyle. Mój sprzęt nadal liczy różne okresy testowe, więc w razie
                    czego będę chwalił się wynikami :)

                    Pozdrawiam serdecznie,
                    Musztardek :)
                    • musztardek Od Musztardka - Re: Strategia (multi)mandatów 26.08.02, 19:54
                      Zacznę tak:

                      Wszedłem przed chwilą do pokoju, zaświeciłem światło i... spaliła się żarówka.
                      Znamienne, co?

                      Car de Mon, masz rację: Nie ma się co bawić w kilka cykli - trzeba huknąć raz,
                      a dobrze. Wydłużenie okresów w pierwszym cyklu, a pozostawienie krótszych w
                      dalszych cyklach (które mimo wszystko trzeba zostawić, bo nigdy nie ma
                      pewności, czy jeden cykl wystarczy) daje rewelacyjne rezultaty.

                      Mój ostatni wynik: 3850 dni.
                      Czy uda się pokonać barierę 10 lat?? Teraz taki posł zaczyna wyglądać realnie...

                      Pozdrawiam,
                      Musztardek
                      • cardemon Od Musztardka - Re: Strategia (multi)mandatów 27.08.02, 02:54
                        musztardek napisał:

                        > Mój ostatni wynik: 3850 dni.

                        No niesamowite!!! To zes huknął z grubej rury! Ja tu licze od tygodnia i ledwie
                        zszedlem ponizej 4000, a Ty tu 3850.
                        Wiesz, mam propozycje. Daj mi jakiekolwiek liczby i porownajmy obliczenia.
                        Zobaczymy w ten sposob, czy nasze symulacje dobrze chodza.
                        Ja sluze Ci moimi danymi:

                        1) 30 dni "poszukiwanie" rachmistrza, do 400 dnia zarowka wlaczona = 1 mandat,
                        od 401 do 1000 dnia zarowka = 2 mandaty, od 1001 do 1800 dnia zarowka = 4
                        mandaty, od 1801 do 3200 dnia zarowka = 8 mandatow, powyzej 3200 dnia zarowka =
                        1 mandat;
                        przecietna ilosc dni po 10 tys. symulacji = 4139

                        2) 30 dni "poszukiwanie" rachmistrza, do 400 dnia zarowka wlaczona = 1 mandat,
                        od 401 do 850 dnia zarowka = 2 mandaty, od 851 do 1600 dnia zarowka = 4
                        mandaty, od 1601 do 3000 dnia zarowka = 8 mandatow, powyzej 3000 dnia zarowka =
                        1 mandat;
                        przecietna ilosc dni po 10 tys. symulacji = 4056

                        3) 30 dni "poszukiwanie" rachmistrza, do 400 dnia zarowka wlaczona = 1 mandat,
                        od 401 do 900 dnia zarowka = 2 mandaty, od 901 do 1900 dnia zarowka = 4
                        mandaty, od 1901 do 3300 dnia zarowka = 8 mandatow, powyzej 3300 dnia zarowka =
                        1 mandat;
                        przecietna ilosc dni po 10 tys. symulacji = 4287

                        Kazda symulacja jest obarczona bledem nie wiekszym niz +-100 dni.

                        pzdr. CdM
                        • cardemon Od Musztardka - Re: Strategia (multi)mandatów 27.08.02, 04:24
                          Jeszcze drobiazg. Wprowadzilem Twoja poprawke do mojego algorytmu, tzn. w
                          ostatnim dniu okresu jedno-, dwu- i czteromandatowego, jeśli więzień zobaczy
                          zapalone światło, a sam ma 1, 2 lub 4 mandaty, to je "oddaje" i zostawia
                          zarowke zapalona. Niewiele to co prawda daje, ale zawsze cos mozna uszczknąć.

                          pzdr. CdM

                          PS. Nie moge zejsc ponizej 3900 dni. :(
                          • musztardek Od Musztardka - Re: Strategia (multi)mandatów 27.08.02, 07:45
                            OK, puszczę mój program z Twoimi długościami i zobaczymy, jak nam się pokrywają
                            wyniki.

                            A oto moje 'parametry':
                            Okres testowy - 20 dni.
                            M1: 21-700, M2: 701-1400, M4: 1401-2000, M8: 2001-3600
                            Potem M1: 200 dni, M2: 300 dni, M4: 300 dni, M8: 600 dni

                            (Na granicy dni więźniowie dopełniają mandaty do wyższej liczby, jeśli tylko
                            mogą).

                            Sprawdź, proszę, jak to będzie wyglądało u Ciebie - moja średnia schodzi ciut
                            poniżej 3850. Jeśli potwierdzisz, to mamy całkiem niezły wynik.

                            Generalnie, jedyne, czym można się jeszcze zająć, to przeanalizowanie, jakiej
                            długości powinny być te pierwsze okresy, żeby nie były za długie, a żeby
                            wyłapywały (niemal) wszystkie mandaty z danego przedziału. Robię
                            odpowiednie 'badania' - pewnie pochwalę się wieczorem, jeśli mi komputer
                            wyrzuci jakieś sensowne rezultaty.

                            No i ciekawi mnie jeszcze jedno - który ze sposobów jest w takim razie lepszy
                            na zebranie 'resztek' po pierwszym cyklu: Twój (tylko okres jednomandatowy),
                            czy mój (dalej cykle, ale z krótszymi okresami)??

                            Zjedziemy poniżej 10 lat, czy nie?? :)

                            Pozdrawiam,
                            Musztardek :)
    • mesquaki nagroda 26.08.02, 05:36
      Zaczynam się niepokoić o tę obiecaną nagrodę za najdłuższy algorytm. Czy aby na
      pewno nikt mi jej nie odbierze?
      W razie, gdyby poprzednia strategia z jakiegoś powodu się nie kwalifikowała,
      spieszę donieść, iż posiadam jeszcze gorszą.
      Jest genialnie prosta, piorunująco skuteczna i o absolutnie porażającym czasie
      trwania.
      Czas dzielimy na setki dni. Każdy więzień pojawiający się po raz pierwszy w
      świetlicy w danej setce zostawia po sobie zapaloną żarówkę. Pierwszy więzień,
      który pojawi się powtórnie, gasi żarówkę. Raz zgaszonej nie można już zapalić
      do końca danej setki. Jeśli więzień w dniu x-setnym zastał zapalone światło,
      idzie meldować.
      Jednym słowem, czekamy na taką setkę dni, w której w każdym dniu w świetlicy
      codziennie jest inny więzień.
      Czekamy spokojnie. Czasu mamy sporo.

      Pozostawiam Komisji pod rozwagę i łączę wyrazy szacunku
      mes
      • cardemon Re: nagroda 26.08.02, 05:47
        mesquaki napisała:

        > Zaczynam się niepokoić o tę obiecaną nagrodę za najdłuższy algorytm. Czy aby
        > na pewno nikt mi jej nie odbierze?
        > W razie, gdyby poprzednia strategia z jakiegoś powodu się nie kwalifikowała,
        > spieszę donieść, iż posiadam jeszcze gorszą. (...)

        Mes, nie obawiaj sie, komisja wszystko dokladnie rozpatrzy i nagrody
        przydzieli... :))))
        Jedna rzecz tylko jest niedopuszczalna w danej strategii. Nie mozesz zmusic
        pojedynczego wieznia, by robil jakies bzdury (np. wlaczal czy wylaczal swiatlo
        wg swego widzimisie). Oni musza dzialac wg z gory scisle okreslonego planu.

        W zasadzie to chcialem sobie juz na dzis dac spokoj z forum, ale wlasnie
        dostalem wynik z jednego obliczenia. Przelamalem bariere 4000 dni!!!! UFF!!!!
        To bylo cos!!!
        Licze dalej! Tzn. tak naprawde to moj komp liczy :(

        Pzdr. CdM
    • cardemon Kto da mniej - Re: 100 wiezniow i zarowka 29.08.02, 05:38
      Musztardek zaproponowal kolejno okresy zliczen:

      Wylonienie rachmistrza po gora 20 dniach, a nastepnie sygnalizowanie przez
      zapalona zarowke odpowiednio: 1 mandatu do 700 dnia, 2 mandatow do 1400 dnia,
      czterech do 2000 i osiem do 3600 dnia, 1 mandat po 3600 dniu. Wstawilem te dane
      i policzylem dla JEDNEGO cyklu. Wyszlo mi, ze srednio (z 10 tys. symulacji) po
      3780 dniach nastapi uwolnienie wiezniow. Jak na razie jest to wiec najlepszy
      wynik. Kto da mniej?

      CdM

      PS. Moj najlepszy rezultat jak do tej pory wynosil 3955 dni zliczony wg danych:
      20 dni wylonienie rachmistrza, M1 do 400, M2 do 850, M3 do 1400, M4 do 2800 dni.
      • cardemon Kto da mniej - Re: 100 wiezniow i zarowka 10.09.02, 22:37
        Przypominam, ze ta zagadka jeszcze nie doczekala sie ostatecznego rozwiazania.
        Czy ktos moze przedstawic rozwiazanie, ktore gwarantowaloby wiezniom
        oswobodzenie po mniej niz 10 latach? Moj najlepszy algorytm daje srednio jakies
        3760 dni tym wiezniom, by w calkowitej pewnosci mogli wyjsc na wolnosc. Ktos
        daje mniej?
        • kopperek Kto da mniej - Re: 100 wiezniow i zarowka 10.09.02, 22:44
          Nie śledzę tej zagadki zbyt dokładnie (po prostu ją sobie
          odpuściłem), ale jedno mnie zaintrygowało - faktycznie
          Twój algorytm daje całkowitą pewność???
          • kopperek Kto da mniej - Re: 100 wiezniow i zarowka 10.09.02, 22:59
            Nie no, głupie pytanie:) - o pewności w ogóle mowy być
            nie może.

            hej
            • cardemon Kto da mniej - Re: 100 wiezniow i zarowka 10.09.02, 23:01
              kopperek napisał:

              > Nie no, głupie pytanie:) - o pewności w ogóle mowy być
              > nie może.

              Absolutnie daje pewnosc. To z reszta jest jednym z warunkow zadania. (To znaczy
              pewnosc dotyczy uwolnienia, nie ilosci dni. :))

              pzdr. CdM
              • musztardek Do CdM: Kto da mniej - Re: 100 wiezniow i zarowka 11.09.02, 22:53
                Mała "łata" do ostatnio stosowanego przez nas algorytmu:

                Pierwszy więzień, który zajrzy do świetlicy po rachmistrzu (czyli gaszący za
                nim światło) dodaje sobie jeden mandat (czyli jeśli już tu był, to ma ponownie
                1, a jeśli nie, to 2). Rachmistrz natomiast zbiera pojedynczy mandat w okresie
                1-M tylko w przypadku, gdy ma ich nieparzystą liczbę (nie licząc swojego).
                Oczywiście musi tych mandatów zliczyć o 1 (ten dopisany) więcej.

                Co to daje? Ano to, że eliminujemy pozostanie jednego pojedynczego mandatu,
                który nie będzie miał 'pary' i który może zostać zebrany tylko przez
                rachmistrza. U mnie dało to zysk rzędu 40 dni (średnia spadła z 3830 do 3790).


                Jeśli to co opisałem, jest w miarę czytelne, to spróbuj zastosować to u siebie -
                powinno pomóc. Jeśli tak, to wynik będzie znów ciut lepszy...

                Pozdrawiam,
                Musztardek
Inne wątki na temat:

Nie pamiętasz hasła

lub ?

 

Nie masz jeszcze konta? Zarejestruj się

Nakarm Pajacyka