Daj jos malo detalja. Da li svakog zatvorenika samo po jednom dovode? Dali svakog dana dovode po nekog ili se ne zna kada ce dovesti nekoga?

Vrlo interesantan zadatak. Ono što je iz prve očigledno je to da se rešavanje ovog zadataka svodi na samu konstrukciju strategije zatvorenika, odnosno šta će značiti 0, a šta 1 ...

Međutim, nisam siguran da je ovo originalni tekst zadatka. Ukoliko sam u pravu, dostavi nam originalnu verziju, kao da fale neki podaci, ili se ja tešim, jer trenutno ne vidim rešenje ...

Na primer, šta ako prođe toliko vremena da svi čuvari pocrkaju (jer nisu besmrtni kao zatvorenici), a još uvek nisu boravili svi zatvorenici u prostoriji. To znači da robijaši nisi ni imali priliku za puštanje. Znači, evo je odmah jedna nedefinisana situacija.

Dalje, čini mi se da i da uspemo da formiramo strategiju nekakvog brojanja, što još uvek ne vidim kako, opet, ko garantuje zatvorenicima da će se desiti takva situacija (da su svi boravili u prostoriji). Naime, može se desiti da postoji bar jedan koji nikad nije bio niti će u prostoriji, jer sama si rekla da bez pravila se biraju zatvorenici, to znači da se može birati i samo jedan non stop, ili recimo 2000 njih da se vrte, a jedan nikad ne itd itd ...

To pitanje je slično kao da imaš 2001 kuglicu u činiji i nasumice vadiš jednu, pa je vraćaš. Da li ćeš i kad osediš moći da se kladiš da si ih sve uzela ? Ja se ne bih kladio ...

Kad neki zatvorenik bude prvi put odveden u zajedničku prostoriju, ostavi prekidač u položaju 1. Svaki sledeći put kad ga odvedu tamo, ostavi 0 na prekidaču. Svaki zatvorenik pamti koliko je puta zatekao 1 na prekidaču kad je ušao u zajedničku prostoriju. Prvi koji izbroji 2000 jedinica, može da se javi čuvarima.

Kakvo je to resnje? Sta ako ih odvedu po redu, svi ce zateci samo po jednom jedinicu jer ce posle svi ostavljati nulu i tako nikada nece izaci.

A da probamo ovako:

Postoji jedan zatvorenik-brojač.

Kad zatvorenik-brojač uđe u sobu, ako zatekne 1 doda ga u svoj zbir pa postavi na 0, a ako zatekne 0 ništa ne radi.

Običan zatvorenik kad prvi put zatekne 0, okrene na 1. U svakom drugom slučaju, ništa ne dira.

Problem koji se javlja u ovom rešenju je početni položaj prekidača. Ako je to 1, brojač će izbrojati jednog zatvorenika manje. Deluje mi da je ovo problem za bilo kakvo rešenje, odnosno da se početni položaj mora definisati.

nisi razumeo,
ako prvo odvedu 1. zatvorenika pa 2. pa 3. .... 2000. pa 2001. svako (sem mozda 1. ) ce zateci prekidac na (I) E onda cuvari ponovo odvedu 1. zatvorenika koji ce sad da postavi prekidac na (O) jer je vec jedanput bio u zajednickoj prostoriji, zati cuvari odvedu 2. zatvorenika koji ce da zatekne (O) i tako ce da ostavi pa onda 3. ITD...
znaci svi zatvorenici mogu beskonacno puta otici u zajednicku prostoriju ali samo ce prvi put zateci (I) (sem mozda 1. zatvorenika)
capis.

Čekaj, to važi za prvo rešenje koje sam predložio. U ovom drugom, samo zatvorenik-brojač sme da okrene sa keca na nulu. Običan zatvorenik dira prekidač samo kad prvi put zatekne nulu (okrene na keca), ne pre, niti ikad posle.

Ovo drugo resenje je dobro! Svaka cast!

prvo reshenje ima manu -- ako odvedu nekog ('prvog') zatvorenika dva puta pre nego shto nekog ne odvedu ijedanput, onda to pada u vodu.

drugo reshenje ima slichnu manu -- isto tako ne znamo da li su neki zatvorenici bili po dva puta! medjutim to se da ispraviti: ako je neki zatvorenik po drugi put u zajednichkoj prostoriji, ne dira prekidach, tj. 0.

mada, i to ima manu: recimo da ulaze u prostoriju za redom dva zatvorenika, koja su oba po prvi put u prostoriji, recimo da dolaze odmah posle zatvorenika-brojacha. prvi cje da postavi prekidach na 1, drugi ga necje menjati, a sledecji recimo da je bash zatvorenik-brojach, koji cje dodati 1 na zbir i vratiti prekidach na 0... shta ako tog drugog zatvorenika nikad vishe ne dovedu u zajednichku prostoriju? onda se mora postaviti pitanje: da li zatvorenici vechno 'kruzhe' sa prebacivanjem u zajednichku prostoriju?

i pochetni polozhaj nije problem -- neka chekaju dok se ne izbroji jedan vishe, tj. 2002.

znachi, sa eliminisanim dosadashnjim problemima, reshenje bi moglo da glasi ovako:

1) zatvorenik-brojach: 1 sabira na zbir i stavlja prekidach u 0, ako zatekne 0, ne dira je.
2) obichan zatvorenik: ako zatekne 0 i ako je prvi put u prostoriji, stavlja prekidach u 1, u drugim sluchajevima ne dira prekidach.

kao shto je rekao Časlav, što je, po meni, ujedno i tačan odgovor.

Zbog ovoga je u zadatku i rečeno da ima beskonačno vremena. Pošto stražari nasumično odvode zatvorenike u zajedničku prostoriju, pre ili kasnije će svakog odvesti dovoljan broj puta da bi brojač mogao da ih prebroji.

To može ako je prekidač u početku zaista bio na kecu. Ako nije, brojač može da izbroji samo do 2001, nikad neće dobiti 2002. kec.

ako je povremeno bez ikakvih pravila to neznaci da ce svako od zatvorenika ikada otici u zajednicku prostoriju, ali ako se i doda uslov da svaki od zatvorenika mora barem jedanput da poseti tu zajednicku sobu i dalje nemamo resenje jer sta ako zatvorenika-brojeca odvedu samo jedanput onda on nece biti u mogucnosti da izbroji do 2001!
zar ne?


.

Ama poenta je da čuvari moraju da vode zatvorenike u zajedničku prostoriju slučajnim izborom, sve drugo je varanje sa njihove strane ;)

pod pretpostavkom da zatvorenici vide svetlo

2001 zatvorenik se ne racuna, ovih 2000 podele se u 1000 grupa po 2 ili u 2 grupe po 1000 nuje vazno
jedan je 1<pali svetlo> drugi 0 <gasi svetlo>

ulazi prvi 1 pali svetlo ulazi sledeci 0 gasi svetlo = jedna promena
ako drugi udje 1 ugasi pa upali svetlo znaci jedna promena nije vazno da li kojim redom ulaze jer ih ima jednak broj pa ce biti isto promena
vazno je da ovi sto po drugi ili treci... put ulaze nista ne diraju nista
svi zatvorenici prate promene nakon 1000 promena bilo ih je 2000 i sledeci je 2001

Pocetni polozaj prkidaca ne mora biti definisan. Resenje bi trebalo da glasi ovako. Izabre se jedan zatvorenik kome se dodeli cudno ime "Brojac" :) i njegova uloga je da kada god zatekne prekidac u stanju 1 doda to svom zbiru i promeni stanje prekidaca sa 1 na 0. Uloga ostalih zatvorenika je sledeca. Kada udju u sobu prvi put i zateknu 0 na prekidacu to promene na 1. Kada udju u sobu po drugi put i zateknu 0 na prekidacu opet je promene na 1. U svim ostalim slucajevima (tj. kada je prekidac na 1 ili kada zatvonrik udje po treci, cetvrti, peti put u prostoriju kada je prekidac na 0) ne radi nista. Kada zatvorenik-brojac preborji 4000 jedinica na prekidacu tada ce biti siguran da su svi posetili prostoriju i to moze da prijavi.

Dokaz o njegovoj sigurnosti je vise nego jednostavan. Recimo da je u pocetku prekidac bio na 0, i da je brojac-zatvorenik izbrojao 4000, tada je svako od zatvorenika bio najmanje dva puta u prostoriji. Ako je prekidac bio na 1 onda su zatvorenici napravili 3999 jedinica, sto opet znaci da je 1999 zatvorenika bilo najmanje dva puta i da je jedan bio najmanje jednom.

Vrlo interesantna pitalica.

Pozdravi,

Znate sta ljudi? Svaka vam cast svima sto RAZMISLJATE bez obzira na moguce greske i propuste, ali vi razmisljate dublje i prvi put nailazim na neku tako pametnu stranicu poput ove! Bas sam se iznenadila da ima ljudi poput mene (koji vole korisiti glavu za jos nesto osim sminke i frizure)! Evo da i ja pokusam rijesiti zadatak… evo recimo, ja od pocetka mislim DA LI ONI VIDE KADA SE PALI SVJETLO jer onda bi to bilo vrlo lako. Kad udjes prvi put, upalis svjetlo i ugasis ga… inace ga ne palis… i tako svaki put, a ostali broje koliko je puta svjetlo bilo upaljeno… i to je to.
A ima jos par upitnih stvari, recimo DA LI ONI I IZLAZE IZ ZAJEDNICKE PROSTORIJE sto nije navedeno… Dakle, onaj koji prvi udje, broji…
Takodjer mogu nagovoriti nekog cuvara da im signalizira… sto naravno nije rjesenje ovog problema iako znamo da medju tih «dovoljno» cuvara mora biti BAREM 50% koji bi mater svoju prodali… J
Nisam upoznata s prekidacima previse jer sam tek maturantica u gimnaziji (buduca arhitektica), ali mislim da bi nakon toliko paljenja i gasenja svjetlo pregorilo (kao moja lampa!!!)…
Nadalje, vjerujem da bi mogli na neki nacin komunicirati putem binarnog sustava (znamenke 0 i 1), nisam sigurna kako, ali me na to asocirao zadatak dok sam ga citala prvi put. Ja sam ucila samo osnovu binarnog sustava, pa molim nekoga pametnijeg i vise informiranog da malo promisli o tome…
E onda, nije uracunato i to da zatvorenici IMAJU jos jedan nacin komunikacije… oni u tom «beskonacnom zivotu» moraju nesto jesti. Mogu ostacima hrane ostaviti otisak prsta kada ulaze prvi put…
A imaju i drugi nacin komunikacije… ostave jednu dlaku kose kad udju prvi put (mana je u tome sto netko moze biti potpuno celav!)… dobro ovo rjesenje je bila mala sala.
Uuuuh… celija SAMICA? Znaci, ne vide svjetlo! Hmmmm… Ne mogu ostavljati pisane ili slicne znakova? Hmmmm…

Evo resenja!!!

Zatvorenici odrede jednog od njih koji ce brojati ( u nastavku BROJAC)!

Kada bilo koji zatvorenik (u nastavku BKZ) prvi put udje u celiju i zatekne iskljucen prekidac postavice prekidac na 1 ( ukljucice ga).

Kada BKZ udje u celiju i naidje na ukljucen prekidac, nece menjati stanje prekidaca.

Kada BROJAC udje u celiju i zatekne ukljucen prekidac, povecace ukupan broj zatvorenika koji su bili u celiji ( na pocetku je taj broj 0 ) i iskljucice prekidac ( postavice ga na 0 ).

Kada BROJAC izbroji 2000 ukljucenih prekidaca bice siguran da su svi zatvorenici bar jednom bili u celiji i to je kraj!!!

Naravno pretpostavka je da zatvorenici znaju koje je pocetno stanje prekidaca ( ako je pocetno stanje prekidaca 1 koristite obrnutu logiku odnosno sve nule zamenite jedinicama i sve jedinice zamenite nulama ). Ovo nije navedeno u tekstu zadatka ali i bez toga moje resenje moze pogresiti za najvise jednog zatvorenika.