0

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.

bobble
  • 10,245
  • 4
  • 32
  • 80
lost
  • 51
  • 4
  • 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. – lost Aug 07 '21 at 09:21
  • 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 – bobble Aug 07 '21 at 14:22
  • 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. – lost Aug 07 '21 at 22:57
  • 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. – Florian F Aug 09 '21 at 11:39

0 Answers0