wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> 5 pirate problem
        
(Message started by: birbal on May 28^th, 2008, 10:17am)

Title: 5 pirate problem
Post by birbal on May 28^th, 2008, 10:17am

Five pirates (of different ages) have 100 gold coins to divide amongst themselves. They decide on the following approach to determine how much each pirate receives:

The eldest pirate proposes an allocation. All pirates (including the eldest) then vote on the proposal. If the majority accept the proposal then the coins are divided in the way suggested. If not, then the eldest pirate is executed and the new eldest amongst the remaining pirates proposes a new allocation. If the votes are tied then this is enough for the proposal to be accepted.

Assuming that the pirates are motivated primarily by survival, then to a lesser extent by greed and finally to the least extent by sadism (i.e. they'd prefer to receive a gold coin and see someone get executed than just receive one coin earlier, but would prefer one coin to none and an execution; and obviously would prefer 0 coins and surviving to 100 coins and being executed), and act in a logical way, what is the maximum number of coins the eldest pirate can get?

Title: Re: 5 pirate problem
Post by towr on May 28^th, 2008, 11:02am

There's an earlier topic on it here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805318). And variation here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1091579834).

Maybe instead, we could look at 100 pirates trying to divide 5 coins ;)

Title: Re: 5 pirate problem
Post by QuantumAnenome on Nov 4^th, 2008, 1:44pm

It would seem all answers there are incorrect...
It was stated a tie is enough to accept a proposal, so 1 cannot kill 2.

Title: Re: 5 pirate problem
Post by towr on Nov 4^th, 2008, 2:01pm

on 11/04/08 at 13:44:23, QuantumAnenome wrote:

It would seem all answers there are incorrect...
It was stated a tie is enough to accept a proposal, so 1 cannot kill 2.

It was also stated that

Quote:

If the majority accept the proposal then the coins are divided in the way suggested. If not, then the eldest pirate is executed and the new eldest amongst the remaining pirates proposes a new allocation.

So the problem statement is self-contradictory.

Title: Re: 5 pirate problem
Post by chronodekar on Jun 24^th, 2009, 2:59am

If a majority vote is all it takes, then the eldest will need to appease 2 other pirates. And he can afford to ignore the other 2.

So that means 2 pirates do not get any money. Then 100/3 = 33.333...

Hmmm... That can possibly lead to an argument on who gets that extra coin. I propose this,

[hide]33 + 33 + 33 + 1 + 0[/hide]

as the way to split the coins. So the maximum number the oldest gets is [hide]33[/hide].

-chronodekar

Title: Re: 5 pirate problem
Post by towr on Jun 24^th, 2009, 3:13am

That does not take into account what would would happen if those two don't accept the current proposal. If they'd die (have whatever proposal they make rejected), they will have to accept this one no matter how bad it is.
The eldest pirate can get a much bigger share because of this.

Title: Re: 5 pirate problem
Post by chronodekar on Jun 24^th, 2009, 9:18am

on 06/24/09 at 03:13:16, towr wrote:

That does not take into account what would would happen if those two don't accept the current proposal.

I went under the assumption that the 2 pirates getting the smaller shares would not accept. The eldest only needs 2 other votes, right?

And I can't think of a reason why the other 2 getting [hide]33[/hide] would protest.

-chronodekar

Title: Re: 5 pirate problem
Post by towr on Jun 24^th, 2009, 3:36pm

on 06/24/09 at 09:18:54, chronodekar wrote:

I went under the assumption that the 2 pirates getting the smaller shares would not accept.

They'd be better off accepting 1 coin that rejecting that offer. So 33 is more than they deserve.

Consider it like this:
If there were one pirate, well, he won't vote against himself, so he could in that case keep everything.
If there were two pirates, the first would rather be in the situation where there were only one, but pirate number two can vote for himself, and in case of a tie the proposal carries. So he doesn't need to offer the younger pirate anything.
If there were 3 pirates, then all that's needed to get that extra vote is to offer the youngest pirate 1 coin, since that's better than what he'd get in the case where pirate number two takes everything.
Now if there were 4 pirates, then the fourth can get the second's vote for just one gold coin, because in the previous case pirate #2 got nothing, so he'll be better off accepting.
So if there are 5 pirates, pirates #1 and #3 should accept an offer of one coin, because the alternative is the previous scenario where they'll get nothing at all.

And so on until there are about twice as many pirates as coins.

Quote:

And I can't think of a reason why the other 2 getting [hide]33[/hide] would protest

Oh they won't protest, but they wouldn't protest if they got much less.

Title: Re: 5 pirate problem
Post by chronodekar on Jun 25^th, 2009, 3:17am

on 06/24/09 at 15:36:33, towr wrote:

Oh they won't protest, but they wouldn't protest if they got much less.

That makes a lot of sense. I think I "missed" the fact that if a proposal was rejected, the eldest gets executed. Going further along those lines, (executing the eldest if he never gave out anything)

Then, yes you'd better accept that 1 coin.

So, the eldest should be able to get away with [hide]98[/hide] coins!

Enlightened,
chronodekar

Title: Re: 5 pirate problem
Post by wolfiewolfie on Jul 20^th, 2009, 3:46pm

If he proposed "I get all of the coins and you three do not get executed"

Would he get 100 coins? I dont think they would disagree with not being executed. ;D

Title: Re: 5 pirate problem
Post by chronodekar on Jul 20^th, 2009, 7:16pm

on 07/20/09 at 15:46:16, wolfiewolfie wrote:

If he proposed "I get all of the coins and you three do not get executed"

Would he get 100 coins? I dont think they would disagree with not being executed. ;D

If that were all it took, then what pray tell is the point of the RIDDLE?

While it is not specifically mentioned in the question, I feel that making the "you get executed" parts of the problem non-bargain able makes the whole thing a lot more challenging.

Of course, this could just be me wanting to complicate things. :)

-chronodekar

Title: Re: 5 pirate problem
Post by Azgard on Jul 20^th, 2009, 7:22pm

on 07/20/09 at 15:46:16, wolfiewolfie wrote:

If he proposed "I get all of the coins and you three do not get executed"

Would he get 100 coins? I dont think they would disagree with not being executed. ;D

But they might question his logic of 1 against 3 in a fight...

Title: Re: 5 pirate problem
Post by wolfiewolfie on Jul 20^th, 2009, 8:03pm

Ok than, another perspective on the 'one man gets 100 coins' theory.

Being pirates, they would more than likley disagree alot. The eldest would make a proposal, the other 4 would disagree and he was executed.

The next eldest now becomes the eldest, and his proposal is shunted, and he is executed.

This would also happen with the third pirate, who had become the eldest.

This can now go 2 ways. The remaining two can split the coins 50 - 50, or the youngest can (intentionally) disagree with the eldest, causing him to be executed and the youngest, who is now the eldest, will get 100 coins, and have the pleasure of seeing 3 executions :)

Title: Re: 5 pirate problem
Post by Azgard on Jul 20^th, 2009, 8:15pm

on 05/28/08 at 10:17:14, birbal wrote:

If the votes are tied then this is enough for the proposal to be accepted.

wolfiewolfie:

Quote:

This can now go 2 ways. The remaining two can split the coins 50 - 50, or the youngest can (intentionally) disagree with the eldest, causing him to be executed and the youngest, who is now the eldest, will get 100 coins, and have the pleasure of seeing 3 executions :)

This makes no sense, the eldest would not disagree with himself because as long as he accepts his own proposal, he lives and gets whatever he puts forth in his proposal.

Title: Re: 5 pirate problem
Post by wolfiewolfie on Jul 20^th, 2009, 8:23pm

My apologies, I forgot about the tied part.

In that case, i stick to the first part of my last response and my answer is that the eldest can get a maximum of 50 coins :)

Title: Re: 5 pirate problem
Post by Azgard on Jul 20^th, 2009, 8:27pm

Nah, once it gets down to the last 2, the eldest, if he's smart, would say that he gets all the coins, all 100, and there is nothing that the youngest can do about it... Except hunt him down afterwards for the coins, of course... ;)

Title: Re: 5 pirate problem
Post by wolfiewolfie on Jul 20^th, 2009, 8:35pm

"if he's smart"

Remember we are talking about pirates :P

Title: Re: 5 pirate problem
Post by Azgard on Jul 20^th, 2009, 8:37pm

Okay, then substitute "greedy" for "smart".

Title: Re: 5 pirate problem
Post by wolfiewolfie on Jul 20^th, 2009, 8:38pm

Hahahaha, no, I think you hit the nail on the head.

With only 2 of them, the votes can either be:

for and against = tie = eldest gets 100 coins

or

for and for = eldest gets 100 coins.

I highly doubt it would be against and against.

Title: Re: 5 pirate problem
Post by Azgard on Jul 20^th, 2009, 8:44pm

You would hope not, anyway.