Here's a fun one from the Rice math competition General test in 2008:
Four pirates are dividing up 2008 gold pieces. They take turns, in order of rank, proposing ways to distribute the gold. If at least half the pirates agree to a proposal, it is enacted; otherwise, the proposer walks the plank. If no pirate ever agrees to a proposal that gives him nothing, how many gold pieces does the highest-ranking pirate end up with? (Assume all pirates are perfectly rational and act in self-interest, i.e. a pirate will never agree to a proposal if he knows he can gain more coins by rejecting
it.)
Also, consider how the answer might be generalized to arbitrary numbers of pirates and gold pieces.
:P
ReplyDeleteHmm. An interesting initial suggestion.
ReplyDeletelol Thanks it was all I could think of after I got a short circuit when I read the question. You know, something popped in my brain and I smelled smoke.
ReplyDeleteWell, consider a simpler version of the problem. Suppose there are only two pirates -- the captain and the deck swab. The captain gets to make the first proposal. What should he propose?
ReplyDeletehe should propose that he gets all the money, because he's half the pirates so he agrees and the deck swab gets nothing. lol
ReplyDeleteRight. So now let's think about three pirates. It won't work for the captain to propose everything for him, because then the other two will definitely vote against him. He needs to get at least one of the other two to vote for his proposal. What's the minimum he has to offer to make sure he gets a vote?
ReplyDeleteIf I was the next pirate in rank, I would vote against it unless he gave it all to me, because if I voted against and the other guy voted against, then I would get to vote myself all the money next. But I guess the captain should give most of the money to himself and then a very little of it to the guy of lowest rank, assuming that this guy realizes that if he votes against it, and the captain walks the plank, then he won't get any.
ReplyDeleteOkay, so I'm thinking that with the 4 pirates, he still only has to give away one coin to the lowest ranking pirate, so he gets 2007 coins, because the lowest ranking guy won't get any more than that if he has the captain walk the plank.
ReplyDeleteHowever, Dad says that the pirate might be mad at the captain for being such a scum and keeping all that gold for himself, and vote out the captain's proposal so he gets both a gold coin and the satisfaction of seeing the evil captain walk the plank. So he thinks the captain should give him 2 gold coins. But I think he's missing the point. :)
Good. Let's go through the three pirate case carefully. We've got captain, first mate, and swab. The captain needs one of the other two to vote for him. What will it take to get the first mate to vote for him? Well, if the captain loses, the first mate gets everything. So there's nothing the captain can offer the first mate that's better than what he gets if the captain loses.
ReplyDeleteSo if the captain's going to get a vote, it'll have to come from the swab. Now, what's the minimum the captain can offer? If the captain loses, then the first mate takes everything and the swab gets nothing. So if the captain offers the swab even one coin, he'd do better voting for than against.
So the captain offers nothing to the first mate, and one coin to the swab, with the other 2007 for him. First mate votes against, swab votes for, and the proposal passes.
You're on the right track with the four pirate case, but it's a little bit more complicated than what you've got there.
okay, what you had for the 3 pirates is what I was thinking.
ReplyDeleteBut I don't really get the 4 pirate case yet. How is it more complicated? Because the captain still only has to get the swab to vote for his proposal, right? And if the swab has the captain walk the plank, then the next guy will still only give him one coin, since it would be back to the 3 guy situation. so he doesn't gain anything in the way of money by making the captain walk the plank if he only is offered one coin. Unless he has a really great desire to see the captain walk the plank.
Well, think about things from the point of view of the swab. Let's call the pirates A, B, C, and D, in rank order. If A's proposal is voted down, then B gets to make a proposal. It's now a three-pirate game, and we know how that's going to go: B will get 2007 coins, C will get nothing, and D will get one coin.
ReplyDeleteSo now suppose A offers 2007 to himself, nothing to B and C, and one coin to D. B and C will of course vote against that. Will D vote for it? Well, he knows he'll do just as well if he votes against it, and waits for B to make his offer. So maybe he'll vote for it, but he has no compelling reason to do so -- he could just as well wait. And that's not what A wants. A wants to be sure that his proposal will be accepted, because otherwise it's over the plank for him.
So what could A do to make sure his offer is accepted?
So I guess he gives D 2 coins because D probably knows that B will only give him one coin.
ReplyDeleteWell, that will work, but there's a more economical solution.
ReplyDeleteA gives one coin to C, and the rest to himself. Remember, if A's proposal is voted down, and it becomes B's turn to propose, B is going to offer one coin to D, and keep the rest for himself. So if A's proposal fails, C gets nothing. So as long as C gets at least one coin from A's proposal, he'll prefer it, and vote for it. That'll be enough, and A's proposal will pass.
ReplyDeleteSo, what happens if there are five pirates?
Oh, I should have thought of that, it makes sense.
ReplyDeleteWell if there are five pirates, the captain needs two other people to vote for it. So I'm thinking he has to give one to the third guy and one to the last guy. Because if he loses, the second guy will vote himself all the money except one, so he won't vote for anything the captain proposes. and the fourth guy can't be guaranteed to vote for the captain's proposal unless he's given alot because the second guy would be sure to give him something.
Right. The key idea here is that we use what we know will happen in the four-pirate case to think about the five-pirate case.
ReplyDeleteIn the five-pirate case, if pirate #1's proposal gets voted down, then #2 will give one gold coin to #4, and keep the rest for himself. So #3 and #5 know they're getting nothing if #1's proposal gets voted down. So as long as #1 gives each of them a coin, they'll vote for him.
Similarly for six pirates. If #1's proposal gets voted down, then #2 will give one coin each to #4 and #6, and #3 and #5 will get nothing. So #1 should offer one coin to #3 and one coin to #5.