haios.ro

Comment

Ancient wise - 8 Feb 2013

Problema data la interviul de angajare la Google

Presupunerea de baza e ca piratii sunt rationali si fiecare vrea cat mai mult. Nu e foarte clar, dar cred ca nu exista posibilitatea "abtinerii".
P5 stie ca daca ramane numai cu P4, acela ii va lua toti banii. Prin urmare, nu are niciun interes sa-l elimine pe P3, daca acela ii da ceva. Chiar si 1 galben. P3 stie si el ca, intr-o astfel de situatie, va putea conta pe votul lui P5 chiar daca ii va da doar un galben. In situatia in care P1 e eliminat, P2 va putea conta pe votul lui P5 daca ii da mai mult decat i-ar da P3, deci daca i-ar da 2g. La fel si P1 isi poate asigura votul lui P5 pentru 3g. Acum P4 stie ca daca ajunge singur cu P5 ia toti banii. Dar, pentru asta trebuie sa scape de P3. Ori, acela ii va da 1g lui P5 si lui P4 nimic ... iar P4 nu vrea asta. Dar, va vota totusi pentru asta, daca P2 fiind la propunere, acela nu-i va da nimic. Pe de alta parte, asta nu conteaza, fiindca P2 poate cumpara votul lui P5 cu 2g, si atunci voturile contra ale lui P4 si P4 nu mai conteaza. Prin urmare, maximul pe care l-ar putea obtine P4 ar fi, eventual, 1g, daca P1 va dori sa i-l ofere. P1 are nevoie, in afara de votul lui, de inca doua voturi. Votul lui P4 il va obtine cu 1g, si, ca urmare, ii va da 1g. Dupa cum am mai aratat, daca P1 este eliminat, P2 isi poate asigura votul care ii mai este necesar cu 2g, de la P5. P3 nu poate impiedica asta, si, pe de alta parte, nu are interes sa o faca pentru mai putin de 99g, deoarece, daca P2 ar fi eliminat, el va da 1g lui P5 si va pastra restul de 99. Dar, e clar ca nu va primi 99g, de fapt, nu va primi nimic daca P1 este eliminat. Prin urmare, va vota impotriva eliminarii lui P1, chiar si pentru 1g.
Din cele de mai sus, rezulta ca P1 va imparti banii dupa cum urmeaza: pentru sine va opri 98, si va mai da cate 1g lui P3 si P4. Solutia este, deci: P1 - 98, P2-0, P3-1; P4-1; P5-0.