Skip to main content

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. :) *

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

Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"


Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:
1)
(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Source:
Sent to me by Gaurav Sinha

Problem:
Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?