Bine aţi venit pe Scientia QA!
Pentru a putea publica întrebări şi răspunsuri, trebuie să vă înregistraţi.
Atenţie! Este posibil ca e-mailul de confirmare a înregistrării să intre în Spam.
Pune o întrebare

Newsletter


3.5k intrebari

6.7k raspunsuri

15.2k comentarii

2.2k utilizatori

3 plusuri 0 minusuri
613 vizualizari

De data asta sunt 9 prizonieri (logicieni, desigur) aflați toți într-o sală din palatul unui tiran din Grecia Antică.

Despoticul rege intră în încăpere și le spune:

" Vă voi încarcera separat, pe fiecare în câte o celulă, fără să vă las nicio posibilitate de a comunica între voi.

Voi scrie apoi pe o tăbliță numele fiecăruia dintre voi, asociind apoi fiecăruia un nume al uneia dintre cele Nouă Muze: Calliope, Clio, Erato, Euterpe, Melpomene, Polyhymnia, Terpsichora, Thalia și Urania.

Cum nu toate Muzele îmi plac, numele unora din ele nu va fi atribuit niciunuia dintre voi, astfel că mai mulți vor putea primi numele aceleiași Muze (dintre cele pe care le iubesc). Doar eu știu cum arată în final tăblița cu tabelul astfel întocmit.

Voi intra apoi pe rând în fiecare celulă și voi comunica prizonierului aflat în ea, ce Muză a fost atribuită fiecăruia dintre ceilalți 8 tovarăși. Îi voi cere apoi să spună care Muză i-a fost atribuită lui.

Dacă măcar unul dintre voi va indica fără greșeală Muza cu care a fost asociat, vă voi elibera pe toți. Dacă nu... nu.

Aveți la dispoziție atâta timp cât are nevoie umbra gnomonului să parcurgă a douăsprezecea parte a circumferinței, pentru a gândi o strategie care să vă garanteze că nu voia avea încotro și va trebui să vă eliberez."

Poate cineva să-i ajute pe prizonieri cu o strategie, asfel încât să-și redobândească libertatea?

Senior (6.6k puncte) in categoria Matematica
0 0
Am și eu o soluție frumoasă, dar trebuie să mă bazez pe faptul că deținuții își știu ordinea în care vor fi întrebați.

Adică deținutul cu numărul 6 va fi al 6-lea întrebat ce muză i-a fost atribuită?

Principiul de deducere ar fi următorul.

Deținutul cu numărul x, din cei 9 firește, ia în calcul doar faptul că ceilalți x-1 deținuți întrebați înaintea lui au răspuns greșit. Altfel, dacă unul dintre cei întrebați înaintea lui a răspuns corect, atunci atât el, cât și ceilalți vor fi salvați.

Deci, fiecare deținut știe câți au fost întrebați înaintea lui ?
0 0
Nu, nu are această informație. Știe că e al x-lea, unde x poate avea oricare una din 9 valori ordonate crescător. Mai mult, tiranul nu e obligat nici măcar să păstreze aceeași ordine aunci când comunică fiecăruia ce Muze au fost atribuite celorlalți 8.
0 0

Da, de fapt cred că nu are atât de multă importanță.

Ideea este că atât timp cât au la dispoziție să-și construiască strategia, ei pot stabili de comun acord un set de reguli pe care să le respecte fiecare dintre ei.

Spre exemplu, dacă ei stabilesc înainte de începe jocul ca fiecare să ordoneze muzele în ordine alfabetică și să spună numele muzei lipsă cea mai apropiată de partea de început pare că ajung să fie eliberați.

Spre exemplu, numerotând muzele aranjate în ordine alfabetică cu numere de la 1 la 9, dacă tiranului nu-i place muza 9 și o alege ca dublură pe cea cu numărul 8, unui prizonier căruia i se va spune muzele cu numerele 1, 2, 3, 4, 5, 6, 7, 8 va stabili că cel puțin unul întrebat anterior a răspuns corect.

E mai dificil pentru generalizarea problemei.

0 0
Soluția mea nu este corectă și într-adevăr, problema este foarte fumoasă. Dacă Puiu mai are răbdare aș mai avea o singură întrebare.

Problema are o rezolvare pur logică sau pot fi formulate răspunsuri ce-l pun pe tiran în dilemă ?

De genul prizonierul x răspunde: Muza mea este cea pe care a spus-o prizonierul y .

Pentru că așa prizonierul y alege o variantă din cele care i s-au spus, chiar dacă greșește știe sigur că dacă toți vor da răspunsul de mai sus unul dintre ei va răspunde corect.
0 0

Iertați-mă, CiprianM, dar abia acum am văzut întrebarea dumneavoastră. V-au "luat fața" răspunsul și comentariile lui Bogdan Sava, cu care am purtat un dialog care cred că, măcar parțial, răspunde și întrebării pe care mi-o puneți.

Strategia nu se bazează pe factori psihologici, common knowledge, calambururi, ambiguități sau șmecherii. Prizonierii trebuie să caute o cale prin care să se asigure că măcar unul din ei răspunde corect, fără echivoc.Tipul de abordare a lui zec e cel corect, din păcate el nu a plecat pe o direcție utilă. Așa e, problema e frumoasă, iar mie îmi place și pentru că demonstrează puterea grupului într-o situație nerezolvabilă individual de niciunul din membrii săi. E o contribuție a matematicii la evidențierea necesității unei etici a cooperării inteligente și oneste. Iar așa ceva mi se pare o rara avis în societatea umană a prezentului.

3 Raspunsuri

2 plusuri 0 minusuri
 
Cel mai bun raspuns

Deci mai terminat cu problema asta  dar intr-un final am gasit o solutie .

O sa pastrez notatiile prizonierilor si muzelor cu numerele de la 1 la 9 si corespondenta prizonier-muza cu functia g.

 Definesc functia

 f(k)=\sum_{i=1;i\neq k}^{9}(i-g(i)) mod(9)

Sa presupunem prin absurd ca f(k)\neq g(k)  oricare ar fi k

Adica 

 f(k)=\sum_{i=1;i\neq k}^{9}(i-g(i))\neq g(k)

De unde obtinem 

\sum_{i=1}^{9}g(i)\neq \sum_{i=1;i\neq k}^{9}i=S-k

unde S este suma de la 1 la 9 adica 45 si egalitatea de mai sus e in continuare modulo 9. cum sumele din dreapta vor lua toate valorile de la 1 la 9(care teoretic e zero mod 9 ) si ceea din stanga e aceeasi mereu am obtine o contradictie intrucat nu putem avea decat o valoare de la 1 la 9 pentru suma din stanga..De remarcat ca nu am avut nevoie de ipoteza muzelor neiubite.

Edit.Deci fiecare prizonieri alege valoarea sumei diferentelor dintre ordinul prizonierului si ordinul muzei corespondente care va fi considerata ca valoare rest modulo 9 si pentru ca in notatiile celelalte nu am folosit 0 o sa consideram 0 ca fiind 9.

De exemplu daca rezltatul ne da -3 el este echivalent cu 6=-3+9 etc.

Experimentat (2.3k puncte)
selectat de
0 0

Da, asta e ideea. Feliciări! 

O notare a prizonierilor și a Muzelor de la 0 la 8 v-ar fi făcut viața mai ușoară și răspunsul mai simplu. 

Iată cum formulez eu răspunsul, care e fundamental identic cu al dumneavoastră, dar cred că e mai ușor de înțeles pentru mai mulți cititori:

Notăm prizonierii cu P0, P1,...,Pși Muzele cu M0 = 0, M= 1,...,M= 8.

Muzele repartizate prizonierilor, însumate, formează un total pe care nu-l cunoaște decât tiranul. Ceea ce știu însă prizonierii este că acel total general ia cu necesitate una și numai una din valorile 0 mod 9 sau 1 mod 9 sau 2 mod 9 sau..... sau 8 mod 9.

La totalul parțial primit, P0 va aduna atât cât e nevoie pentru a obține un total general T= 0 mod 9, numărul adunat fiind muza pe care o indică.

La fel, P1 va aduna la totalul lui parțial ceea ce lipsește pentru ca totalul general să fie T= 1 mod 9. Și tot așa până la P8, care va aduna la totalul parțial primit atât cât lipsește ca totalul general să fie T= 8 mod 9.

Dintre totalurile generale calculate astfel, unul și numai unul, notat cu Ti, este cel adevărat. La acest total va ajunge numai prizonierul Pi, care va aduna numărul lipsă, adică cel corespunzător Muzei sale, pentru a obțineT= i mod 9,

Se observă că, în acest mod, doar un prizonier indică rezultatul corect iar toți ceilalți vor propune unul greșit. De remarcat e și că cel care îi salvează nu știe că el e cel ce a dat răspunsul bun. Important rămâne că împreună au aplicat o strategie care garantează că unul și numai unul, oricare-ar fi dintre ei, va răspunde corect, condiție suficientă ca să fie toți salvați. 

Aveți dreptate cu ipoteza Muzeler neiubite, ea nu e strict necesară. Am stat pe gânduri dacă să o pun, am pus-o totuși, ca să evit cazul banal în care cineva socotea că între cele două mulțimi ar fi o relație bijectivă și, de aici, discuții inutile. Se pare că precauția mea nu a evitat unele discuții pe lângă subiect, așa că mă puteam lipsi de ea. 

Felicitări, din nou, pentru idee!

0 0

Sunt de acord cu tine în două privințe, zec.

Și mie mi-a înroșit circuitele problema și este corect ce-ai scris.

Dar am o mică nelămurire pe care nu reușesc să mi-o clarific exact și sper să mă ajuți.

Fiecărui prizonier i se spune numele muzelor celorlalți prizonieri, dar nu și corespondența acestora.

Cu alte cuvinte, dacă fiecare prizonier ar cunoaște corespondența dintre numărul prizonierului x și numărul muzei sale, raționamentul pare să fie corect.

Edit:

Citind ce a scris Puiu după ce am postat eu, am înțeles mai bine.

Felicitări și de la mine!

Uff...în sfârșit, am scăpat și eu de "chinul" ăsta!

0 0

Acum că soluția a fost găsită pot spune că inițial problema era cunoscută drept 88 hats puzzle, mai apoi rainbow hats puzzle iar de acum înainte 9 muses puzzle. Să nu uităm că tiranul a impus un barem de timp, deci soluția este inutilă dacă este găsită după zile și nopți de gîndire.

0 0
Gheorghița, hai să zicem că problema li s-a dat la începutul nopții și n-au putut folosi ceasul solar pentru a măsura timpul, hai să mai zicem că au urmat câteva zile la rând mohorâte și cu ceață deasă, încât nici pe lumină nu s-a putut folosi umbra gnomonului, astfel că tiranul nu a putut măsura respectarea baremului de timp. Până la urmă, totul e bine când se termină cu bine :)
0 0
E genul de problema care trezeste mult interes.Am gasit solutia mergand pe caz particular mai exact cu 4 prizonieri.Pe alta parte nu am stat mereu sa ma gandesc dar ajunsesem sa cred ca mai repede rezolv ipoteza Riemann(cine stie poate o rezolv!!!) decat aceasta problema.E de remarcat ca poate fi generalizata si doar un singur prizonier va raspunde corect.
0 0
La o concluzie asemănătoare ajunsesem și eu, zec, și mă gândeam la un moment dat să încerc să arăt că nu se poate construi un raționament care să elibereze prizonierii, plecând de la ideea că orice numere/muze ar alege ei, se poate găsi un contraexemplu pe care l-ar fi ales tiranul.

Acum, cu demonstrația în față, nu-mi vine să cred cât de simplă era rezolvarea.

Într-adevăr, frumoasă problema, m-a captivat mult și m-a ținut în suspans și pe mine.
0 0
Ca să simplific problema, eu am plecat de la 2 prizonieri, cărora le-am asociat una din valorile 0 sau 1, adică cele două resturi posibile ale împărțirii la 2. Dacă se înțeleg să țintească totalul, care nu poate fi decât 0 mod 2 sau 1 mod 2, atunci unul din ei nimerește rezultatul corect indiferent dacă alocarea a fost (0,0), (0,1), (1,0) sau (1,1).

Mai departe, că sunt 7 pitici, 9 muze sau 101 dalmațieni, soluția e aceeași.
0 0

Ati fi putut astepta proiectatele ordonante de urgenta privind gratierea! smiley

0 plusuri 0 minusuri
Cred ca o idee ar fi urmatoarea:

-Sa numerotam muzele cu valori de la 1 la 9 in ordinea alfabetica asa cum au fost enumerate in enunt.

-Fiecare prizonier va primi si el o valoare numerica de la 1 la 9.

Prizonierul numarul 1 va alege prima valoare din muzele atribuite celor 8.

Prizonierul numarul 2 va alege a 2-a valoare  din sirul muzelor puse in ordine crescatoare si asa mai departe.Prizonierul numarul 9 va alege la fel cu al 8-lea prizonier.

Obtinem astfel o functie crescatoare de la multimea {1,2,....9} la multimea {1,2,...9}

Sa notam multimea {1,2....9} cu A si cu f functia definita mai sus.

Voi demonstra ca o functie monotona f:A->A are punct fix.

Daca A e un interval inchis si marginit devine teorema lui Knaster.

Ideea demonstratiei e cam aceeasi.Fie X={x din A|x<=f(x)}

cum f(1)>=1 avem ca 1 apartine lui X deci X este nevida si inclusa in A.

fie m valoarea maxima din X  .

Avem m<=f(m) si cum f e crescatoare rezulta f(m)<=f(f(m)) adina f(m) apartine lui X si cum m era maxim obtinem ca f(m)<=m de unde obtinem ca f(m)=m.

Sa demonstram ca functia definita de noi este crescatoare.

Fie i<j si consideram Ai respectiv Aj secventele ca sir al numerelor (muzelor) primite de prizonieri i si j.Ai si Aj vor avea in comun cel putin 7 valori in secventa reprezentand muzele celorlati 7 prizonieri in afara de i si j.Dar Ai si Aj au 8 termeni ceea ce inseamna ca nu putem sa avem un salt mai mare de o treapta ceea ce inseamna ca pot fi cel mult egale.
Experimentat (2.3k puncte)
0 0
Vreo două exemple ar ajuta la înțelegerea soluției prezentate.
0 0

fie tabelul in care am sa pun numarul prizonierului si muza selectata

prizonier123456789
muza537582693
functia definita
x123456789
f(x)233557889

ideea functioneaza dar din pacate am gresit cautind punctele fixe.Deci e cam partial rezolvata,in cazul de mai sus de remarcat valorile lui f in 2 si 4 care sunt asemanatoare cu functia muzei.

Daca consideram g(x) functia muzelor problema revine la arata ca f(x)=g(x) are solutie.

0 0

M-ați cam pierdut cu Teorema lui Knaster. Dar, pentru prima parte a răspunsului,vă rog să-mi spuneți dacă am înțeles bine și, dacă nu, să mă corectați.

Deci alocați Muzelor, în ordinea din enunț, numerele 1, 2,,...,8. 9, formând cu ele mulțimea A.

Prizonierii își repartizează și ei câte un număr de la 1 la 9 formând cu ele mulțimea A.

Definiți apoi o funcție f:A->A. Dar domeniul și codomeniul lui f nu sunt aceeași mulțime A. Dacă prizonierii își repartizează toate numerele de la 1 la 9, nu același lucru se întâmplă cu Muzele, pentru că tiranul nu le foloseste pe toate, una sau mai multe putând fi folosite de mai multe ori - aceeași Muză la mai mulți prizonieri -. Cele două mulțimi sunt doar cardinal echivalente dar nu și egale. De aici mai departe nu văd cum mai aplicați teorema. Dar poate nu înțeleg eu bine.

V-aș ruga să descrieți mai complet modalitatea prin care prizonierii aleg muzele, când afirmați că 

Prizonierul numarul 1 va alege prima valoare din muzele atribuite celor 8.

Prizonierul numarul 2 va alege a 2-a valoare  din sirul muzelor puse in ordine crescatoare si asa mai departe.Prizonierul numarul 9 va alege la fel cu al 8-lea prizonier.

Eu zic că urmând această procedură, doar cu noroc poate unul din ei să nimerească Muza care i s-a alocat.

Cel mai bine ar fi, cum zicea și Gheorghița, să dați un exemplu care să arate cum funcționează strategia descrisă.

P.S. Între timp ați postat comentariul, când eu tocmai îl redactam pe al meu.

0 0
functia muzelor adica g(x) nu e surjectiva conform enuntului,exista cel putin o muza pe care nimeni nu o va primi ,dar corsepondenta prizonier muza e o functie pe A cu valori in A unde A ={1,2...9}.

Pentru functia f ca mod de definire o sa consideram informatiile primite de catre fiecare prizonieri ca niste vectori sau matrice  .De exemplu in cazul tabelului din comentariul anterior prizonierul 4 primeste informatiile

(5,3,7,8,2,6,9,3) evident am exclus informatia muzei lui.Aceste valori le ordonam crescator si alegem a 4 valoare din vector astfel reordonat devine (2,3,3,5,6,7,8,9) si a 4-a valoare este 5 deci f(4)=5.Exceptie face al 9 -lea prizonieri care nu poate alege a 9-a valoare si deci el va alege tot a 8-a valoare.

Deci asa se defineste functia mea dar cum am specificat m-am derutat cautand punctele fixe ,dar pare sa functioneze.
0 0
Iată un contraexemplu la metoda pe care o propuneți:

Prizonier:     1    2    3    4    5    6    7    8    9

Muza:          4    3    6    5    8    2    7    1    1

x                 1    2    3    4    5    6    7    8    9

f(x)              1    1    2    3    4    5    6    7    8

Niciunul nu nimerește Muza care i-a fost alocată.
0 0
Se pare ca f(6) = 6 și ar fi corect.
0 0
După metoda indicată de zec f(6) = 5 pentru că 1 se pune odată ca cel mai mic număr alocat iar a doua oară ca al doilea număr după cel mai mic alocat. Vedeți și șirul valorilor crescătoare ale lui f(x) construit în exemplul lui zec.

Mă bucur sincer să vă reîntâlnesc pe Scientia :)
0 0
Deci ne trebuie alta idee:D .Multumesc pentru contraexemplu cu corectura respectiva .
0 0
Puiu: din secvența pe care ați propus-o (4,3,6,5,8,2,7,1,1), conform alogoritmului lui zec, pentru elementul cu număr de ordine 6 se elimină muza 2 din șir. Rămîne  (4,3,6,5,8,7,1,1)  , ordonăm (1,1,3,4,5,6,7,8) și luăm al 6-lea element care este 6 și nu 5. Exact așa a procedat zec în exemplul dat.
0 0
Gheorghița, aveți dreptate. Am buchisit alt contraexemplu care îndeplinește condițiile de la cap la coadă:

Prizonieri:     1    2    3    4    5    6    7    8    9

Muze:           2    2    3    3    4    4    5    1    1

x                  1    2    3    4    5    6    7    8    9

f(x)               1    1    2    2    3    3    4    5    5

Mulțumesc pentru observație.
0 plusuri 0 minusuri

Intriganta problema, dar nu vad sa fie informatie completa pentru rezolvare. de exemplu, exista o problema in definitie ”unora”...caci functie de contexte poate insemna o minoritate dar si un numar mic...adica in cadrul celor 9 minoritatea e 4 dar si numarul mic 7 e la ”unora”. O aporie, imi pare. Apoi, alte incompletitudini tin de dihotomiiile: crud stapan/dovada scrisa, crud stapan/promisiune indeplinita. Insa nici asta nu este rezolvare, caci necinstea crudului stapan nu se traduce in mod necesar in fiece context. Daca, prin neintelegerea mea, exista vreunul de ar ghici, intervine caracterul crud poate. 

Precizez ca nu activez prin domenii matematice, nu am aplecare spre mate dar la logica zilnica țin.

Novice (105 puncte)
0 0

Bun venit pe Scientia, Bogdan Sava.

Presupun că problema vi se pare imposibil de rezolvat și în acest sens o calificați ca aporie. Vă asigur că e doar dificil de rezolvat, iar asta în situația în care nu vă vine o idee utilă, ceea ce ar face-o chiar simpluță. 

Nu-mi e clar ce vreți să spuneți prin dihotomiile crud stăpân/dovada scrisă, crud stăpân/promisiune îndeplinită și nici în ce fel afectează ele completitudinea enunțului. Nici exemplele cu minoritatea reprezentată de numărul 4 și numărul mic 7 nu  au vreo legătură cu structura ipotezei, logică dacă vreți. Unora înseamnă că doar un număr neprecizat din cele 9 va fi folosit. Așa e problema și e, într-adevăr, de matematică.

Spuneți că nu aveți aplecare spre matematică. Păcat! V-ar putea fi foarte utilă în respectarea regulilor logicii zilnice la care țineți.

Tot ce funcționează după reguli logice (mă refer la logica clasică în special) este susceptibil de a fi descris cu mijloacele matematicii. 

0 0
M-as mira sa fie rezolvabila (matematic) cand avem incompletitudinea/incertitudinea la care m-am referit cu dihotomia stapanului crud-caracterului tiranic. Caci nu-i tinut sa elibereze pe careva de care dispune avand puterea (informatie din enunt-tiran). Daca se inlatura informatia ca e tiran si nesupus controlului, atunci buna intelegere dintre unul din cei 9 si tiranul interlocutor ajunge pentru aplicarea unei solutii matematice (despre care veti fi stiind). Si atunci intreb, considerentul logic al urmaririi datelor (tiranul, despotul) nu depaseste orice raspuns matematic valid? Sugerez citirea https://en.wikipedia.org/wiki/Common_knowledge_(logic) unde este si informatia cinstei/credibilitatii. In antiteza. Si am mai zis, chiar de e tiran, asta inseamna bun plac si poate sa se tina de cuvant cand vrea.
0 0

Mulțumesc pentru link. Dacă faceți o plimbare pe secțiunea Matematică a Scientiei Q&A veți găsi multe probleme interesante bazate pe ipoteza de tip common knowledge. Nu e și cazul problemei de față. 

Corectitudinea tiranului e nerelevantă în acest caz. Dar uite, strict pentru dumneavoastră, ca să deblocăm situația, adaug că tiranul se va ține de cuvânt și îi va elibera, dacă măcar unul din prizonieri va indica Muza care i-a fost atribuită. 

Sper că dacă v-am înlăturat acest obstacol veți încerca pasul următor, acela de a încerca să rezolvați problema. 

0 0
Sunt lamurit, multumesc pentru tact si pentru provocare. E si o neintelegere la mijloc, caci aceasta problema este dublu incadrata: la noutati si la matematica. Mi s-a adus in atentie de catre un prieten, ce o postase pe fb in forma usor modificata, fara apelul exclusiv la matematica. Cata vreme incadrarea e pe sectiune atunci se limiteaza perspectiva gandirii/interpretarii la sectiune. Intrucat la notiunile avansate de matematica nu (ma) mai pricep, voi pleca de la acest subiect. Insa pe acest site voi reveni mai des, gasind probleme de interes (pe alte sectiuni). Spor la gandit matematicienilor.
...