Problem #09 - greedy pirates

Enunciado: o Capitão Jack Girão foi o pirata mais perigoso do século XV. Ele, e a sua tripulação de 9 piratas desdentados, pilhavam todos os navios que navegavam nos seus mares. Para além de terem um raciocínio lógico perfeito, os piratas eram todos um pouco sádicos! Sempre que tinham oportunidade gostavam de atirar um colega pirata borda fora para ir nadar com os tubarões. Para além disto, todos os piratas adoravam ouro. Certo dia o Capitão Jack Girão e a sua tripulação saquearam um navio onde encontraram 30 moedas de ouro. O Capitão Jack Girão, perigoso mas democrático, convocou uma assembleia para distribuir as moedas. A assembleia convocada tinha as seguintes regras:

1. O Capitão propõe que as moedas sejam distribuídas de uma certa maneira e todos os piratas a bordo votam se aprovam ou não.
2. Se pelo menos metade dos piratas aprovar, a distribuição é feita. Se não, o Capitão é atirado borda fora, o pirata mais velho a bordo passa a ser o Capitão e voltamos para 1.

Que distribuição deve o Capitão Jack Girão propôr para que não seja atirado borda fora e para maximizar as suas moedas?

Solução: se a tripulação tem 10 piratas, uma proposta só é aceite se tivermos 5 ou mais votos a favor. Podemos assumir que o Capitão Jack Girão nunca vota contra si próprio, portanto teremos de fazer com que mais 4 piratas votem em aprovar a distribuição. Se não oferecermos uma única moeda a um pirata, esse pirata vota contra nós para nos mandar borda fora, logo temos de gastar pelo menos uma moeda com cada um desses 4 piratas cujo voto queremos comprar. Isto significa que o Capitão Jack Girão nunca conseguirá ficar com mais de 26 moedas no final; o que mostramos de seguida é que existe uma proposta que faz com que o Capitão fique exatamente com 26 moedas.

O tipo de raciocínio a fazer deve ser indutivo: vamos ver o que acontece para uma tripulação com os 2 piratas mais velhos, depois com os 3 piratas mais velhos, com os 4 mais velhos, e por aí fora. Para facilitar a explicação do raciocínio, suponhamos que os piratas, por ordem decrescente de idades, são o Capitão Jack Girão, o Alves, o Bruno, o Carlos, o Dias, o Esteves, o Fausto, o Gustavo, o Henriques e o Inácio
2 piratas (Capitão Jack Girão e Alves): como só há dois piratas a votação da assembleia fica ganha com um único voto. Deste modo, se o Capitão Jack Girão propuser a distribuição $(30, 0)$ (30 moedas para si, 0 moedas para o Alves) ele pode votar a favor, que independentemente do que o Alves votar, a distribuição é aceite.
3 piratas (Capitão Jack Girão, Alves e Bruno): notemos primeiro que são precisos 2 votos a favor para uma proposta ser aceite, o voto do Capitão e mais um de outro pirata. Se o Capitão Jack Girão for borda fora, só sobram os piratas Alves e Bruno, e nesse caso o pirata Alves consegue ficar com as 30 moedas para si. Sabendo isto, o pirata Alves vai votar contra a distribuição do Capitão Jack Girão, a não ser que ele lhe ofereça as 30 moedas. No entanto, o Bruno também sabe disso: se o Capitão Jack Girão for borda fora, não vai conseguir uma única moeda porque o Alves não lha vai dar. Assim, se o Capitão Jack Girão propuser a distribuição $(29, 0, 1)$ (29 moedas para o Capitão, 0 para o Alves e 1 para o Bruno) conseguimos comprar o voto do Bruno: se ele votar contra, então em vez de 1 moeda ele passa a receber 0 moedas, que é uma coisa que ele não quer; afinal de contas os piratas adoram ouro.
4 piratas (Capitão Jack Girão, Alves, Bruno e Carlos): notemos primeiro que bastam 2 votos a favor para uma proposta ser aceite, o voto do Capitão e o de outro pirata. De novo, se o Capitão Jack Girão for borda fora, então só ficam o Alves, o Bruno e o Carlos a bordo, e qualquer um deles sabe que a distribuição que vai ser proposta pelo Alves é $(\underline{}, 29, 0, 1)$ (o Capitão foi borda fora, 29 moedas para o Alves, 0 para o Bruno e 1 para o Carlos) que vai ser aceite, pelo que vimos no parágrafo anterior. A proposta que fazemos é então $(29, 0, 1, 0)$. Tanto o Alves como o Carlos votam contra, mas o Bruno vota a favor porque se não o fizer, e mandar o Capitão borda fora, na próxima ronda com 3 piratas ele não ganha uma única moeda.

Seguindo este raciocínio, vemos que as propostas mais gananciosas que podem ser aceites são:

5 piratas: $(28,0,1,0,1)$
6 piratas: $(28,0,1,0,1,0)$
7 piratas: $(27,0,1,0,1,0,1)$
8 piratas: $(27,0,1,0,1,0,1,0)$
9 piratas: $(26,0,1,0,1,0,1,0,1)$
10 piratas (tripulação toda): se propusermos $(26,0,1,0,1,0,1,0,1,0)$ então o Bruno, o Dias, o Fausto e o Henriques votam a favor já que se o Capitão for borda fora, na ronda com 9 piratas eles não ganham uma única moeda; mas os votos do Bruno, do Dias, do Fausto e do Henriques, juntamente com o do Capitão, perfazem um total de 5 votos, que é o mínimo necessário para que a distribuição seja aceite!

Para conluir, 26 era o número máximo de moedas que o Capitão podia aspirar a manter, já que teria sempre de gastar pelo menos 4 moedas com outros piratas. Por outro lado há uma distribuição que pode ser proposta, e que seria aprovada, em que o Capitão Jack Girão fica com 26 moedas, logo 26 é a resposta certa.

Deixem qualquer dúvida ou comentário na secção em baixo!

- RGS

Statement: Captain Jack Girão was the most feared pirate of the 15th century. He was accompanied by 9 toothless pirates and they pillaged every ship that sailed their seas. Besides having perfect logic reasoning, all the pirates were sadistic! Whenever they had a chance, they would throw a fellow pirate to the sea so they could watch him swim with the sharks. Besides that, all pirates loved gold. One day Captain Jack Girão and his crew pillaged a ship from where they took 30 gold coins. Captain Jack Girão, dangerous but democratic, summoned a meeting to distribute the recently acquired gold. The meeting he summoned had the following rules:

1. The Captain proposes a certain distribution of the gold coins and every pirate has to vote if they approve said distribution or not.
2. If half or more of the votes are in favour the proposed distribution takes place. If not, the Captain is sent to swim with the sharks, the most experienced pirate becomes the Captain and then the meeting goes back to 1.

What distribution should Captain Jack Girão propose in order to maximize his own profits and to keep his life?

Solution: if the crew is composed of 10 pirates in total, a proposal needs at least 5 votes to be accepted. We can assume Captain Jack Girão never votes against himself, meaning we only need to ensure 4 more votes. If we don't offer a single coin to a pirate he will vote against us, therefore we will need to spend some gold coins with the 4 pirates whose votes we want to guarantee. This means Captain Jack Girão will never be able to survive a proposal in which he keeps more than 26 gold coins; we will show that there is an accepted distribution where the Captain keeps 26 gold coins .

We will follow an inductive reasoning: we will see what happens when the crew is composed of 2 pirates, then what happens when we have 3 pirates, then 4, etcetera. To make the explanation easier, let us say that the pirates' names are, in descending order of experience, Captain Jack Girão, Abel, Bernard, Charles, Dickson, Esteban, Fabian, Gabe, Henry and Ian.
2 pirates (Captain Jack Girão and Abel): as there are only two pirates, one vote suffices to approve the proposal. Having said that, if Captain Jack Girão proposes the distribution $(30, 0)$ (30 coins for him and 0 for Abel), he can have his proposal approved regardless of the voting intention of Abel.
3 pirates (Captain Jack Girão, Abel and Bernard): we start by noting we will need two votes in favour, the one from Captain Jack Girão and another vote from another pirate. If Captain Jack Girão goes swimming with the sharks, only Abel and Bernard will be left on board, in which case Abel is able (no anagram was originally planned) to keep the 30 coins for himself. Being aware of this, Abel is going to vote against the proposal of Captain Jack Girão unless he proposes to give all coins to Abel. On the other hand, Bernard is also aware of that: if the Captain goes swimming with the sharks, Bernard will not be given a single gold coin as Abel will keep them all for himself. Equating all these reasonings together, we see that if Captain Jack Girão proposes the distribution $(29, 0, 1)$ (29 for the Captain, none for Abel and 1 for Bernard) Bernard will vote in favour: if he votes against, he will lose the only gold coin he had been offered and that is something he does not want; after all, pirates love gold.
4 pirates (Captain Jack Girão, Abel, Bernard and Charles): we start by noting two votes in favour suffice to approve the proposal: the vote of the Captain and another vote from another pirate. Again, if the Captain goes swimming, Abel, Bernard and Charles will be the ones left, and any of the three know that the distribution to be proposed by Abel will be $(\underline{}, 29, 0, 1)$ (the Captain is swimming with the sharks, 29 coins stay with Abel, Bernard gets none and Charles gets 1) and that proposal is going to be accepted, as we saw in the previous paragraph. What the Captain should propose is $(29,0,1,0)$. Both Abel and Charles will vote against, but Bernard will vote in favour otherwise he would be sending the Captain to go have a swim and then when the 3 pirates restart the meeting he will get no coins at all.

If we keep following this train of thought we see that the greediest distributions that get accepted are:

5 pirates: $(28,0,1,0,1)$
6 pirates: $(28,0,1,0,1,0)$
7 pirates: $(27,0,1,0,1,0,1)$
8 pirates: $(27,0,1,0,1,0,1,0)$
9 pirates: $(26,0,1,0,1,0,1,0,1)$
10 pirates (the whole crew): if the Captain proposes $(26,0,1,0,1,0,1,0,1,0)$ then Bernard, Dickson, Fabian and Henry will vote in favour, as voting against would mean that the Captain would go swimming and then in the meeting with 9 pirates they would get no gold coins; but the votes in favour of Bernard, Dickson, Fabian and Henry are enough: if we also account for the vote of the Captain, we get 5 votes in favour of the distribution, meaning it gets accepted!

Summing it up, 26 was the maximum ammount of gold coins the Captain could hope for, as he would have to spend at least 4 of them. On the other hand, there is a distribution where he gets to keep 26 coins, thus the answer is 26.

Please leave any questions or thoughts below!

- RGS