Dilema prizonierilor(dificultate 15%)

Vezi solutia problemei

                                                 Motto:  Cea mai mare inspiraţie vine adesea din disperare (Comer Cotrell)

E. Dilema prizonierilor

Alice şi Bob sunt prizonierii tiranului Charlie. Într-o duminică, Alice este adusă într-o cameră specială, unde pe masă se află un pachet de 52 cărţi de joc. Cărţile sunt etalate pe masă, toate cu faţa în sus pe o singură linie, într-o ordine arbitrară. Alice are voie să inter-schimbe – dacă vrea – maxim două cărţi.

După care iese din cameră, iar Charlie întoarce toate cărţile cu faţa în jos, păstrând însă ordinea lor.

Bob este adus în cameră. Charlie îi cere să îi dea de pe masă o anumită carte T (de exemplu, T poate fi un Valet de cupă). În încercarea de a localiza cartea T, lui Bob i se permite să întoarcă pe faţă cel mult 26 cărţi.

Dacă Bob reuşeşte, ambii prizonieri vor fi eliberaţi imediat. Dacă nu, vor rămâne uitaţi în închisoarea lui Charlie.

Găsiţi o strategie care garantează succesul celor doi prizonieri.

Se ştie:

  • Alice şi Bob ştiu regulile şi pot pune la cale o strategie până cel târziu sâmbătă (duminică ei nu mai au nici o modalitate de comunicare).
  • Alice nu are nici o posibilitate de a afla dinainte ce carte T va alege Charlie.
  • Alice şi Bob au un IQ foarte ridicat.
  • Bob poate folosi o strategie de întoarcere a fiecărei cărţi bazată pe ceea ce a întors anterior.

 

Sursă: Macalestear POTW.

Vezi comentarii
Logheaza-te in site pentru a trimite solutii si comentarii
aatanasiu

Am gasit o problema similara in MSRI (Mathematical Science Research Institute), primavara 2015:

Prisoner A is brought into the warden’s office and shown a row of n coins. The warden points to one of the coins. The prisoner is then required to turn over exactly one coin (that is, reverse the heads/tails of that coin). Prisoner A is escorted out of the room, and then Prisoner B is brought into the room and asked to point at a coin. If the prisoner points at the same coin that the warden pointed at earlier to Prisoner A, then both prisoners are released. Otherwise, one year is added to each of their sentences. The “usual” rules are assumed: the prisoners have a strategy session the night before and know what will happen the next day, though of course they do not know what coin the warden will point to, or what the heads/tails orientation of the coins will be (so that they might as well assume that the initial orientation is random, that is, the orientation of each coin is determined by a flip of a fair coin). No further communication is allowed after the strategy session; for example, they do not communicate at all after Prisoner A is taken to the office. Prove that a perfect strategy (that is, one in which the prisoners will always be released) exists if and only if n is a power of 2.

Comment: This problem apparently first appeared (with n = 8) in the 2007 International Tournament of Towns, and we first saw it (with n = 64) in Anany and Maria Levitin’s Algorithmic Puzzles, problem 148.


bburlacu

Se pot interschimba maxim 2 carti inseamna de fapt ca se poate face o singura interschimbare?


aatanasiu

Da. Sunt posibile doua actiuni:

1. Nu se face nimic (pas);

2 Se aleg cartile de pe pozitiile m si n si se schimba intre ele.


aatanasiu

Da. Sunt posibile doua actiuni:

1. Nu se face nimic (pas);

2 Se aleg cartile de pe pozitiile m si n si se schimba intre ele.