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.
- 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)
- How many prisoners will survive, and what is value that prisoner #1 can expect?
- 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.