answers to the "related possible questions"

[jtfeng]

Hi, Mark:
The related possible questions in the answer section are really good, but there are no answers provided, and some of those related questions are equally hard and tricky. Since there is a high chance that the interviewer is going to task those related questions, will you provide answers to them?

[mj]

well it would triple the length of the book plus I think it's good for the reader to have some questions that he can't look up the answers to...

You can ask here about any question you are stuck on.

[anna]

Ok, here the unanswered question i got stuck with:
p290, bottom of the page: "6 pirates discover a treasure chest filled with 10000 gold coins..."
can you at least give a hint?

[mj]

it's a similar kind of backwards induction. i.e. what happens with one and then two...

It's pretty easy to find an answer with google for this one.

[anna]

i know it is backward, but i got stuck and can't move because i don't see my mistake:

if there is only one pirate, he got all money

if there are two, then they split 500/500, because otherwise they will never agree to anything ("the majority should be strict" meaning we need 2 vote to accept or kill the proposal)

if there are three, then the one making a proposal can leave himself 499 and let the other one (randomly chosen) has 501. in this case the randomly chosen one will vote in favor of the proposal, because if he kills it, he ll get only 500

if there are four, then the one making a proposal needs two more votes. he should give some money to first two pirates, but how much to give? both of them randomly getting 0 or 501... should he gave them 1 and 1, or should i calculate average payoff and give 1 coin more above it?

i got stuck.... if you have 5 minutes, help!

[mj]

if there are two, you would have to give everything to the other pirate since if he votes against, there is no majority and you die.

with three you can give one to the second pirate and keep the rest since this better for him than dying.

with four you can give two to the guy who gets one when there are three, and one to the one who gets zero and they will vote in favour so you have a strict majority.

Anyway, there is loads of discussion of this on the web:

http://www.google.com.au/search?q=pirate+split+treasure

[anna]

o! i see my mistake now!

you need majority to accept the proposal, but you don't need it to kill the proposal!
thank you! the rest of question is easy.

i know that there is a big discussion in web, but forum is much more convenient and give you time and opportunity to figure out where you were wrong, and this is much better for brains, then just reading solution from the web