0
$\begingroup$

During a mass prison escape, 1000 prisoners managed to break into a prison safe and steal 100 gold bars. Since all prisoners wear shirts with consecutive numbers from #1 to #1000, they decided to split that gold in following way:

  • the prisoner with highest number will propose split (starting with #1000), and all prisoners (including him) will vote for that proposal.
  • if majority voted for proposal, it is accepted and split is done. Otherwise, prisoner who proposed is killed, and next prisoner (#999...) make his proposal.

Assuming following:

  • all prisoners are highly intelligent, and are able to find optimal solution
  • gold bars are indivisible, so proposal must suggest integer number of gold bars to certain prisoners
  • 'majority' means more than half. Example 1: with 1000 prisoners 501 must vote yes (including prisoner who proposes). Example 2: with either 4 or 5 prisoners, prisoner who proposes need 2 additional votes.
  • prisoners have following priority: survive > profit > kill other prisoners (this means they will vote against proposal if they can expect same value in later proposals)

Question:

  1. How many prisoners will survive, and what is value that prisoner #1 can expect?
  2. What is formula for above two values, given arbitrary starting number of prisoners N and gold G?

For 2nd question, large N,G (> 10) can be assumed, to avoid special cases.

Improve this question
$\endgroup$
4
  • $\begingroup$ While it is similar question, it does not answer it. Answers there contain procedures (algorithm) that could be used here to find number of prisoners to survive ( although not expected value ), but there is no single/simple formula there that answers second question here. $\endgroup$
    – lost
    Commented Aug 7, 2021 at 9:21
  • $\begingroup$ The (implied) simple formula from the top answer there would be: find the largest number of pirates, less than or equal to the starting amount, that form a stable solution with the given number of gold coins. Then divide the coins in accordance with the stable solution plan, as outlined there. I don't think you'll get much simpler than that $\endgroup$
    – bobble
    Commented Aug 7, 2021 at 14:22
  • $\begingroup$ My problem #2 has single formula solution, in a form : nSurvivors(N,G)= ... , also expectedValue(N,G)=... - and those single formulas are, arguably, much simpler than what you mentioned. $\endgroup$
    – lost
    Commented Aug 7, 2021 at 22:57
  • $\begingroup$ Actually the pirate version is different in the handling of ties. It results in a different solution. For example pirate #4 needs 3 votes, he must propose a split like (2,1,0,97) to survive. This questions should not have been closed. $\endgroup$
    – Florian F
    Commented Aug 9, 2021 at 11:39

0

Reset to default

Browse other questions tagged or ask your own question.