Combinatorics is one of the four fundamental branches of Mathematics in high school competitive math. Compared with number theory, combinatorics has a shorter history. Game theory is an important and fun part of combinatorics.
Today let’s look at a fun problem:
Five rational pirates discover 100 gold coins on the island. They are in strict order of seniority of A, B, C, D, and E. They decide to sit down and devise a distribution strategy. The most senior one chooses how to split up the gold and has the casting vote. All five pirates vote on whether to accept the distribution or not. If the majority accepts, the pirates live. If not, they killed the most senior one and the next one in line divides the gold instead. How many coins does private A end with?
The Answer is 98!
Did you get it right? Let’s see how it works.
Solution:
Since they are rational, they know the priority is to stay alive and then maximize the gold they can get.
First, let’s reduce the problem to 2 pirates. If D and E are left, D is senior to E. D would propose 100 for himself and 0 for E. E would have to agree, or he will both die. When two left, C:100, E:0.
Second, how about C, D, and E left? Since they are rational people, C knows that D will offer 0 to E. Therefore, C will win E’s vote if C offers E a coin. When three are left, C:99, D:0, E:1.
Then, if there are four left, B needs to get one more pirate to vote for his proposal. Pirate B realizes that D gets nothings according to C’s plan. If B gives D a coin, D will support him.
When four are left, B:99, C:0, D:1, E:0.
Last, with 5 people left, pirate A knows that he needs 2 more votes to get accepted. If A dies, C and E will get 0 according to B’s plan. He can bribe C and E each with 1 coin. Pirate A will propose, A:98, B:0, C:1, D:0, E:1.
Okay!
By using the same method, what if there is no seniority between the five pirates, will the answer be different?
Written by EG