December 17, 2015

I can still remember when I was doing my first interview, I was asked a question like this: 5 pirates of different ages (A being oldest, B, C, D, and E being the youngest) want to split a fortune of 100 gold coins. The oldest pirate will propose a plan. If that plan is agreed by 50% or more pirates, then this plan goes effective; otherwise the plan is discarded and the oldest pirate gets killed. The process repeats in the remaining party of the pirates until a plan goes effective. Assume every pirate wants to maximize his own fortune without being killed, what will be the final plan, and how many coins can each pirate get?

This is a relatively tricky question. As I said always, there are several common techniques to target this kind of questions. For example: (1) For the case of N, start from the base case N = 1; (2) Think backwards. The question mentioned above requires both.

Case 1: Suppose E is the only pirate. He gets all.

Case 2: Suppose (D, E) want to split 100 coins. D can get 100 coins since he always approves his own plan. Although E will definitely disapprove, D gets 100, and E gets 0. (This plan is very bad for E!)

Case 3: Suppose (C, D, E) want to split 100 coins. Note that if C is killed, case 3 becomes case 2; however, E has to avoid case 2. So no matter how many coins C gives E (at least 1 coin), E will approve C's plan. So C may propose a plan where C gets 99, D gets 0, and E gets 1. (This plan is very bad for D!)

Case 4: Suppose (B, C, D, E) want to split 100 coins. Since B approves his own plan, it only requires 1 more pirate to approve B's plan. Note that D has to avoid case 3; so no matter how many coins B gives D (at least 1), D will approve B's plan. The final plan from B will be: B gets 99, C gets 0, D gets 1, and E gets 0. (This plan is very bad for C and E!)

Case 5: Suppose (A, B, C, D, E) want to split 100 coins. For the same reason, C and E have to avoid case 4; no matter how many coins A gives to C and E, C and E will approve A's plan. So the final plan proposed by A will be: A gets 98, B gets 0, C gets 1, D gets 0, and E gets 1. This plan will be approved by A, C, and E.

Pirate game is a mathematical game well studied for many years. It is still interesting to see those kinds of questions during interviews.