Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Aug 23, 2009

Five Thieves and Bounty

Another puzzle from Krishnamurthy Iyer's website

Problem
Five thieves have just looted a bounty of 1000 gold coins. The loot has to be divided among them and therein lies the problem. It is then decided that the youngest one will come up with a strategy of division, and the rest will put the strategy to vote. If the strategy is voted with a majority, it will be accepted and will be carried out. Otherwise, the youngest one will be shot and the second youngest will be asked to do the same...and so on. So the problem is, if you are the youngest thief, what will be your strategy, to maximize your share of the bounty? (Assume all thieves have different ages.)

Thieves base their decisions on three factors. First of all, each thief wants to survive. Secondly, each thief wants to maximize the amount of gold coins he receives. Thirdly, each thief would prefer to throw another overboard, if all other results would otherwise be equal

Update (11/12/09):
Solution provided by Jaadu ... Better explanation by Maoo with arguments from PD
Solution:
Highlight the part between the * symbols for the answer.
* When there are only two thieves left, oldest would never accept anything offered by younger, so younger would anyway get killed. So, 2nd oldest would never let the third oldest get killed. So, whatever the 3rd oldest offers to oldest and 2nd oldest, it would be accepted. So, he would offer them nothing and 2nd oldest would have no choice but to support him. Since, this way, oldest and second oldest are not getting anything, they would prefer whatever the 4th oldest proposes. So, fourth oldest would give 1 coin to oldest, 1 to 2nd oldest and nothing to 3rd oldest. They will have no option but to support him. So, if the youngest child offers 2 coins to oldest, 0 to 2nd oldest, 1 coin to 3rd oldest and 0 coins to 4th oldest.. The oldest and third oldest thieves would support him.

So, youngest, i.e I can go away with 997 coins. :) *

10 comments:

  1. youngest ko 3rd oldest thieve ko kuch bhi dene ki jaarurat nahi hai.Ek khud ka bhi vote milega.

    ReplyDelete
  2. @Jaadu...
    Thanx..... So, that would make it 996... but some sites are telling answer is 998... no solution provided though..

    ReplyDelete
  3. You might want to rethink/amend the statement "rest will put the strategy to vote. If the strategy is voted with a majority, it will be accepted" .
    If such is the case, even the 3rd youngest (while proposing the strategy) wont be able to survive in any case.
    [Postulates:
    1. A thief is ready to accept a zero rather die.
    2. They vote strategically in order to reduce the no. of thieves alive. Therefore, say if a thief is getting the same share from two proposals he will vote in order to reduce the no. of thieves.
    3. (Deduction) The eldest will always vote NO.
    4. Majority here means votes in excess of 50%.
    ]
    Hence, when 2nd youngest proposes, 3rd and 4th youngest will accept a 0 and agree (majority). He gets all 1000.
    When the youngest proposes, to secure three Yays he needs to give away at least 3, one to each except 2nd youngest. So he's left with 997.

    Solution takes a different turn if the vote of the proposer counts in the majority. The answer will be 996 as jaadu suggested.

    PS: You can see that postulate 2 is inevitable, else the answer would be 1000.

    ReplyDelete
  4. This is a standard problem. Here's the solution with a good explanation
    http://en.wikipedia.org/wiki/Pirate_game

    ReplyDelete
  5. @PD:
    3rd is not a deduction....

    Oldest guy knows that if I am getting x and if I say no now, the next guy would not give me even x and it would be accepted because other would be giving yes to this guy. So, he would want to maximize his earnings and so, will not say no to all offers.

    Yes, the proposer also votes and majority means strictly more than 50%. Changed the language of the question to make it better.

    yo!!

    ReplyDelete
  6. @Maoo..

    macha rahe ho... dhanyawaad... So, that would mean answer is 996...

    Edit: Made it clear in the question now that each pirate would prefer to throw another overboard, if all other results would otherwise be equal

    ReplyDelete
  7. When there are only two thieves left, oldest would never accept anything offered by younger, so younger would anyway get killed. So, 2nd oldest would never let the third oldest get killed. So, whatever the 3rd oldest offers to oldest and 2nd oldest, it would be accepted. So, he would offer them nothing and 2nd oldest would have no choice but to support him. Since, this way, oldest and second oldest are not getting anything, they would prefer whatever the 4th oldest proposes. So, fourth oldest would give 1 coin to oldest, 1 to 2nd oldest and nothing to 3rd oldest. They will have no option but to support him. So, if the youngest child offers 2 coins to oldest, 0 to 2nd oldest, 1 coin to 3rd oldest and 0 coins to 4th oldest.. The oldest and third oldest thieves would support him.

    So, youngest, i.e I can go away with 997 coins. :)

    ReplyDelete
  8. ladayi mat karo answer 996.5 maan lo

    ReplyDelete
  9. @Jaddu... tatti mat pheko.....

    997 answer :)

    badhiyaan junta

    ReplyDelete
  10. Question will be can the youngest one vote or not? and what is majority exact half or more than half?
    Most of the site take exact half vote for majority like 2 out 4 is majority and youngest one can vote. With that if 2 are remaining youngest of both will take whole because he don't need oldest ones vote since his vote is with him. So oldest one won't get anything. split is from oldest to youngest of remaining
    3 are remaining -> (1,0,999) (+,-,+) 2/3 votes
    4 are remaining -> (0,1,0,999) (-,+,-,+) 2/4 votes
    all are there -> (1,0,1,0,998) (+,-,+,-,+) 3/5 votes
    gets 998

    if youngest cannot vote and 50% is majority
    2 remaining -> (1000,0) youngest die
    3 remaining -> (0,0,1000) (-,+) 1/2 votes. if 2nd don't support he dies
    4 remaining -> (1,1,0,998) (+,+,-) 2/3 votes
    all there -> (2,0,1,0,997) (+,-,+,-) 2/4 votes

    if more than 50% for majority and youngest can vote:
    2 remaining -> (1000,0) youngest die oldest won't agree
    3 remaining -> (0,1,999) (-,+,+) 2/3 votes
    4 remaining -> (1,2,0,997) (+,+,-,+) 3/4 votes
    5 remaining -> (2,0,1,0,997) (+,-,+,-,+) 4/5 votes

    if more than 50% for majority and youngest cannot vote:
    2 remaining -> (1000,0) youngest die
    3 remaining -> youngest die because oldest won't agree
    4 remaining -> (0,1,1,998) (-,+,+) 2/3 votes
    5 remaining -> (1,2,2,0,995) (+,+,+,-) 3/4 votes

    ReplyDelete