Difference between revisions of "TADM2E 2.52"

From Algorithm Wiki
Jump to: navigation, search
(Correct the answer for situation "b".)
(Corrected part b.)
Line 37: Line 37:
 
'''b.''' They want as many other pirates to live if it doesn't affect their outcome -  
 
'''b.''' They want as many other pirates to live if it doesn't affect their outcome -  
  
2 pirates: Senior gets it
+
Senior most pirate gets the gold.
 
 
3 pirates: Since a pirate will always vote along with another pirate's plan if he/she gets the gold (since you get the gold and want to maximize the number of pirates who live), the most senior pirate would give the gold to any of the remaining two pirates.
 
 
 
4 pirates: The same argument above is applicable here; thus the most senior pirate gives the gold to any of the other three pirates.
 
 
 
5 pirates: There will be at least 3 pirates (more than half) that don't receive the gold; and since each one would have greater than 0% chance of receiving the gold if the 2nd-most-senior pirate gets to decide (as described above), they would all vote to kill the senior most pirate. From here it becomes the "4 pirates" situation where one of the three least senior pirates will receive the gold.
 
 
 
6 pirates: The 2nd-most-senior pirate knows he/she is dead if he/she has to pick the pirate to receive the gold; thus he/she will always vote in favor for the most senior pirate's plan. To receive the last vote necessary to live, the senior most pirate can then decide to give it to any of the other 4 pirates (since that pirate will get the gold and maximize the number of pirates who live). Thus all pirates live and one of the 4 least senior pirates gets the gold.
 

Revision as of 01:41, 24 May 2017

This problem is a famous game-theoretical scenario called the pirate game (http://en.wikipedia.org/wiki/Pirate_game). Assume the senior pirate gets to vote.

Where there is only 1 indivisible dollar: 2 pirates - The senior pirate gets it. 3+ pirates - The least senior pirate gets it.

In general, every 2 + 2^K (k >= 1) pirate will survive, while the others will die

Another Answer : Assume senior pirate also gets to vote.

Based on pirates inherent tendency -

a. They want to kill other pirates even if it does not affect their outcome -

2 pirates: Senior gets it.

3 pirates: Least-senior pirate gets it because the 2nd-least-senior pirate will vote for kill; so in order to live, he/she must give the gold to the least-senior pirate.

4 pirates: 2nd or 3rd-least-senior pirate will get gold (equally likely) because 1st will vote for kill irrespective of whether he/she gets the gold or not, and the 2nd or 3rd-least-senior pirate will vote for the plan if he/she gets the gold respectively.

5 pirates - This pirate is certainly going to die regardless of his/her proposal since there will be at least 3 pirates that don't get the gold and thus vote to kill him/her. This will eventually lead to the above situation where the 2nd or 3rd-least-senior pirate will receive the gold.

6 pirates: The 5th-least-senior pirate will vote for whatever plan the most senior pirate proposes—if the proposal falls down to him/her, then he/she is guaranteed to die as explained above. In order to get the last vote, the most senior pirate can give the gold to any of the remaining four pirates. The reason for each is below—recall, the desire to have the gold surpasses the desire to kill another pirate (e.g., if Pirate A has a 50% chance of getting the gold without killing anyone vs. a 49% chance of getting the gold and killing everyone else, he/she will choose the former):

• 4th-least-senior pirate: would agree to receive the coin, because as mentioned before, if the 5th-least-senior pirate decides, he/she will die. This will eventually result in this pirate having to give away the coin in order to live as described in the "4 pirates" situation.

• 3rd-least-senior pirate: would agree to receive the coin since there would only be a 50% chance he/she would get it as described in the eventually inevitable "4 pirates" situation.

• 2nd-least-senior pirate: same reasoning as above.

• Least senior pirate: the least senior pirate would agree to receive the coin since he/she would have a 0% chance to receive the gold as described in the eventually inevitable "4 pirates" situation.

Thus the result would be that no one dies and either the first, second, third, or fourth-least-senior pirate would receive the coin.

b. They want as many other pirates to live if it doesn't affect their outcome -

Senior most pirate gets the gold.