I was asked this question in my second technical interview ever. I eventually got it with some help. I would argue the solution is non-obvious but feel free to disagree (i.e. call me dumb). The problem is stated as follows:
Five pirates dock and take stock of their treasure. They find they have 100 gold coins. They want to agree on a way to distribute the gold between them. They propose the following plan. One at a time, each pirate will take turns proposing a gold distribution between the five pirates. Then all the pirates will vote on that plan. If the plan wins with a tie or majority, then that plan is adopted and that will be how they distribute the gold. If the plan loses in the vote, then the pirate who suggested the distribution is killed and the next pirate will take his turn in suggesting a distribution. And so on until the pirates agree on a distribution. Assuming the pirates are perfectly logical and perfectly greedy, what is the final gold distribution?
The hint I needed from my eventual boss was “use induction.” Start with N = 1 pirates. This case is trivial. The sole pirate will keep all 100 gold coins because he is perfectly greedy. Consider the N = 2 case. The pirate whose turn it is to suggest a distribution can suggest any distribution he wants, because he knows he will vote ‘yes’ for that distribution, and since a tie or better is all that is needed to adopt the proposed gold distribution, the perfectly greedy and perfectly logical pirate will choose to give himself 100 coins and give the other pirate 0 coins.
With N = 3 is where it gets interesting. Call these pirates x, y, and z, with pirate x being the one who is currently proposing a gold distribution, and pirate y is next in case pirate x’s plan is rejected.
All the pirates, being perfectly logical, are well aware of the N = 2 case. Namely, that pirate y will get 100 coins and pirate z will get 0. Therefore, pirate z will vote ‘yes’ for any gold distribution which gives him at least 1 gold coin, because that would be better than the N = 2 case where he will get 0. Therefore, pirate x suggests that he get 99 gold coins, pirate y gets 0, and pirate z gets 1.
Now consider N = 4, with the pirates in order of their proposal turns being w, x, y, and z. All the pirates are aware of the outcome in the N = 3 case. Namely, pirate y is aware that he will get 0 coins if it comes down to N = 3. Therefore, pirate y will vote ‘yes’ on any plan that gives him at least 1 gold coin. Since all that is needed to make a proposed distribution be adopted is a tie or better, pirate w will propose that he get 99 gold coins, x gets 0, y gets 1, and z gets 0. Pirates w and y vote ‘yes’ and so the plan passes.
Finally, consider N = 5, and call the pirates v, w, x, y, and z. Pirate v is up to propose a distribution. Pirates x and z know that in the N = 4 case, they will get 0 gold coins. Therefore, they will vote ‘yes’ for any plan that gives them at least 1 gold coin. Knowing this, pirate v suggests that the gold distribution be: {<v: 98>, <w: 0>, <x: 1>, <y: 0>, <z: 1>}. Pirates x and z know that this is better than they can do in the N = 4 case and so they vote ‘yes’ along with pirate v. 3 votes to 2 means the plan passes, and that is our final distribution among the 5 pirates.
adhocery 