23 de maig de 2013

De com els pirates cruels es reparteixen el botí


Al llibre Locos por las matemáticas el divulgador matemàtic Ian Stewart dedica un capítol (Apuradas piruetas entre piratas) a estudiar un problema de lògica força interessant per la seva sorprenent solució. L'enunciat és el següent:
“Deu pirates s'han fet amb un tresor de cent peces d'or i se'l volen repartir. Són pirates democràtics, a la seva manera, i tenen el costum de fer els repartiments de la següent forma. El pirata més cruel fa una proposta de repartiment i tots voten: cadascú té un vot, inclòs el que fa la proposta. Si s'obté un 50% o més dels vots a favor, la proposta s'aprova i es posa en pràctica. En cas contrari, el proposant és llançat per la borda i es repeteix el procediment amb el següent pirata més cruel. 
Tots els pirates frueixen llençant gent per la borda, però si els dónes a triar s'estimen més tenir diners a la butxaca. No els agrada ser ells mateixos els llançats per la borda. Tots els pirates són racionals, saben que els altres pirates són racionals, saben que ells saben que.... (../..) No hi ha dos pirates igualment cruels, de forma que hi ha un ordre per fer propostes precís, que és conegut per tots ells. Per acabar, les peces d'or són indivisibles i no es permeten acords per compartir peces (donat que cap pirata confia en que els seus col·legues respectin un acord d'aquesta mena). Cadascú es preocupa només d'ell mateix. 
Quina proposta maximitzarà els guanys del pirata més cruel?"


Aquest problema pot proporcionar una interessant discussió en grup (a l'aula o a la tertúlia d'amistats). Convé recordar, a mesura que es vagin fent propostes, quines són les condicions del problema:

  • tots els pirates són lògics perfectes
  • cadascú vol obtenir el màxim guany possible
  • amb la meitat justa dels vots n'hi ha prou perquè la proposta sigui acceptada, no cal majoria.
Potser cal afegir unes condició derivades de les anteriors:

  • és millor viure que ser aliment dels peixos
  • és millor tenir alguns diners, per pocs que siguin, que no tenir-ne cap
Així una proposta del tipus: "fem parts iguals" no prosperarà si hi ha algun argument lògic que doni opció a un pirata a obtenir ni que sigui una moneda més que els altres. Ni tan sols la farà el proposant si veu opció de  treure'n més.

Deixem tres línies i una bandera per pensar i passem a la solució
..............................................................
..............................................................
..............................................................



Solucionem el problema

Aquest és un problema clàssic en que convé fer reduccions i procedir de forma ordenada i a la inversa: què passa si només hi ha un pirata? I si hi ha dos? I si són tres?

Designarem el grau de "crueltat" amb un subíndex en ordre descendent: P1 serà el menys cruel, P2 serà més cruel que P2 però menys que P3 ... i així succesivament.
  • Un pirata
No hi ha dubte. S'ho queda tot: 100 monedes
  • Dos pirates
El pirata més cruel (P2) proposa quedar-s'ho tot. Quan es voti P2 votarà a favor i P1 en contra. Amb la meitat de vots n'hi ha prou i la proposta queda aprovada.
  • Tres pirates
Aquí la cosa es complica. El P1 sap que si la proposta del P3 es rebutja i només queden dos pirates ell es quedarà sense res. Per tant l'interessa aprovar la proposta del P3 . Però el P1 sap que el P3 ha fet aquest raonament. Mirem, per exemple, aquesta proposta:

P1 P2 P3
0 0 100

P2 votarà en contra i P3 a favor. Però no tenim molt clar què farà P3 . Tant si s'aprova com si no es quedarà pelat. Potser considera que posats així pot votar en contra per castigar a P3 per la seva avarícia. Hi ha alguna manera de que P3 el convenci? La resposta és que sí: subornant-lo. Però gastant-se el mínim amb el suborn. Per tant la proposta que li proporcionarà més guanys a P1 i Pserà aquesta altra:

P1P2P3
1099
P2 votarà en contra, mentre que P1P3 ho faran a favor. Per a P1 és millor una moneda que cap.

Ara segur que ja anem enganxant millor les "regles" del joc!
  • Quatre pirates
Quan tenim quatre pirates se suposa que tothom ja sap què passa quan només queden tres i dos pirates. La qüestió ara és mirar com es quedava el P2 en la situació anterior: pelat. El P4 ho sap i també sap que només necessita un vot. A qui cal subornar en aquesta situació? Al P2 i amb el mínim de diners. La proposta del P4 serà:
P1 P2 P3 P4
0 1 0 99

Dos vots a favor... dos en contra. La proposta és acceptada!
  • Cinc pirates
Ara hi ha un petit canvi: la majoria són tres vots per tant cal "convèncer" a dos pirates. Quan queden només 4 pirates els que "pringuen" són P1P3 . Són aquests els indicats pel suborn i fent-ho amb el mínim de "pasta" necessària: dues monedes.

P1 P2 P3 P4 P5
1 0 1 0 98

  • Deu pirates
Suposem que ja podeu reconstruir els casos que ens deixem: 6 pirates, 7, 8 i 9. Es pot observar que si hi ha una quantitat senar de pirates cal subornar als senars i si és parell, als parells. Per tant amb 10 pirates la proposta del P10 serà:

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
0 1 0 1 0 1 0 1 0 96

Sorprenent, no? Ben segur que quan heu llegit el problema no us imaginàveu una solució tan òptima per al primer pirata!

I si hi ha molts i molts pirates?

Ian Stewart comenta en el llibre una ampliació del problema molt interessant i que aquí només plantejarem. 

Quina haurà de ser la proposta per repartir les 100 monedes si hi ha 500 pirates?

Per comprendre la situació hem d'observar que hi ha un cas límit: 200 pirates. Si observem el desenvolupament de les propostes a mesura que augmenten els pirates veurem que el pirata més cruel cada vegada guanya menys perquè ha d'invertir més ens suborns. Amb 200 pirates oferirà una moneda a cada pirata parell i només li en quedarà una per a ell mateix. Com variarà ara l'estratègia amb 201, 202, 203...?

Cap comentari:

Publica un comentari a l'entrada