Pirati i podela plena

Evo jednog zanimljivog zadatka koji zahteva dosta koncentracije.

Posada od n pirata se domogla kovčega sa blagom u kome se nalazi određen broj zlatnika. U toj posadi pirati su raspoređeni po snazi od najjačeg do najslabijeg i svi su upoznati sa tim redosledom. Po piratskim pravilima najjači predlaže podelu plena koja se prihvata ako za nju glasa bar polovina svih pirata. Ako se podela ne prihvati pirat koji je dao predlog biva eliminisan (hodanjem na dasci) i dužnost podele plena pripada sledećem po snazi i tako redom sve dok se ne usvoji neki predlog. U glasanju i predlaganju podela plena pirati se ponašaju racionalno i znaju da se i drugi pirati ponašaju racionalno. Svakom piratu je lista prioriteta ista:

- Piratu je pre svega najviše stalo da sačuva živu glavu.

- Ako je prvi uslov zadovoljen pirat će glasati i predlagati tako da osvoji što veću količinu zlatnika.

- Ako je piratu po obe prethodne tačke svejedno, on će glasati protiv podele u cilju eliminisanja svojih rivala.

Koji će biti prvi pirat po snazi koji će sačuvati živu glavu i kako će glasiti konačna podela plena ako u kovčegu ima 100 zlatnika a broj pirata iznosi: a) n=100, b) n=2004.

Originalno rešenje zadatka nemam, rešavao sam ga bez papira i olovke i došao do određenog rezultata koji ću kasnije napisati da ne upropastim zabavu onima koji budu hteli da rešavaju - ne garantujem da je tačno, ali možemo međusobno uporediti kad još neko uradi. Ako smatrate da ste rešili zadatak najpre napišite samo rezultat da vidimo da li će biti više različitih rešenja, a posle ćemo diskutovati i postupak.

Još nešto: mislim da zadatak nije dovoljno precizno formulisan, može se rešiti i ovako ali smatram da treba dodati još jedno pravilo:

- Ako pirat koji predlaže podelu ima izbor između više mogućnosti od kojih mu je svejedno koju će odabrati, on će podelu predložiti tako da najslabiji pirati dobiju što više zlatnika (jer ne želi da "časti" svoje jake konkurente).

Ovo sam ja naknadno dodao, ako rešite zadatak bez ovoga nema problema a ako vam bude kojim slučajem zatrebalo možete koristiti.

Ajd' sad na posao :)

---

Posto pirati dele plen redom od najjaceg do najslabijeg da li to znaci da ako ih ostane dvojica da ce taj jaci da ostavi sve sebi jer ovaj slabiji ne moze da ga natera da seta po dasci? Takodje koliko je jak treci od nazad i da li je jaci od poslednje dvojice. Drugim recima, da li on moze da ostavi sve sebi? Mozda bi ipak bilo bolje da najslabiji predlaze podelu.

Kad ih ostane dvojica ovaj najjači predloži da on uzme sve (logično), zatim njih dvojica glasaju - ovaj slabiji glasa protiv, ali ovaj jači glasa za (logično), a da bi se podela prihvatila dovoljno je da polovina pirata glasa pozitivno, tako da u ovom slučaju jači uzima sve. Nije bitna snaga pojedinca, da li će se podela prihvatiti ili ne odlučuje se glasanjem, odnosno ako se bar polovina pirata slaže sa predlogom onda se zlatnici tako podele i tu je kraj, ako nema dovoljno onih koji se slažu piratu koji je to predložio ode glava i podelu predlaže sledeći u nizu.

---

Da, pošto u zadatku kaže da se podela prihvata ako bar polovina glasa, ako ih je dvojica jedan je pola i šta god on predloži prihvata se.

Ako on sve uzme sebi ova dva preostala izglasaju da on šeta po dasci - drugi zato što to znači da će u sledećem krugu on dobiti sve a poslednji zbog trećeg uslova.

Što se tiče rešenja, ovako naškrabano malo na brzinu mislim da pod a) već prvi može sačuvati glavu, a na osnovu toga mislim da bi pod b) 200-ti (tj. najjači kad ih ostane 200) mogao sačuvati glavu, ali to baš nisam još razradio već ću se sutra ujutru pozabaviti time.

Da su ostala trojica i da sam ja najslabiji,ja ne bih glasao protiv najjačega,jer bih znao da ću ispu*iti posle s drugim,a i treći (najjači) ne bi trebalo da traži "puno" ako hoće živu glavu..... tako da varijanta da sve ostane drugom odpozadi vredi samo ako su pirati ne znaju da računaju,a u sličnim zadacima treba računati na najbolje od igrača..?!

Ovo je bila hipotetička situacija u kojoj je srki pitao "šta bi bilo kad bi bilo" - ako treći odluči da zadrži sve pare za sebe najslabijem je sve jedno da li će pobediti treći ili drugi pošto ne dobija ništa ni ovako ni onako i zbog trećeg uslova glasa protiv.

Što se tiče rešenja, ostajem pri tome da svi mogu da prežive pod a) a pod b) bi možda mogao da preživi i 202. (od pozadi) samo nisam siguran da li bi takva raspodela plena bila u opciji, videćemo kad budemo prikazivali rešenja.

Pod a) sam i ja dobio isto (to je dosta lako), a pod b) po mojoj računici može da preživi znatno više, dobio sam da će glavu sačuvati 781. od napred, tj. da ih ostaje ukupno čak 1224. Možda i nisam u pravu, mislim da je najbolje da sačekamo da još neko kaže svoje rezultate pa ćemo onda analizirati jedno po jedno.

---

Zadatak je krajnje prost. Neka je G broj gusara i Z broj zlatnika. Svakom gusaru pridružimo njegov redni broj po snazi u obrnutom poretku (1 najslabijem, a G najjačem). Prvo se reši slučaj kiada je 1<G<2Z+2. Primetimo da ako je taj uslov zadovoljen i važi G>2, da će onda i nakon eventualnog smaknuća predlagača ostati zadovoljen jer se broj gusara smanjio, a broj zlatnika ostao isti, tako da možemo svoditi složenije slučajeve na prostije razmatrati samo ovaj slučaj. Takođe, predlagač će svakakao glasati za svoj predlog. Krenimo redom.

G=2:
2 će predložiti da dobije on sve, pošto 1 ne može da ga nadglasa. Dakle, podela glasi:
2 - Z,
1 - 0.

G=3:
2 sigurno glasa protiv, a 1 glasa za samo ako mu se ponudi barem jedan zlatnik. 3 treba da zadovolji barem jednog glasača, što je moguće jer je 2Z+2>3. Dakle, 3 ostaje živ, a podela glasi:
3 - Z-1,
2 - 0,
1 - 1.

G=4:
3 traži sve zlatnike da bi glasao za, 2 traži barem jedan, a 1 traži bar 2. Da bi 4 ostao živ, neophodno je da zadovolji barem jednog glasača (pošto će on glasati za). On taj uslov može da zadovolji opet zbog uslova 2Z+2>4. Podela dakle glasi:
4 - Z-1,
3 - 0,
2 - 1,
1 - 0.
Podela je jedinstvena, jer je zbog istog uslova gusar 3 skuplji od gusara 2.

Na sličan način se zaklkučuje da će un opštem slučaju podela glasiti
G - Z - ceo deo od (G-1)/2,
G-1 - 0,
G-2 - 1,
G-3 - 0,
G-4 - 1,
G-5 - 0,
...
kao i da je ta podela jedinstvena. Preciznije, može se koristiti matematička indukcija po G.

Ukoliko je sada G=2Z+2. Pošto najači gusar sigurno glasa za svoj predlog potrebno mu je barem još Z glasača da bi ostao živ. Prema prethodnom, mi znamo podelu u slučaju njegovog smaknuća. Dakle, gusari sa neparnim brojevima traže po bar dva zlatnika, a sa parnim po jedan. Pošto parnih gusara ima (osim predlagača) tačno Z, on mora njima da podeli po jedan zlatnik, i to mu je jedini način da preživi.

Neka je sada G=2Z+3. Prema prethodnom će parni glasači tražiti po barem dva zlatnika (osim onog sa brojem 2Z+2 koji traži jedan), a neparni po jedan. No, njemu treba još barem Z+1 glasača, a zlatnika ima samo Z, i eto prve pogibije.

Ukoliko je pak G=2Z+4, zahtevi su isti kao malopre, osim što će 2Z+3 da glasa za predlog i za džabe da bi ostao živ. Predlagaču je potrebno još Z glasača. Onih koji traže samo jedan zlatnik ima čak Z+1, tako da predlagač svakako preživljava (ali bez plena), ali podela nije jedinstvena, osim u slučaju dodavanja Bojanovog uslova.

Pretpostavimo sada da je G=2Z+5. Pošto u prethodnom slučaju niko ne gine, niko ne dobija više od jednog zlatnika, i u slučaju originalne postavke niko nije siguran da će dobiti i taj jedan zlatnik, svi će tražiti po jedan zlatnik da bi glasali za predlog. Ipak, njemu je potrebno da pridobije više glasača nego što ima zlatnika, tako da gine.

Stoga je u slučaju da je G=2Z+6 gusar 2Z+5 siguran glasač (čak i za džabe), dok ostali traže po jedan zlatnik. Na tajn način predlagač ne može da pridobije potrebnih Z+3 glasača, pa gine.

Ali, onda su u slučaju da je G=2Z+7 predlagač ima čak dva "besplatna" glasača - 2Z+5 i 2Z+6. Na žalost, ni to nije dovoljno, pa će i on poginuti.

Međutim, to znači da će u slučaju da je G=2Z+8, predlagač imati čak tri "besplatna" glasača, što mu je dovoljno da preživi.

Stoga u slučaju da je G=2Z+9 predlagač nema "besplatne" glasače, pa gine. U opštem slučaju, za G>2Z+1 predlagač preživljava ako i amo ako je broj G-2Z potpun stepen dvojke. Tada su mu "besplatni" glasači tačno oni koji imaju redni broj veći od prvog sledećeg koji bi preživeo u slučaju pogibije predlagača i ima ih (G-2Z)/2. Ako je pritom i G>2Z+4, onda on može na potuno proizvoljan način da izabere Z od onih preostalih glasača (koji traže barem jedan zlatnik da bi glasali za predlog).

U slučaju Bojanove dopune zadatka, po zlatnik dobijaju gusari sa neparnim brojevima od 1 do 2Z+1 ako je pomenuti potpun stepen dvojke istovremeno i potpun stepen četvorke, odnosno gusari sa parnim brojevima od 2 do 2Z+2 u suprotnom.

Dakle, preživeće 1224 gusara (poginuće njih 780), pri čemu će gusari sa rednim brojevima od 713 do 1224 (njih ukupno 512) sigurno ostati bez plena, dok će od ostalih 712 njih tačno 100 dobiti po zlatnik, ali to nikome nije zagarantovano. U slučaju Bojanove dopune zadatka po jedan zlatnik će dobiti gusari sa neparnim brojevima od 1 do 201.

---

Da, tako sam i ja rešio, eventualno smo mogli još malo da sačekamo da ne upropastimo ostalima zabavu ali u svakom slučaju Nedeljku svaka čast ne samo za rešenje nego i za precizno objašnjenje. Sad je jasno i zašto sam postavio ovaj dodatni uslov, iako se zadatak može rešiti i bez toga ovako je sve precizirano. Nije nam trebalo u ovom rešenju, ali bez mog dodatnog uslova nisam siguran kako bi gusar glasao u slučaju da po trenutnom predlogu ima jedan zlatnik a ako ne prođe podela možda ima 2 a možda i ništa.

---