El problema de los 5 piratas

Question

Cinco piratas encontraron juntos un tesoro que tiene 1000 piezas de oro. Para repartirlas entre ellos, han decidido numerarse, y que el pirata 5 proponga cómo deben repartirse. Después, su propuesta es votada a favor o en contra. Si la mayoría vota en contra, el pirata 5 es asesinado y propone entonces el pirata 4, y así continúa. Así, si la propuesta del pirata 5 es aceptada por 2 o más, el pirata 5 vive y su propuesta es llevada a cabo. En caso contrario, si la propuesta del pirata 4 es aceptada por 2 o más, el pirata 4 vive y su propuesta es llevada a cabo, y así sucesivamente. Suponiendo que las prioridades de los piratas son, en orden:

a)vivir,

b)ganar piezas de oro,

c)matar a sus compañeros (esto es, si pudiera decidir entre que un compañero viva o muera, preferiría que muriera, siempre y cuando esto no signifique para él perder piezas o morir él mismo),

Además cada pirata es totalmente racional, ¿cuál es la propuesta óptima para el pirata 5? Consideramos que una propuesta es óptima para el pirata $n$ si con ella se queda con el mayor dinero posible y sobrevive.

Este problema fue originalmente publicado por el Dr. Gil Bor en su Rincón de Problemas de CIMAT, y se puede ver una solución en la página http://personal.cimat.mx:8181/~gil/ciencia_para_jovenes/rincon/soluciones/e27.html , pero a mí me parece que la solución publicada es incorrecta, así que abro el debate.

También, podemos preguntarnos, ¿qué pasa si son $n$ piratas? ¿Cuál es la propuesta óptima para el pirata $n$? ¿Qué pasa conforme $n$ se acerca a 1000?

Comments

¿cómo se decide un empate?

---

Según entiendo con empate se acepta las propuesta

---

Estoy de acuerdo que la solución esta mal. No es cierto que 1 siempre va a decir que no. Y a 4 le conviene decir que no, pues si el decide, puede convencer a 1y a 2 con (1,1,0,998) pues si 3 decide se quedan sin nada. la mejor estrategia para 5 es (2,0,1,0,997) o (0,2,1,0,997)

---

Depende de qué tipo de empate hablas. Si te refieres a empate cuando los piratas votan, entonces la propuesta se acepta. Si te refieres a empate en las propuestas, nunca dije que la propuesta óptima deba ser única. Sería interesante pensar en una restricción que la hiciera única, también.

---

En lo que escribí arriba estaba pensando que el que propone no vota. Es cierto esto?

---

A ver, para aclarar. Aunque creo que no hay ambigüedad en el enunciado: el que propone no vota, y si hay empate en la votación, la propuesta es aceptada. Así que el problema es ligeramente distinto del analizado en Wikipedia, y por lo tanto no tiene la misma solución.

Answer 1

Este es un problema bien conocido y la respuesta viene en wikipedia. La solución es que el primero al mando se lleva la gran mayoría de las monedas dándole el mínimo posible a cada pirata con la misma paridad y 0 a los que tienen paridad distinta. Por ejemplo si son 7 piratas el 7 le daría 1 moneda al 5, una al 3, y una al 1 quedándose con el resto. Con eso ganaría el voto de los piratas 1,3,5 y 7 obteniendo así la mayoría. Se puede demostrar por inducción.

Cuando tienes 2000 piratas, la mitad tendrá una moneda y la otra mitad ninguna, después de ese punto los piratas que no alcancen moneda serán la mitad o más y hecharán a los tiburones a los que sea necesario hasta que la mitad obtenga una moneda.

Comments

La solución depende un poco de qué haces en una votación empatada. La versión que yo conosco dice que en caso de que la votación sea un empate la repartición se acepta. En la versión del link que pones se está tomando que en caso de empate la decisión se rechaza.

---

Estoy pensando que quizás sobresimplifiqué lo que pasa a partir de 2000 piratas (doble de piratas que monedas). Si tienes 2001 piratas, sabes que todos los 1000 que se quedarían sin nada en el caso 2000 van a votar a favor si les das algo. Así que el pirata 2001 puede dar todas las monedas a esos 1000 piratas y él conformarse con la vida. Si son 2002, los 1001 piratas que no tendrían nada en el caso 2001 se conformarán con una moneda. Sólo que no tienes tantas, así que le das una moneda a cada uno de 1000 de ellos y te con tu propio voto tendrás 1001 a favor y 1001 en contra, así que todavia la armas.

Con 2003 piratas ya no puedes hacer este truco, así que te tirarán por la borda sin importar qué propongas (por los 1002 votos de los que no ganen nada). Así que con 2004, ya tienes ganado el voto del pirata 2003, y además puedes ganar otros 1000 votos dando una moneda, más el tuyo son 1002 a favor y 1002 en contra.

Con 2005 te tiran por la borda sin importar qué pase, así que el 2006 tiene ganado el voto del 2005, pero no el del 2003 que ya sabe que conserva su vida si llegan al 2004, así que ahora sí, de ahí en adelante a todos los tiran por la borda.

---

Creo que es aún más complicado que eso, como se puede ver en la solución de wikipedia que mencionas

---

http://en.wikipedia.org/wiki/Pirate_game

También tiene un análisis mejor que el mío para cuando el número de piratas es más que el doble de monedas. Insisto en que:

a) El que propone la repartición también vota.
b) En caso de que haya misma cantidad de votos a favor y en contra se ACEPTA la repartición.