Author |
Topic: Elegantly Greedy Pirates (Read 9573 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Elegantly Greedy Pirates
« on: Aug 3rd, 2004, 5:37pm » |
 Quote  Modify
|
This is a cute puzzle sent to me by Mark Newheiser via e-mail. It was originally written by some student at Mark's alma mater, the Rose-Hulman Institute of Technology. I believe I've worked out the solution (hopefully correctly) and it is quite satisfying. Here is the puzzle:
ELEGANTLY GREEDY PIRATES
"You have 1000 pirates, who are all extremely greedy, heartless, and perfectly rational. They're also aware that all the other pirates share these characteristics. They're all ranked by the order in which they joined the group, from pirate one down to a thousand.
They've stumbled across a huge horde of treasure, and they have to decide how to split it up. Every day they will vote to either kill the lowest ranking pirate, or split the treasure up among the surviving pirates. If 50% or more of them vote to split it, the treasure gets split. Otherwise, they kill the lowest ranking pirate and repeat the process until half or more of the pirates decide to split the treasure.
The question, of course, is at what point will the treasure be split, and what will the precise vote be?
After that, consider solving the problem when a two-thirds or three-fourths majority is required. Then you can easily generalize the result."
Note: For those of you who have already solved the chestnut Greedy Pirates riddle from the hard section, you may find this very easy. However, this problem strikes me as being more elegantly designed. (I made up the title.) Also, give a chance to riddlers who have not seen the pirates problem before 
|
| « Last Edit: Aug 3rd, 2004, 6:12pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
 |
Re: Elegantly Greedy Pirates
« Reply #1 on: Aug 3rd, 2004, 5:56pm » |
Quote Modify
|
Does "heartless" also mean that they do not have any instinct of self-preservation? How much do they value their lives in terms of a fraction of the loot?
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Elegantly Greedy Pirates
« Reply #2 on: Aug 3rd, 2004, 6:15pm » |
Quote Modify
|
I think heartless just means they don't care how many of their comrades die, as long as they optimize the amount of loot they receive in the end. As far as valuing one's own life, when I worked it out it seems that the two goals of staying alive and maximizing income are actually one and the same. You either get a fraction (the same amount for everyone), or you end up dead.
|
| « Last Edit: Aug 3rd, 2004, 6:16pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Elegantly Greedy Pirates
« Reply #3 on: Aug 3rd, 2004, 7:03pm » |
Quote Modify
|
Thenwhat is the point of mentioning the treasure at all?
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Elegantly Greedy Pirates
« Reply #5 on: Aug 3rd, 2004, 7:23pm » |
Quote Modify
|
Ok I see your point now. One could say that each pirate just wants as many deaths as possible, excluding the death of himself. But for what rationale? I guess they'd have to be truly misanthropic pirates with insatiable lust for blood. At least the treasure factor gives some reasonable rationale.
|
| « Last Edit: Aug 3rd, 2004, 7:24pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Elegantly Greedy Pirates
« Reply #6 on: Aug 3rd, 2004, 7:51pm » |
Quote Modify
|
If we define greed as "I'd rather die than receive less than X of my share", where 0 < X <= 1 and each pirate's share is defined as 1/n, where n is their rank, then the puzzle becomes quantifiable. And if we define extreme greed as greed with X = 1, then the answer is obvious ( 2 ).
If we equate heartlessness with bloodthirst and define extreme bloodthirst the same way as the greed, the answer is the same.
But if we add the self-preservation into the equation and consider that in case of the extreme greed the killing, once started, does not stop until it reaches the answer above, then the answer is 1000, and the first 500 vote to kill. I see no other way for the killing to start but to stop mid-way, unless the "greed coefficient" is specified.
|
|
IP Logged |
|
|
|
asterix
Guest
|
|
Re: Elegantly Greedy Pirates
« Reply #7 on: Aug 3rd, 2004, 8:39pm » |
Quote Modify
 Remove
|
I suspect that 512 will survive to split the loot.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Elegantly Greedy Pirates
« Reply #8 on: Aug 3rd, 2004, 8:57pm » |
Quote Modify
|
Asterix, your answer could be justified if everyone knows his rank but does not know the total number of pirates, and decides on the cutoff number regardless of the actual total.
But as everyone knows that the total is 1000 in advance, your reasoning (as I understand it having passed through the same hypothetical answer) does not work.
|
| « Last Edit: Aug 3rd, 2004, 8:57pm by Leo Broukhis » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Elegantly Greedy Pirates
« Reply #9 on: Aug 4th, 2004, 12:44am » |
Quote Modify
|
::
Pirates one and two won't ever die, so they'll vote no untill they're the only two left (in which case #1 votes to kill #2, but #2 votes not to, and since he's 50% survives)
#3 would die if he stood alone, so he'll vote to keep #4 alive as well, together #3 and #4 make up 50% of the top4 and can always survive. Which means they can just vote to kill of everyone else.
#5,6,7 need each other and #8 to get 50% of the votes, and so they'd always survive and thus vote to kill everyone else.
etc
The first 512 will vote to kill everyone else, but the 488 left can't get 50% of the votes to save themselves, so they die, and only 512 survive.::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Elegantly Greedy Pirates
« Reply #10 on: Aug 4th, 2004, 3:50am » |
Quote Modify
|
Sorry i am new around here and dunno how to start a new post but i have a question,
what is the highest power of 2<1000?
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Elegantly Greedy Pirates
« Reply #12 on: Aug 4th, 2004, 9:33am » |
Quote Modify
|
on Aug 4th, 2004, 12:44am, towr wrote:::
#5,6,7 need each other and #8 to get 50% of the votes, and so they'd always survive and thus vote to kill everyone else.
etc
The first 512 will vote to kill everyone else, but the 488 left can't get 50% of the votes to save themselves, so they die, and only 512 survive.:: |
|
Hmm... now I cannot remember what consideration did not let me lock to this answer. Maybe it was all that bloodthurst and infinite greed talk (in which case #500 needs #1000 to guarantee survival), but they do not seek blood in particular, they are just greedy (in a rational way) and heartless.
asterix, I take my previous comment back.
|
| « Last Edit: Aug 4th, 2004, 9:43am by Leo Broukhis » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Elegantly Greedy Pirates
« Reply #13 on: Aug 4th, 2004, 9:58am » |
Quote Modify
|
on Aug 4th, 2004, 3:50am, TenaliRaman wrote:Sorry i am new around here and dunno how to start a new post but i have a question,
what is the highest power of 2<1000? |
|
It's not. It is the highest power of 2 <= 1000.
Anyway, asterix's answer and and towr's explanation are what I came up with last night before falling asleep. And you don't need to know the starting number of pirates.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Elegantly Greedy Pirates
« Reply #14 on: Aug 4th, 2004, 10:37am » |
Quote Modify
|
Nice explanation, towr! I worked from the ground up too.
For k greedy pirates, you would expect 2[log(k)/log(2)], where [n] is the integer part function, pirates to remain.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
BigCow
Guest
|
|
Re: Elegantly Greedy Pirates
« Reply #15 on: Aug 4th, 2004, 11:29am » |
Quote Modify
Remove
|
Hey guys, I'm the guy who sent in the riddle, glad you liked it.
For me, it was a textbook problem come up with a student from my school to illustrate recursion, starting from simpler cases and working up to more general ones.
Needless to say, if Pirates of the Caribbean is any indication, this kind of strategy wouldn't be all that useful in real life. Human decision making rarely follows strictly logical backwards induction.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Elegantly Greedy Pirates
« Reply #16 on: Aug 4th, 2004, 1:07pm » |
Quote Modify
|
Thanks for sharing it with us, Mark. I certainly enjoyed working on it.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Elegantly Greedy Pirates
« Reply #17 on: Aug 5th, 2004, 4:43am » |
Quote Modify
|
So how about the proposed generalisation: N-1 out of N pirates need to vote for a split; more than 1/N of the pirates voting against splitting gives a corpse?
If anyone wants to take it further, finding an elegant form for situations where a different proportion of the pirates need to vote in favour to split the treasure is a little more challenging (sufficiently so that I haven't put in the work for it yet)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Elegantly Greedy Pirates
« Reply #18 on: Aug 5th, 2004, 5:28am » |
Quote Modify
|
on Aug 5th, 2004, 4:43am, rmsgrey wrote:| So how about the proposed generalisation: N-1 out of N pirates need to vote for a split; more than 1/N of the pirates voting against splitting gives a corpse? |
|
This shouldn't be too hard, it's much like the first problem, but with N instead of 2..
So ::for k pirates the highest power of N <= k will survive, or N[log(k)/log(N)] where again [x] is the integer part function::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Elegantly Greedy Pirates
« Reply #19 on: Aug 5th, 2004, 7:34am » |
Quote Modify
|
I've still not solved it completely, but I get a different result to you, towr. 
If we extend it to the full generalisation, where m/n pirates must vote for a split, otherwise the lowest rank dies, we gain a useful insight into the nature of the whole problem...
We shall assume, as before, that no pirate would vote for his own death just to spite a higher ranking pirate.
Suppose that 2/3 is the required proportion.
If 3 pirates remained, 2 must vote with 3 for a split, otherwise, after 3 had been killed, 1 would not vote with 2 to give the required 2/3.
As pirates 1-3 have this security, given the choice they will not vote for anyone else to survive. We shall call 3 a secure number.
Clearly, the next secure number will be obtained by increase the previous secure number (3) by an amount such that the new members constitute 2/3 of the whole group.
In general for a required proportion m/n, we can see that the previous secure number, x, must increase by an amount, y, such that the new members constitute m/n of the whole group:
y=(m/n)*(x+y)
ny=mx+my
y(n-m)=mx
y=mx/(n-m)
Hence the next secure number, x+y=x(m/(n-m)+1).
So for a required proportion of 1/n, the multiplier will be n/(n-1), not n.
However, I am having difficulties finding the mininum number.
Let M(m/n) be the mininum secure number (exluding 1) for a required proportion of m/n.
In general, M(1/n)=2 and M((n-1)/n)=n, but for values in-between I have not been able to generalise.
Any ideas?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Elegantly Greedy Pirates
« Reply #20 on: Aug 5th, 2004, 7:45am » |
Quote Modify
|
on Aug 5th, 2004, 7:29am, Sir Col wrote:| I've still not solved it completely, but I get a different result to you, towr. |
|
you do?
Quote:| Suppose that 2/3 is the required proportion. |
|
So 2/3 = (N-1)/N, or N=3
Quote:| Clearly, the next secure number will be obtained by increase the previous secure number (3) by an amount such that the new members constitute 2/3 of the whole group. |
|
In other words the group gets three (N) times as big (provided it stays lower than the total number of pirates)
Seems suspiciously much like the answer I got..
Quote:In general for a required proportion m/n, we can see that the previous secure number, x, must increase by an amount, y, such that the new members constitute m/n of the whole group:
y=(m/n)*(x+y)
ny=mx+my
y(n-m)=mx
y=mx/(n-m)
Hence the next secure number, x+y=x(m/(n-m)+1). |
|
Not necessarily, you needn't be dealing with whole numbers.
Suppose f.i. only 1/3rd of the pirates need to vote in favour of splitting. You'll need to round up.
The safe numbers in this case would be
1,2,3,5,8,12 etc
|
| « Last Edit: Aug 5th, 2004, 7:46am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Elegantly Greedy Pirates
« Reply #21 on: Aug 5th, 2004, 8:44am » |
Quote Modify
|
Sorry, I thought you had generalised for 1/n; I missed the quote (don't ask me how) that you referred to: "So how about the proposed generalisation: N-1 out of N pirates need to vote for a split".
You're right about the non-integer values of x+y = x(m/(n-m)+1). I should have said, x+y = ceil[x(m/(n-m)+1)].
In fact, I just noticed that x(m/(n-m)+1), can be written as, x(n/(n-m)).
The problem is that is in the general case: m/n, it is not possible to extract the multiplier. That is, for a given secure number, xk, the next one, xk+1 = ceil[xk(n/(n-m))], and we can't write xk+1=c*xk in the general case.
Clearly for the specific case, (n-1)/n, xk+1 = ceil[xk(n/(n-(n-1)))] = ceil[xk*n] = nxk.
Is there anyway to fully generalise this?
|
| « Last Edit: Aug 5th, 2004, 8:46am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Elegantly Greedy Pirates
« Reply #22 on: Aug 10th, 2004, 7:08am » |
Quote Modify
|
I don't know if it goes anywhere, but I'd have thought looking at 2/5 and 3/5 as the simplest cases which aren't just 1/n or 1-1/n might offer some insight
|
|
IP Logged |
|
|
|
jermanis
Newbie
Posts: 1
|
|
Re: Elegantly Greedy Pirates
« Reply #23 on: Dec 31st, 2005, 11:18pm » |
Quote Modify
|
This is a great puzzle... can't say I've seen one quite like it before. This topic seems to be dormant, but I'm here to revive it.
I think the answer that has been presented here is a bit off. While 512 seems to be the prevailing opinion, I believe that it should be 511. Consider that pirate 256 needs to force a "no kill" vote to save his life. Even with the pirate count down to 511, he can force a treasure split with a vote of 256to 255.
|
| « Last Edit: Dec 31st, 2005, 11:19pm by jermanis » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Elegantly Greedy Pirates
« Reply #24 on: Jan 2nd, 2006, 3:19am » |
Quote Modify
|
on Dec 31st, 2005, 11:18pm, jermanis wrote:This is a great puzzle... can't say I've seen one quite like it before. This topic seems to be dormant, but I'm here to revive it.
I think the answer that has been presented here is a bit off. While 512 seems to be the prevailing opinion, I believe that it should be 511. Consider that pirate 256 needs to force a "no kill" vote to save his life. Even with the pirate count down to 511, he can force a treasure split with a vote of 256to 255. |
|
But does pirate #256 need to vote "no kill" before #257 dies?
| hidden: | | The result people have got for this problem is that each pirate will vote to kill until the number of pirates reaches the lowest number for which that pirate would survive - so pirate #1 will vote to "share" the treasure when he's the only pirate left, and vote to kill until then. Pirate #2 can save himself and get half the treasure by holding off until there are just two pirates left, so he'll vote to kill until then. Pirate #3 can't survive if there are only 3 pirates left, but when there are 4, both #3 and #4 can survive, so both will vote to share then, and to kill for larger numbers. Above 4, you have (at least) 4 pirates voting to kill at each stage - so you need (at least) 4 pirates to vote together to share for any of them to survive - which happens at 8 remaining - then treasure gets shared out at 16, 32, 64, 128 and 256 pirates remaining - so the first 256 pirates will all be voting for kills as long as #257 is still alive, so pirates #257-512 need each other's votes to survive. Pirates 513 onwards are out of luck because they can get at most 488 votes against 512 and end up dead. |
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print