Problema prizonierilor – tema de gandire
by Mithrandir
(Pe langa faptul ca am sters deja odata pagina asta)
E din nou joi si la probleme lucram. Problema de saptamana trecuta nu a fost rezolvata satisfacator de nimeni asa ca voi da aici solutia. Din cauza orei intarziate voi spune numai ideea de rezolvare pe uncaz, celelalte urmand sa rezulte din demonstratia pentru care voi oferi punctele de saptamana trecuta daca va fi facuta pana pe 1 ianuarie. (Mai dau o sansa, asa de Craciun) . Solutia e urmatoarea: se ia maximul de pe fiecare coloana (unde sunt mai multe nu conteaza care – veti demonstra de ce) si se formeaza o alta matrice astfel: 0 unde nu este un maxim de coloana, 1 unde este maxim. Se obtine o matrice de permutare care va duce direct la ordinea evenimentelor. Pana pe 1 demonstrati ca este o solutie valida si ca daca am 2 maxime pe o coloana voi avea 2 maxime si pe alta coloana, pe aceleasi linii. Cine demonstreaza primeste pucntele de data trecuta.
Si acum problema: “Avem N prizonieri condamnati la moarte si care locuiesc intr-o inchisoare cu N camere, cate unul in camera, si un paznic glumet. El ii aduna pe toti intr-o zi si le spune “Exista o camera ce contine doar un bec si un intrerupator. In acea camera voi duce zilnic pe unul dintre voi ales la intamplare. In acea camera veti intra doar voi. Voi repeta acest procedeu pana cand cineva va spune “sunt sigur ca au fost toti prizonierii aici” Daca propozitia este adevarata, atunci va dau drumul la toti. Altfel, va execut pe loc. Aveti timp o ora sa va stabiliti strategia dupa care nu va veti mai intalni“. Se cere sa gasiti o strategie care va permite eliberarea prizonierilor (1 punct). NU se cere strategia optima dar cine o gaseste primeste 2 puncte (1 punct bonus).
Solutie exista, am aflat ieri.
Later edit: camera cu becul este a N+1-a camera.
Primul lucru care imi trece prin cap : prizonierul N1 intra in camera, aprinde becul, trage o linie pe perete, stinge lumina; preizonierul N2 intra, aprinde becul, trage o linie pe perete, stinge lumina etc. Daca Ni revinde in camera, nu va trage o linie pe perete. In momentul in care sunt n lini pe perete, prizonierul poate spune afirmatia.
Fara linii, utilizati doar becul:) (E o solutie totusi si asta, ai jumatate de punct :) )
Nu iti inteleg “late edit”-ul . Pai sunt doar N camere. Care e a N+1 -a ?Si mai am o intrebare… restul camerelor au becuri? Dar ferestre?
Sunt N camere pentru prizonieri, cu becuri si ferestre dar numai un singur prizonier sta in ele. Camera N+1 este camera in care merge fiecare prizonier si este acel bec de comunicatie. Becul din aceasta camera este singurul lor mod de a comunica
Trebuie sa admit k stiu problema(inclusiv solutia), asa k poate e incorect sa o postez, deoarece ar trebui sa dau si altora sansa sa se gandeasca. Tu decizi dak sa o postez sau nu:P
Am pornit de la ideea ca “primul ajunge de f multe ori in camera”, de suficiente ori cat sa fie martorul indirect al trecerii celorlalti pe acolo.
Inainte de a spune ce face el mai exact precizez ca toti ceilalti in afara de el au dreptul sa produca o modificare asupra becului o singura data(necontand dak fac lucrul asta la prima vizita in camera sau nu); ei trebuie doar sa il stinga(cei care il gasesc stins sau cei care au mai avut ocazia sa il stinga nu fac nimic).
So…..intra primul, aprinde becul,pleak….e posibil ca cineva sa il stinga pana la reintoarcerea sa in camera….dak il gaseste stins….e bine,il reaprinde…..dak il gaseste stins de N-1 ori e fbine,inseamna ca au trecut toti pe-acolo.:D
da eu vin mai tarziu cu rezolvarea ca acum amavut si eu parte de net. nu stiu daca se mai pune dar incerca e chiar la fel cu cea din fata mea deci nu mai are rost sa o scriu, mai bine dau copy-paste, acu e problema ta daca ma crezi sau nu.
Imparti timpul in intervale de N zile. Strategia fiecaruia e asa:
- daca ajunge in camera in ziua m*N+1, aprinde becul
- daca ajunge in camera pentru a doua sau a treia sau etc. oara in zilele de la m*N+2…m*N+N-1, stinge becul
- daca nu a mai fost in camera in ultimele N zile si ajunge in camera in ziua m*N si becul e aprins, zice ca e sigur ca toti au trecut prin camera.
Ma indoiesc ca e optima, dar functioneaza.
Ai ajuns cam tarziu cu solutia aici (concursul se terminase de saptamana trecuta). Faptul ca ai oferit o alta solutie este imbucurator, mai ales ca mi se pare ca asta ar fi solutia optima – nu am dus calculul pana la capat dar asa pare. Facand o medie intre 0 puncte (ca expirase perioada in care se accepta solutia) si 2 puncte (pentru solutia optima) reiese ca ai obtinut 1 punct. (In cazuri normale nu as fi facut medieri de astea…)
Nu e cea optima, sunt aproape convins. Aia de mai sus ii scoate din inchisoare pe astia prima data cand primul prizonier intra in camera dupa ce toti restul au intrat. In asta sansele sa intre in camera toti prizonierii in mod distinct in intervale fixe de zile sunt mult mai mici: de exemplu, cu patru prizonieri, A B C A B C D nu o sa ii scoata din inchisoare pentru ca nu a inceput ciclul la o zi multiplu de patru.
Deci, dami o jumate de punct.
Punctele astea, la care Carfur le schimbi in bani?
Jumatate de punct se rotunjeste oricum la un punct. Voi face un script si voi rula cateva simulari imediat.
Punctele nu se schimba in bani, la trei puncte iti ofer o bere (suc daca nu bei bere). Cu ocazia asta te vad si in realitate.
Am facut eu scriptul. Solutia mea nu e mai buna nici de la o posta. E de fapt cam de vreo 100 de ori mai proasta decat cealalta. 1/100 puncte rotunjite in sus la un punct?