My wife likes puzzles. Here is one she asked me back when we were engaged.

It is a little appreciated historical fact that pirate ships usually had their own constitutions and laws. So lets take a case of a pirate vessel with 50 pirates on board. One day while approaching a safe harbour, they decide to split their ill gotten loot of 100 gold coins. According to their constitution, the treasure would be split by the senior most pirate, the Captain.

But there was another rule that said that if the pirates were disatisfied with the distribution, they could vote to kill the captian and appoint the next senior most pirate as the new captain. The new captain would again divide the treasure among them. For the overthrow to be successful, more than 50% of the pirates (including the current captain) had to be in favour of killing the sitting captain.

The pirates are greedy, rational and bloodthirsty. They are smart enough to anticipate what would happen if they killed the current captain and are bloodthirsty enough that if they feel their share will not increase, they would prefer to vote against their captain.

How should the captain distribute the gold so that he gets to keep as much gold as possible as well as his life?

.

.

.

.

.

Lets start at the very end.

Case 1: Suppose there are only 2 pirates left alive. Lets call them pirate 2 (senior) and pirate 1 (junior). Pirate 2, the senior one becomes captain and takes all the money and the junior one can do nothing.

Pirate 2 = 100

Pirate 1 = 0

Case2: Now if there are three pirates, with pirate 3 being the captain. Pirate 3 knows he needs 1 more vote (other than his own) to save himself. Pirate 3 will take 99 coins for himself and give 1 coin to pirate 1 and nothing to pirate 2. Pirate 1 will agree to this arrangement because he realises that if pirate 3 dies, pirate 2 will give him nothing (Case 1). So he would rather settle for 1 coin than that situation.

Pirate 3 = 99

Pirate 2 = 0

Pirate 1 = 1

Case 3: Now, if there are 4 pirates with pirate 4 as captain, then he will need at least 1 more vote (other than his own) to avoid death. So he will offer 1 gold coin to pirate 2 and keep 99 for himself. Pirate 2 will support him because he realises that if pirate 4 is deposed and pirate 3 becomes captain (Case 2), his share will go from 1 coin to 0.

Pirate 4 = 99

Pirate 3 = 0

Pirate 2 = 1

Pirate 1 = 0

Case 4: If there are 5 pirates alive with pirate 5 as captain, then pirate 5 needs 2 votes to stay alive. So he will keep 98 coins for himself and give 1 coin each to pirates 3 and 1. Pirates 3 and 1 will vote in his favour because if he is killed and pirate 4 becomes captain, they will get nothing (case 3).

Pirate 5 = 98

Pirate 4 = 0

Pirate 3 = 1

Pirate 2 = 0

Pirate 1 = 1

See a pattern emerging here? So if we go on like this and come to

Case 49: If there are 50 pirates with pirate 50 as captain, then he needs 24 more votes to save himself. So he distributes as follows. He takes 100-24 = 76 coins for himself. He gives 1 coin each to pirates 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48 (all the even numbered pirates). All these people vote for him because they realise that if he dies and pirate 49 becomes captain, then they will get nothing.

Advertisements
(function(g,$){if("undefined"!=typeof g.__ATA){
g.__ATA.initAd({collapseEmpty:'after', sectionId:26942, width:300, height:250});
g.__ATA.initAd({collapseEmpty:'after', sectionId:114160, width:300, height:250});
}})(window,jQuery);
var o = document.getElementById('crt-1872130908');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-1872130908",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-1872130908'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}
var o = document.getElementById('crt-1082265818');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-1082265818",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-1082265818'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}