El problema de los piratas.

Ahora trataremos un poco la programación dinamica.
Para mi, en escencia la programación dinamica no es mas que adentrarse a los mas profundo de un problema y resolver un pequeño pedasito del problema, dar un paso para atras y resolver otro pedacito, y así hasta terminar.

Lo importate es poder separar el problema de tal manera que podamos resolver estos pequeños problemitas de forma eficiente (si resolver todos los problemitas es mas tardado que resolver el problema original se pierde el sentido).

Para ejemplificar la idea de Programación dinamica trataremos el problema de los piratas.

En un gran barco pirata existian 10 piratas malvados con un gusto un tanto extraño por la democracia. Como todo buen pirata, se dedicaban a despojar a los barcos de sus poseciones.
Un dia los piratas lograron obtener un botin de 100 monedas de oro. Como estos piratas tenían un gusto extraño por la democracía no se repartian las monedas de oro de forma equitativa.
Si no que los piratas se ordenaban por el tamaño de sus barbas, el pirata con la barba mas larga proponía una forma de repartir el botin, digamos 100 monedas de oro para el, y nada para los demas.

Despues de la propuesta todos los piratas votan para decidir si aceptan dicha propuesta o la rechazan. Si la propuesta es votada el 50% o mas de los piratas vivos la propuesta es aceptada, si no esta es rechazada y el pirata que la propuso sera tirado por la borda.
Los piratas, siendo unos seres razonables, siempre preferían tener oro en las manos en contra de no tenerlo, en caso de no obtener oro prefieren no morir, y luego prefieren ver caminar a un pirata por la plancha.

---

Orden de preferencía:
-Oro
-Vivir
-Ver a alguien caminar por la plancha
-Nada

Metodo democratico:
El pirata con la barba mas larga realiza una propuesta, los piratas votan en base a sus preferencías. Si almenos el 50% de los piratas votan a favor se aprueba la propuesta y se termina la repartición, votan menos del 50% en favor, el pirata que realizo la propuesta es lanzado por la borda y el siguiente pirata con la barba mas larga realiza una nueva propuesta.

---

La pregunta para este problema consiste aconsejar al pirata con la barba mas larga para que realice la repartición que maximize sus intereses.
Para hacer las cosas mas sencillas de entender, numeraremos a los piratas de acuerdo al tamaño de su barba.
Diremos que el pirata con la barba mas larga es el número 1, el segundo pirata con la barba mas larga sera el número 2, y así sucesivamente hasta el pirata con la barba mas corta que sera el pirata número 10.



La respuesta a este problema se da a continuación:
Si quiere obtenerla por su cuenta, solo siga leyendo.

Pirata 10	Pirata 9	Pirata 8	Pirata 7	Pirata 6	Pirata 5	Pirata 4	Pirata 3	Pirata 2	Pirata 1
0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	96 monedas

Para llegar a esta respuesta aplicaremos la idea de programación dinamica de empezar al final y trabajar hacía atras.


a)
Supongamos que la propuesta de todos los piratas del 1 al 9 fue rechazada y solo queda el pirata número 10 (el de la barba mas corta).
Ya que él es el unico pirata vivo, la mejor repartición que puede conseguir es repartir las 100 monedas de oro para él. Dado que es el unico pirata el votara a favor de su propuesta.


b)
Ahora suponga que solo quedan el pirata 10 y 9 vivos, es el turno del pirata 9 de hacer una propuesta.
Veamos como razona el pirata 9:
Con su voto, no importa si el pirata 10, vota en su favor o no, el tendra almenos el 50% de los votos, con lo que su propuesta pasara.
Por ende, lo que mas le conviene es una repartición en la que el obtenga las 100 monedas y el pirata 10 no obtenga nada.


c)
Ahora demos otro paso atras, y veamos la situación cuando quedan los piratas 10, 9 y 8 vivos.
A diferencia del pirata 9, el pirata 8 no puede ganar la votación solo con su voto, necesita el voto de almenos uno de los otros piratas.
El sabe que si su propuesta no pasa, tendremos el caso descrito en b), donde el pirata 10 no revice ninguna moneda.
Luego, suponga que el pirata 8 propone una repartición de 99 monedas si mismo, cero monedas para el pirata 9, y una moneda para el pirata 10.
Con esta propuesta el pirata 10 obtendra una moneda de oro, mientras que si no vota en favor de esta propuesta tendremos el caso en b) donde el no gana ninguna moneda.
Luego el pirata 10 votara a favor de esta propuesta, sumando el voto del pirata 8 (que obviamente votara por su propuesta) se aprobara esta propuesta.

Repartición de monedas:

Pirata 10	Pirata 9	Pirata 8
1 moneda	0 monedas	99 monedas

d)
Demos un nuevo paso para atras, ahora con los piratas 10, 9, 8, y 7 vivos.
Es el turno del pirata 7 para dar su propuesta.
El pirata 7 necesita 2 votos para que su propuesta pase, contando el suyo, necesita convencer a uno de los otros 3 piratas vivos.
Su propuesta es la siguiente:

Pirata 10	Pirata 9	Pirata 8	Pirata 7
0 monedas	1 moneda	0 monedas	99 monedas

Si la propuesta del pirata 7 no pasa, tendremos el caso marcado como c) en donde el pirata 9 no obtiene ninguna moneda.
Como en la propuesta del pirata 7 el pirata almenos resive una moneda, mejor votar a favor.
Así es como el pirata 7 consigue el voto del pirata 9 y consigue aprobar su propuesta.


e)
Un nuevo paso atras nos lleva a la situación en que los piratas 10, 9, 8, 7 y 6 estan vivos.

La propuesta del pirata 6 sera la siguiente:

Pirata 10	Pirata 9	Pirata 8	Pirata 7	Pirata 6
1 moneda	0 monedas	1 moneda	0 monedas	98 monedas

El pirata 6 necesita 3 votos para lograr pasar su propuesta, tiene su voto asegurado, eintenta obtener los votos de los piratas 10 y 8.
Nuevamente, si la propuesta del pirata 6 no es aprobada, pasaremos al caso d) en el cual los piratas 10 y 8 no optienen monedas. Como en la propuesta del pirata 6 los piratas 10 y 8 obtienen una moneda, mejor votan por a favor, con lo que se aprueba la propuesta.

f)
La propuesta es la siguiente:

Pirata 10	Pirata 9	Pirata 8	Pirata 7	Pirata 6	Pirata 5
0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	98 monedas

Por las mismas razones dadas anteriormente.

g)

Pirata 10	Pirata 9	Pirata 8	Pirata 7	Pirata 6	Pirata 5	Pirata 4
1 moneda	0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	97 monedas

h)

Pirata 10	Pirata 9	Pirata 8	Pirata 7	Pirata 6	Pirata 5	Pirata 4	Pirata 3
0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	97 monedas

i)

Pirata 10	Pirata 9	Pirata 8	Pirata 7	Pirata 6	Pirata 5	Pirata 4	Pirata 3	Pirata 2
1 moneda	0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	96 monedas

j)

Luego, la mejor repartición que el pirata con la barba mas larga puede proponer para su propio beneficio, es:

Pirata 10	Pirata 9	Pirata 8	Pirata 7	Pirata 6	Pirata 5	Pirata 4	Pirata 3	Pirata 2	Pirata 1
0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	1 moneda	0 monedas	96 monedas

Taran.