My Teachers Job Interview Question
My maths teacher - who used to work for google - got this interview question. He presented it to us like this:
There are 100 pirates and 100 coins. They're deciding how to split it. This is their system: the lowest ranked pirate proposes they share all the coins equally. The pirates then vote "Ay" or "Nay". If half or more vote "Ay" then the motion is passed. If not then the lowest ranked pirate walks the plank and the second-lowest ranked pirate will propose they share it equally between the remaining 99 of them. This continues until finally a motion is passed. How many pirates will die before they reach a conclusion?
For example: If it were to reach the highest two ranking pirates then the conclusion would be inevitable. The captain - would presumably - vote "Nay" whereas the second ranking pirate would vote "Ay" as he doesn't wish to die. Therefore since a 50% majority vote "Ay" the loot would be divided.
Clarification - All pirates wish to gain as much loot as possible - The captain's vote is not worth more than his crew - The pirates cannot form alliances - The pirates are perfectly logical, but would rather survive than win more gold
The answer is 36.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Consider the following pirate's moods:
"I wanna maximize my profit" => mood is greedy green.
"I don't wanna die!" => mood is cautious orange.
"Guys! Please, be logical!" => mood is desperate red.
"I'm dead" => mood is hopeless black.
Let's see how these moods distribute with a growing number of pirates until we find the pattern...
2 pirates: 1 2 Motion passed!
3 pirates: 1 2 3 1 and 2 can safely play greedy. Last pirate dies.
4 pirates: 1 2 3 4 Pirate 3 h a s to vote "Ay" and save pirate 4. Otherwise, he dies in the following turn. Motion passed!
5 pirates: 1 2 3 4 5 1 through 4 can safely play greedy. Last pirate dies.
6 pirates: 1 2 3 4 5 6 Same situation. 1 through 4 can safely play greedy. 6 dies now and 5 dies in the next turn.
7 pirates: 1 2 3 4 5 6 7 Once again, 1 through 4 can safely play greedy. 5 through 7 are doomed and they know it.
8 pirates: 1 2 3 4 5 6 7 8 Pirates 5 through 7 h a v e to vote "Ay" and save pirate 8. Don't forget they are pefectly logical, they know what's coming! Motion passed!
9 pirates: 1 2 3 4 5 6 7 8 9 ...
Now you are ready to convince yourself that the following pirates that get their motions passed are 16, 32 and 64. Since the game starts at 100, the first pirate to get his or her motion passed and survive is 64. The remaining 3 6 of them (65 to 100) are doomed and they all eventually walk the plank.