100 wiezniow i zarowka

[cardemon]

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

[reptar]

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]

Więźniów można brać wielokrotnie, tak?
Na przykład 1,5,5,3,5,67 ?

[reptar]

to nie moja zagadka, ale rozumiem, że tak. W przeciwnym razie wystarczyłoby
poczekać 100 dni...

[mesquaki]

No chyba, że niekoniecznie brano jednego dziennie - jedno z dwoch.

[cardemon]

Przypominam, ze wiezniowie brani sa ze swych cel losowo.

[cardemon]

Przypominam, ze kazdego jednego dnia, czyli codziennie, straznik kogos prowadzi
do swietlicy.

[mesquaki]

A ile więźniowie mają lat?
Statystycznie rzecz biorąc, po jakichś paru latach możn by było zaryzykować ;)

[ydorius]

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]

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]

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

Metoda dla mniejszej liczby więźniów

[reptar]

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]

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.

Brawo, musztarda_po_obiedzie!

[reptar]

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]

reptar napisał:

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

Czy na pewno skrócenie???

[reptar]

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]

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]

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]

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]

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]

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.

sorry m<p>o

[reptar]

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.

WD-2 i WD-3: dementi wyników symulacji

[musztarda_po_obiedzie]

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]

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]

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]

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]

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

JESTEM POD WRAŻENIEM

[reptar]

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]

> > 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]

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]

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]

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]

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]

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]

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]

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]

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]

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

[cardemon]

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]

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]

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]

??? 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]

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]

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

W ciemno po 10 latach (dla Mesquaki)

[musztarda_po_obiedzie]

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

Losowo znaczy losowo

[reptar]

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]

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]

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]

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]

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?

Takie tam dywagacje (prawie nie na temat)

[marchewa4]

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.

Przyznaję: bardzo cenne spostrzeżenie

[reptar]

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]

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]

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]

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]

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]

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 ;)

Strategia 'ruchomego testera' - podsumowanie

[musztarda_po_obiedzie]

'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]

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]

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]

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]

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?!

Strategia (multi)mandatów

[musztarda_po_obiedzie]

(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]

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]

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]

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]

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]

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 :)

W odpowiedzi MRe: Strategia (multi)mandatów

[cardemon]

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

W odpowiedzi MRe: Strategia (multi)mandatów

[cardemon]

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... :)))

Do Musztardka - Re: Strategia (multi)mandatów

[cardemon]

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

Od Musztardka - Re: Strategia (multi)mandatów

[musztardek]

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 :)

Od Musztardka - Re: Strategia (multi)mandatów

[musztardek]

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

Od Musztardka - Re: Strategia (multi)mandatów

[cardemon]

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

Od Musztardka - Re: Strategia (multi)mandatów

[cardemon]

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. :(

Od Musztardka - Re: Strategia (multi)mandatów

[musztardek]

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 :)

nagroda

[mesquaki]

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]

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

Kto da mniej - Re: 100 wiezniow i zarowka

[cardemon]

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.

Kto da mniej - Re: 100 wiezniow i zarowka

[cardemon]

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?

Kto da mniej - Re: 100 wiezniow i zarowka

[kopperek]

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ść???

Kto da mniej - Re: 100 wiezniow i zarowka

[kopperek]

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

hej

Kto da mniej - Re: 100 wiezniow i zarowka

[cardemon]

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

Do CdM: Kto da mniej - Re: 100 wiezniow i zarowka

[musztardek]

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