Five pirates on an island have one hundred gold coins to split between them.

Additional material

[ Editor: a version given on "The Ultimate Puzzle Site: Brain-Teasers"
(R.P.T. van Gassel, C.E. Heijmans and E.R. van Veldhoven, 1996).  The
page linked to its solution on a separate page that is not in the
collected copy.  The same page also gave the three-door quiz of
decision/monty.hall. ]

A pirate ship captures a treasure of 1000 golden coins.  The treasure
has to be split among the 5 pirates: 1, 2, 3, 4, and 5 in order of
rank.  The pirates have the following important characteristics:

  * Infinitely smart.
  * Bloodthirsty.
  * Greedy.

Starting with pirate 5 they can make a proposal how to split up the
treasure.  This proposal can either be accepted or the pirate is thrown
overboard.  A proposal is accepted if and only if a majority of the
pirates agrees on it.

The Question: What proposal should pirate 5 make?

[ Editor: the solution page "Solution for: Pirate Treasure..." of The
Ultimate Puzzle Site (R.P.T. van Gassel, C.E. Heijmans and E.R. van
Veldhoven, 1996), for the 1000-coin version given above, converted from
HTML. ]

The idea behind the solution for this puzzle is that a pirate will
accept a proposal only if he knows that in case he would not accept the
proposal, he would get less of the treasure.

If pirate 1 would be the only one left, he would get all the golden
coins.  Therefore, if only pirates 1 and 2 would be left, pirate 2 has
to give all the 1000 coins to pirate 1 in order to stay alive; every
other proposal would be rejected by pirate 1.

                  |  Pirate 1  |  Pirate 2
  ------------------------------------------
  Number of coins |    1000    |     0
  ------------------------------------------
  Pirate agrees   |    Yes     |    Yes

When also pirate 3 would still be alive, he needs the agreement of one
of the other two.  Greedy pirate 2 will agree with every proposal in
which he gets more than 0 coins (if he wouldn't agree, he would get
nothing as we have seen).  So pirate 3 should propose to give one coin
to pirate 2, and keep the rest to himself.

                  |  Pirate 1  |  Pirate 2  |  Pirate 3
  -------------------------------------------------------
  Number of coins |     0      |     1      |    999
  -------------------------------------------------------
  Pirate agrees   |     No     |    Yes     |    Yes

When we have four pirates, pirate 4 should make two other pirates agree
with his proposal.  So he proposes to give one coin to pirate 1, two
coins to pirate 2, and the rest to himself.  Pirates 1 and 2 will accept
the proposal; if they wouldn't, they would get less.

                  |  Pirate 1  |  Pirate 2  |  Pirate 3  |  Pirate 4
  --------------------------------------------------------------------
  Number of coins |     1      |     2      |     0      |    997
  --------------------------------------------------------------------
  Pirate agrees   |    Yes     |    Yes     |     No     |    Yes

But as we know, there are five pirates.  If pirate 5 gives both pirate 1
and pirate 3 one coin more than in the previous case, they are willing
to accept the proposal.  Then a majority (three out of five) of the
pirates will support the proposal, and pirate 5 can keep the rest of
the treasure to himself.

                  |  Pirate 1  |  Pirate 2  |  Pirate 3  |  Pirate 4  |  Pirate 5
  ---------------------------------------------------------------------------------
  Number of coins |     2      |     0      |     1      |     0      |    997
  ---------------------------------------------------------------------------------
  Pirate agrees   |    Yes     |     No     |    Yes     |     No     |    Yes

Conclusion: Pirate 5 should propose to give two coins to pirate 1, one
coin to pirate 3, and the remaining 997 coins to himself.

-- The Ultimate Puzzle Site  (1996)

[ Editor: the same version was posted to rec.puzzles in May 1998: ]

Eric Farmer <efarmer@math.uiuc.edu> writes:

> I enjoyed this one, though I can't remember where I first saw it:

> Five pirates have stolen a treasure of 1000 gold coins, and need to
> divide it up among themselves.  Let's number the pirates by rank: 1,
> 2, 3, 4, and 5, with pirate 1 having the highest rank.  They decide
> to divide the treasure as follows:

> Pirate 5 makes a proposal as to how to divide up the treasure (i.e.,
> how many coins each pirate should get), and all the pirates vote for
> or against the proposal.  If a MAJORITY (more than half) of the
> pirates present (including pirate 5) accept the proposal, then the
> treasure is divided up accordingly.  Otherwise, pirate 5 walks the
> plank, and pirate 4 makes a proposal.  The remaining 4 pirates vote,
> and if a majority doesn't accept the proposal, pirate 4 walks the
> plank, and pirate 3 makes a proposal, etc.

> Each pirate is a perfect logician, and is very greedy, in the sense
> that s/he wants as much of the treasure as possible, and will vote
> FOR a proposal only if it means more money for his/her self than s/he
> would get otherwise.

> What proposal should pirate 5 make?

> Another minor variant: a pirate will vote for a proposal only if it
> means more money, OR if his/her life depends on it.

Work backwards.

Pirate 1 can get the whole treasure by voting against pirate 2.
Therefore, pirate 2 cannot get anything if it comes down to him.

Pirate 3 thus need only offer pirate 2 one gold piece to get pirate 2's
vote, and can keep 999 for himself.

Pirate 4 cannot get a vote from pirate 1, and must offer two gold pieces
to pirate 2 and 1000 to pirate 3, so he has no chance.

[ Editor: pirate 1 gets nothing under pirate 3's proposal, so one coin
does win his vote: pirate 4 can offer 1 to pirate 1 and 2 to pirate 2
and keep 997, as on the page above. ]

Pirate 5 must offer two gold pieces to pirate 2, and one to pirate 4,
and can keep 997 for himself.

(In the variant, pirate 3 need not offer anything other than life to
pirate 2, and pirate 5 must offer one gold piece to pirate 2 and
nothing to pirate 4.)

-- David Grabiner <grabiner@math.lsa.umich.edu>