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. :) *
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.
youngest ko 3rd oldest thieve ko kuch bhi dene ki jaarurat nahi hai.Ek khud ka bhi vote milega.
ReplyDelete@Jaadu...
ReplyDeleteThanx..... So, that would make it 996... but some sites are telling answer is 998... no solution provided though..
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" .
ReplyDeleteIf 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.
This is a standard problem. Here's the solution with a good explanation
ReplyDeletehttp://en.wikipedia.org/wiki/Pirate_game
@PD:
ReplyDelete3rd 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!!
@Maoo..
ReplyDeletemacha 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
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.
ReplyDeleteSo, youngest, i.e I can go away with 997 coins. :)
ladayi mat karo answer 996.5 maan lo
ReplyDelete@Jaddu... tatti mat pheko.....
ReplyDelete997 answer :)
badhiyaan junta
Question will be can the youngest one vote or not? and what is majority exact half or more than half?
ReplyDeleteMost 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