Author |
Topic: HARD: GREEDY PIRATES (Read 41293 times) |
|
Frank Gevaerts
Guest
|
Greedy Pirates
I think this should be solved in reverse order :
1 : his proposal will of course be accepted
2 : Since 1 can always make a better proposal himself, he will reject this one. Therefore, 2 needs to make sure anm earlier proposal is accepted
3 : Because 2 will not survive his own proposal, he will accept any proposal that 3 makes, even if he gets nothing. 1 is irrelevant. 3 will therefore propose to keep all coins for himself
4 : Since 3 can get a everything proposal, he will reject this one. However, if this proposal is rejected, 1 and 2 will get nothing. If 4 offers 1 coin each to 1 and 2, and keeps 998 coins, they will both accept.
5 : Since 1 and 2 can hope for only 1 coin each if 5s proposal gets rejected, they will support 5 if he offers them at least 2 coins each. The optimal proposal is therefore : 2 coins for 1, 2 coins for 2, 996 coins for 5.
|
| « Last Edit: Aug 28th, 2003, 6:27pm by Icarus » |
 IP Logged |
|
|
|
kul
Guest
|
 |
Re: HARD: GREEDY PIRATES
« Reply #1 on: Jul 25th, 2002, 11:19pm » |
 Quote  Modify
 Remove
|
The solution is that 5 will propose 998 for himself and 1 coin each for 3 and 4. If this proposal is rejected, 3 and 4 cannot get anything as 1 and 2 can reject all proposals and finally accept 500 coins each. Note that majority is required for accepting a proposal.
|
|
IP Logged |
|
|
|
Frothingslosh
Guest
|
|
Re: HARD: GREEDY PIRATES
« Reply #2 on: Jul 26th, 2002, 12:09am » |
Quote Modify
Remove
|
kul:
The solution is that 5 will propose 998 for himself and 1 coin each for 3 and 4. If this
proposal is rejected, 3 and 4 cannot get anything as 1 and 2 can reject all proposals and
finally accept 500 coins each. Note that majority is required for accepting a proposal.
No, I think Frank is right. The 500/500 split is certainly wrong, as if 2 ever proposes it (or
anything else, even giving all the coins to 1!) he will be killed by the bloodthirsty 1 and
not able to get a majority - 1 gets to keep everything and kill 2 if 2 makes any proposal.
While you said 3 can't get anything as 1 and 2 can reject all proposals, 2 can't reject 3's
proposal and live. If 3 walks the plank, 2 does also! I wanted to find a solution where 3, 4
and 5 agree, maybe with 5 even getting everyhing and 3 and 4 agreeing to save their lives,
but 3 is smart and knows that 2 is smart enough to have to agree with anything 3 proposes,
so 3 will not make a deal with 5. Strangely, the pirates were not quite smart enough to
know better than to set up this way of splitting the loot in the first place!
|
|
IP Logged |
|
|
|
kul
Guest
|
Frothingslosh: you are right! I was wrong about 1 and 2 sharing! Cannot think straight at 1 am.
However, the solution is:
5 proposes 2 coins for either 1 or 2, 0 coin for 3 and 998 for himself.
The reasoning is:
Going backwards:
2 Proposes: 1 rejects;
3 Proposes: 0 for 2 and 1000 for himself; 2 keeps life
4 proposes: 1 for 1 and 2 and 998 for himself. ( 1 and 2 do better here than in 3's proposal).
5 proposes: 2 for either 1 or 2, 0 for 3, and 998 for himself.
what is better for them in this than in 4's proposal:
1 or 2 gets 1 more coin.
3 gets to live.
|
|
IP Logged |
|
|
|
kul
Guest
|
Actually it is :
2 for 1 or 2 and 1 for 3, and 997 for 5.
The reason is 3 lives even if 4 proposes, so he has to do better in 5's proposal.
|
|
IP Logged |
|
|
|
mebden
Newbie
Posts: 6
|
|
Re: HARD: GREEDY PIRATES
« Reply #5 on: Jul 27th, 2002, 10:45am » |
Quote Modify
|
Yes I think that's it, kul.
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: HARD: GREEDY PIRATES
« Reply #6 on: Jul 27th, 2002, 6:15pm » |
Quote Modify
|
I read the problem differently, with a different idea in mind for what "proposal" meant. I read it as any procedure for dividing the treasure. For example, I thought that 5 could make a proposal including something like "1 and 2 flip a coin to determine who gets it". Then everyone votes. No wonder I couldn't find a unique solution!
That aside, there is another more serious problem with the question: the pirates have two conflicting goals. They are both bloodthirsty and greedy. Are they more bloodthirsty than greedy, or the reverse?
Let's look at 4's proposal, under which both 1 and 2 get a coin each. 3 will definitely reject it. If 1 and 2 accept it, they don't get to kill anyone. Is one lousy coin enough to buy off their bloodthirstiness? I wouldn't have thought so.
In order for kul's solution to work, the pirates have to value a single gold coin above the pleasure of tossing someone overboard. The problem doesn't say whether that's true or not, so we can't know whether it will work.
|
|
IP Logged |
|
|
|
Nathan
Guest
|
Tim, great post. I was laughing out loud reading it.
|
|
IP Logged |
|
|
|
Fluffy
Guest
|
Close, everyone, but no cigar.
NOTE: this solution implies that the puzzle DOES have a single solution, and that we CAN determine the answer from the information given. (I'm assuming that this is implied for ALL puzzles).
First, we need to construct a behavior model for the pirates. We know exactly three facts about them;
a) Infinitely intelligent
b) greedy
c) bloodthirsty.
From a, we can imply three things; first, that any given pirate will always make the choice that will maximise his gains. Second, a pirate will never make an incorrect choice. Third, every pirate knows everything that every other pirate knows. (Corollary: every pirate knows all of the above facts).
Greedy simply means that they desire gold, bloodthirsty means that they desire the death of other pirates. As a previous poster said, we do not know which is the greater desire, greed or bloodthirst. Therefore, let's assign the value B to represent the amout of pleasure a pirate gets from another pirate's death. B is measured in gold coins, since there are no other standards of measurement.
We know that B is not 0, since that would mean that the pirates are _not_ bloodthirsty after all. We know that B is not greater that 1000, since that would result in every single proposal being rejected, rendering the puzzle moot.
So, B is 1000 or less. Since we are assuming that the problem is solvable, we can conclude that B is so small as to be statistically insignifigant, since a signifigant number would represent a datum we do not possess, making the problem unsolvable. Yes, this assumption could be considered circular logic; let's just assume it isn't. 
As most people have reasoned, pirate 1 will simply propose he gets all the gold, which will suceed. Thus, no matter what pirate 2 proposes, 1 will vote no and it will fail.
Most people said that pirate 3 will propose 1000 gold for himself. However, if he does, 2 WILL VOTE NO! Why? Bloodthirst! If he votes yes, he gets no gold and sees two pirates die; if he votes no, he gets no gold and sees three deaths (four if you count himself!) Yes, it's odd that a pirate places no value on his own life, but if he did the rules should have said so. Therefore, 3 will propose 999 gold for himself and 1 for pirate 2. 2 will vote yes, making it pass. (remember, even one gold piece is worth more than any amount of deaths).
So, 4 will propose one gold for 1, two for 2, and 997 for himself. 1 and 2 will vote yes, since both will be getting more gold than they would otherwise, making the proposal pass.
Therefore, 5 should propose 2 gold for pirate 1, 3 gold for pirate 2, and 995 for himself. Again, 1 and 2 will vote yes, making it pass.
|
|
IP Logged |
|
|
|
Mark Ebden
Guest
|
Fluffy,
Interesting, that's clever. But I think this part is wrong:
"a pirate places no value on his own life ... if he did the rules should have said so."
 The rules DID say so, when they announced that the pirates are very intelligent. An intelligent person understands that his life has value and meaning to himself. I take that as a given, and most people would. It is common sense; I don't think the puzzle was meant to 'trick' us in such a trivial way.
If you are still skeptical, consider as well that the pirates are "greedy". You cannot have greed without a sense of self worth; that's because you don't aggrandize to help someone else, you do it solely to benefit yourself. Why? Because you believe yourself to be more important than others.
If the pirates were infinitely "financially-motivated", then MAYBE they would not value their own life. But because they are "intelligent", and for that matter "greedy", they do. Hence I think kul's answer earlier on is still correct.
Cheers,
Mark
|
|
IP Logged |
|
|
|
Frost
Newbie
Posts: 14
|
|
Re: HARD: GREEDY PIRATES
« Reply #10 on: Jul 28th, 2002, 7:12am » |
Quote Modify
|
How about this one:
The pirates are infinitely bloodthirsty, so no finite amount of coins can save a pirate's life. Each pirate knows they'll die if they get to propose, so they'll always agree. Pirate 5 takes all the coins.
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: HARD: GREEDY PIRATES
« Reply #11 on: Jul 28th, 2002, 3:20pm » |
Quote Modify
|
Frost: Quote:| "The pirates are infinitely bloodthirsty, so no finite amount of coins can save a pirate's life. Each pirate knows they'll die if they get to propose" |
|
No, pirate 3 knows that pirate 2 will accept his proposal out of self-preservation. (Or to put it another way, to avoid giving up all future killings)
Pirates 4 and 5 will always be outvoted by 1 2 3, all three of whom want to see them die.
If there were 7 highly bloodthirsty pirates, things would be different: 4 5 6 would know that they're doomed by 1 2 3, and so agree with 7 on anything.
Another interesting problem arises where the bloodthirst is of trivial value: Given that the treasure hoard consists of 1000 coins, and that any proposal must allocate an non-negative integer number of coins to each pirate, how many pirates can there be before the lowest-ranked pirate is thrown overboard regardless of what they propose?
|
|
IP Logged |
|
|
|
Frost
Newbie
Posts: 14
|
|
Re: HARD: GREEDY PIRATES
« Reply #12 on: Jul 29th, 2002, 2:11am » |
Quote Modify
|
The more I look at this riddle, the more solutions I get.
I even tried to design a new "infinitely bloodthirsty vampires" riddle, with the marketprice of a bucket of blood dropping when another vampire dies (less demand, more supply). Didn't work out though.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
|
Re: HARD: GREEDY PIRATES
« Reply #13 on: Jul 29th, 2002, 12:19pm » |
Quote Modify
|
on Jul 27th, 2002, 8:10pm, Fluffy wrote:
First, we need to construct a behavior model for the pirates. We know exactly three facts about them;
a) Infinitely intelligent
b) greedy
c) bloodthirsty.
...
We know that B is not 0, since that would mean that the pirates are _not_ bloodthirsty after all. We know that B is not greater that 1000, since that would result in every single proposal being rejected, rendering the puzzle moot.
|
|
I think the intended interpretation involves two assumptions:
* Pirates are primarily concerned with gold, but all else being equal, would rather see somebody die. That is, B=0.5. This should be stated in the problem.
* They value their lives above any amount of gold, as dead pirates sure don't keep their gold long. This is implied I think.
I believe this leads to the intended answer of:
997 for pirate 5
0 for pirate 4
1 for pirate 3
2 for pirate 2
0 for pirate 1
5 needs to win the votes of 2 pirates by making their share larger than what it would be if 4 decided things. Working out the cheapest way to do that (under the assumptions above) leads to this answer.
|
|
IP Logged |
|
|
|
Gamer555
Newbie
Posts: 19
|
|
Re: HARD: GREEDY PIRATES
« Reply #14 on: Jul 29th, 2002, 7:38pm » |
Quote Modify
|
Sorry if I missed anything! I feel yall are very good at coming up with solutions...
Do any of you feel we need to come up with seperate solutions (like if bloodthirstiness beats greed, and so on) because it seems like now we are solving 2a + b = 5 and we can't come up with one solution... Hmmm...
PS: Just say so if I am wrong (I am sure i missed something) but wouldn't 3 turn down the recent request? ("I believe this leads to the intended answer of:
997 for pirate 5
0 for pirate 4
1 for pirate 3
2 for pirate 2
0 for pirate 1")
If 4's request gave anything but 0 coin for 3, he would turn it down, right? Sorry if i am not paying attention.
|
|
IP Logged |
|
|
|
Alex Harris
Guest
|
|
Re: HARD: GREEDY PIRATES
« Reply #15 on: Jul 29th, 2002, 8:22pm » |
Quote Modify
Remove
|
Yes it does matter whether greed or bloodthirst are more important, and how important survival is. I think survival > bloodthirst/greed seems most logical, but as for the ratio of bloodthirst and greed you could argue lots of different things.
srowen's answer is correct for his stated assumptions of survival >> greed >> bloodthirst. If 5's proposal gets voted down then 4 would propose 998, 0, 1, 1 so 3 would get nothing and he prefers the 1 gold he'd get from 5's proposal. The easiest general way to do these is just to build up from the bottom. What if there are 2 pirates, then add a third, etc.
A generalization: if survival is top priority, then after that each pirate you see die is worth k gold (break ties in favor of bloodthirst).
If k < 333:
5 proposes #1 gets 0, #2 gets 2k+2, 3 gets k+1, #4 gets 0, 5 gets 997-3k. (#1 and #2 are interchangable for this)
If 333 <= k < 500:
5 proposes #1 and #2 get 0, #3 gets k+1, #4 gets 999-k, #5 gets 0.
If 500 <= k < 1000
5 proposes #1 #2 and #4 get 0, #3 gets k+1, #5 gets 999-k
If k >= 1000
5 and 4 are doomed, 3 proposes 1000 for himself and wins.
Its a bit interesting the way it works out. 5 has to pay out more and more as k rises until he gets down to 0, but then at 500 he can make money again because he no longer has to pay off #4 who is doomed if it becomes his turn.
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: HARD: GREEDY PIRATES
« Reply #16 on: Jul 29th, 2002, 9:08pm » |
Quote Modify
|
For the 500 <= k < 1000 case:
I presume you meant that #1 or #2 gets k+1, since 3 isn't going to be bought off. If #5 dies, so does #4 and #3 gets 1000 coins + 2 deaths.
|
|
IP Logged |
|
|
|
klbarrus
Newbie
Posts: 29
|
|
Re: HARD: GREEDY PIRATES
« Reply #17 on: Jul 29th, 2002, 9:57pm » |
Quote Modify
|
I thought this puzzle sounded vaguely familiar, and did a search, finding "A Puzzle for Pirates" in the May 1999 issue of _Scientific American_.
The text adds a bit more info, that pirates enjoy throwing others overboard, but prefer gold coins instead. No pirate enjoys suicide either.
The explanation follows the "work backwards" reasoning that many have explored, and arrives at a slightly different answer (puzzle is slightly different, dividing 100 coins among pirates):
P1 and P3 get 1 coin each
P2 and P4 get no coins
P5 gets the remainder
Basically you get here by starting with 2 pirates: P2 says he gets all, and P1 gets none. P2's vote is good enough to carry, so the proposal is accepted. Add another pirate: P1 will support anything that results in more than nothing, what he got when P2 proposed. So P3 says 1 for P1, 0 for P2, rest for P3. With another pirate, P2 will vote for anything that gets him more than 0, so P1 and P3 get 0, P2 gets 1, P4 gets the rest. And so forth.
The pattern that emerges is the last pirate has to bribe every other pirate with a gold coin to get their vote.
The interesting part of the article in the magazine is what happens when there isn't enough money to bribe all the pirates - the original puzzle examined is something like divide 100 coins among 500 pirates. I won't mention anything further in case somebody wants to work on it 
So in summary, an answer (not the only one as evidenced by the discussion here) that fits with some additional assumptions about pirate behavior is:
P5 = 998 coins
P4 = P2 = 0 coins
P3 = P1 = 1 coin
And you get to that backwards:
2 pirates: P2 = 1000, P1 = 0, accepted with P2's vote
3 pirates: P1 = 1, P2 = 0, P3 = 999; P1 will vote as he gets more than he would if P2 decided
4 pirates: P1 = P3 = 0, P2 = 1, P4 = 999; P2 will agree as he gets more than he would if P3 decided
5 pirates: P1 = P3 = 1, P2 = P4 = 0, P5 = 998; P1 and P3 will agree as they get more than if P4 decided
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: HARD: GREEDY PIRATES
« Reply #18 on: Jul 29th, 2002, 10:16pm » |
Quote Modify
|
Doh. Wasn't paying enough attention when I did that. Good catch tim. I got so happy that we had the "interesting behavior" of 5 getting money again that I didn't properly check that. Sadly 5 has to pay off 2 or 1, but since they'll get to see both 4 and 5 die he won't have the cash to manage it.
At k >= 500 we get the same result as k >=1000. 4 and 5 die while 3 takes all the gold.
|
|
IP Logged |
|
|
|
mebden
Newbie
Posts: 6
|
|
Re: HARD: GREEDY PIRATES
« Reply #19 on: Jul 30th, 2002, 7:43am » |
Quote Modify
|
Thanks Klbarrus, that clears it up completely. The problem on William Wu's site now seems to be very likely modelled on the Scientific American puzzle - but there is of course one important difference: In Mr Wu's puzzle, "A proposal is accepted if and only if a majority of the pirates agrees on it."
According to dictionary.com, a majority is "a number more than half of the total". The Oxford English Dictionary agrees, defining a majority as "a number which is more than half the whole number."
So we have to make a few adjustments on Scientific American's answer, which requires merely 50.0% for acceptance, instead of a majority.
We end up deriving kul's answer above (scroll way up!):
2 coins for 1 or 2, 1 for 3, 0 for 4, and 997 for 5.
What a neat puzzle.
Cheers,
Mark
 [font=Verdana][/font]
|
|
IP Logged |
|
|
|
Erit
Guest
|
|
Re: HARD: GREEDY PIRATES
« Reply #20 on: Jul 30th, 2002, 3:09pm » |
Quote Modify
Remove
|
if pirate 4 knows what pirate 5 WILL do and he knows he will get nothing. Why doesn't he propose 1 for himself and 499 for pirate 1 and 500 for pirate 2. That way pirate 5 would have no way of appeasing pirate 2 without making pirate 1 mad (without pirate 5 getting nothing) and vice versa, so he'll give 1 to pirate 3 (who had nothing) and 2 to pirate 4 (who now has one more) who will agree because they get more than before and pirate 1 and 2 will get nothing. If I were pirate 4 that's what I would do. (Hey it beats getting more than zero!) Am I wrong here or am I making sense? Actually, can't pirate 4 give himself even more up to a certain point? Because as long as he doesnt give himself more than what pirate 1 and 2 are getting each, pirate 5 will have to bribe pirate 3 with 1 (that's all thats needed to bribe) and bribe pirate 4 with one more than what pirate 4 proposed for himself. Because pirate 5 wouldn't bribe 1, 2 with more money since he'd lose more money himself so he'd have to settle with bribing pirate 3 and 4. So in this case:
Pirate 4 proposal:
1) 334
2) 334
3) 0
4) 332
5) 0
1 and 2 will definitely accept this since its a lot more
(then again if they know what then pirate 5 will do and they will get nothing then will they deny this??)
so then pirate 5 would do the smart thing and bribe 3 and 4 as to give himself more money
1) 0
2) 0
3) 1
4) 333
5) 666 (its the devils question I knew it! 
does this make any sense?? I dunno! im at work and bored to heck! ahhhhhhh hehe
This whole (I know what you're gonna do so here's what I'm going to do but you knew that already so this is what im going to do but...) is really confusing me. It's like that one guy in The Princess Bride =P Because if you're dealing with this with one pirate first then two pirates then three.. up to five and if each pirate is indeed infinitely smart they will know what the next pirate(s) will do and use some sort of scheme to at least get SOMETHING. No infinitely smart pirate would allow himself to get zero without somehow giving himself one and giving the rest to others at least. Or are we just assuming here that the pirates don't know what will happen when an additional pirate is added? (but that defeats the question) Sigh.. ok my head hurts, let me know, thanks.
Eric
|
|
IP Logged |
|
|
|
Erit
Guest
|
|
Re: HARD: GREEDY PIRATES
« Reply #21 on: Jul 30th, 2002, 3:16pm » |
Quote Modify
Remove
|
Actually this can be applied to other pirates too to screw over other pirates from getting stuff. Im just applying it to the original situation thinking from pirate 4's position. =P
Eric
|
|
IP Logged |
|
|
|
hot dog samurai
Guest
|
 |
Re: HARD: GREEDY PIRATES
« Reply #22 on: Jul 30th, 2002, 3:21pm » |
Quote Modify
Remove
|
personally i think the pirates will kill each other regardless of what happens because they are pirates and that's what pirates do.
actually, pirates aren't exactly mathematicians, so during the 20 years it takes them to come up with a solution they will probably all die of scurvy.
|
|
IP Logged |
|
|
|
Mark Ebden
Guest
|
|
Re: HARD: GREEDY PIRATES
« Reply #23 on: Jul 31st, 2002, 3:15am » |
Quote Modify
Remove
|
Hi Erit,
Interesting, but a case of over-analysis. Since the puzzle says "Starting with pirate 5 they can make a proposal...", the unfortunate Pirate 4  cannot propose anything until Pirate 5 does. So, your statement about Pirate 4, "Why doesn't he propose 1 for himself and 499 for pirate 1 and 500 for pirate 2", doesn't apply, since this proposal cannot possibly be announced until AFTER Pirate 5 is thrown overboard. And, here's the most important part: IF/when Pirate 5 is thrown overboard, of course all the pirates know that Pirate 4 will NOT go ahead and make the proposal above, no matter how much they thought he might previously. Instead of giving all the coins away to his cap'n and first mate, he will change his mind at the last minute and keep most of the coins for himself (as per kul's solution above) because he is greedy and he CAN.
So yeah, to keep this problem soluble, we have to assume the pirates make no deals or alliances with each other, no hand-shaking, nudges or winks. Otherwise, a near-infinity of solutions explodes.
Cheers,
Mark
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: HARD: GREEDY PIRATES
« Reply #24 on: Aug 1st, 2002, 9:03am » |
Quote Modify
|
Re: tim's msg:
First, to clarify the principles of the original problem, the priorities of the pirates are, in order:
1) Preserve your own life,
2) Maximize your number of gold pieces, and
3) Kill as many pirates as possible.
Although kul's answer is the correct one for this formulation of the problem, I like your idea of generalizing to probabilities (btw, for some reason I recall the true original problem leaving out the survivorship priority, so that the answer comes out uniquely as (2/0/1/0/997) -- if anyone recalls please let me know). Unfortunately, allowing probabilities doesn't make the problem significantly harder in this case; the answer just becomes (2 delta/0/delta/0/1000-3delta), where delta is the smallest probability the pirates can simulate, and 1 and 2 are interchangeable as before.
Oh well.
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print