Steve Landsburg, a mathematician and professor of economics, blogs at The Big Questions. The blog's position near the top of my daily read of hundreds of RSS feeds bespeaks the excellence of its content. Anybody who enjoys this blog would doubtlessly enjoy The Big Questions at least as much.
Today, Prof. Landsburg posted a mathematical puzzle said to have been given in Google job interviews:
\(n=10\) pirates seek to divide \(m=100\) indivisible pieces of gold amongst themselves using this method:
- The pirates have a known ranking of ferocity.
- The most ferocious pirate proposes a division of the gold and all the pirates vote on whether to accept it.
- If at least half of the pirates vote to accept the division, that is how the gold will be divided and the game ends.
- If the pirates reject the division, the most ferocious pirate is thrown overboard and the game continues with the reduced number of pirates at step 2.
- All pirates are perfectly rational optimizers and all pirates know that about all other pirates.
- Every pirate prefers to be alive to being thrown overboard.
- Between options that leave the pirate alive, the pirate prefers the one in which he receives more gold.
- Between options that leave the pirate alive and with equal amounts of gold, the pirate prefers the one in which as many other pirates as possible have been thrown overboard.
- How will the \(n\) pirates divide the \(m\) gold?
Though I may very well be wrong as Prof. Landsburg's puzzles often have a seemingly obvious, irrefutable, but wrong answer, I believe the following is correct.
Let a proposal be a sequence of the form \(\left\{ p_n,p_{n-1},…,p_1 \right\}\) with the condition that that all \(p_k\) be non-negative integers and \(\sum_{k=1}^{n}p_k=m\).
Let an acceptable proposal be a proposal that at least half of the \(n\) pirates will vote for.
Does an acceptable proposal always exist? Not clearly. But if we allow \(p_n\) to be negative (representing an unlimited kitty of other coins that most ferocious pirate could dip into to ensure that the proposal is accepted), then there must be at least one acceptable proposal for the most ferocious pirate could always offer some quantity of gold larger than what any pirate would otherwise receive.
Let an optimal acceptable proposal for every \(n\) be one which leaves the most ferocious pirate with at least as much gold as any other acceptable proposal.
Is there a unique optimal acceptable proposal every \(n\)? That is not clear in the general case. I believe so, if as specified ties go to the ayes, but not if ties go to the nays.
But if there were multiple optimal acceptable proposals, the problem would be ill-defined. One would not be able to predict from the rules which proposal the most ferocious pirate would pick. Assuming that the problem is well-defined, there must be a unique optimal acceptable proposal for every \(n\).
Let \(s_n\) be that unique optimal acceptable proposal for \(n\). This will be the definite outcome if the number of pirates ever reaches \(n\).
Now the question of which proposals are acceptable becomes tractable. Any pirate will vote for any proposal if and only if that proposal leaves the pirate with more gold than the definite, defined alternative \(s_{n-1}\). So to determine \(s_n\) all we need to do is find the proposal leaving the most ferocious pirate with the most gold that will also grant at least half the pirates at least one more coin than \(s_{n-1}\).
Given that if there was only one pirate, he would just take all the gold, we know that \(s_1=\left\{m\right\}\). Now we can code an iterative solution:
step s = takeFirst ((n+1<=) . (2*) . (1+) . length . filter id . zipWith (<) s . tail) pss
where
g=sum s
n=length s
pss=[p0:ps|p0<-[g,g-1..], ps<-splitNtoK (g-p0) n]
The solution for \(n\) pirates is then just (iterate step [100])!!n. This yields the following set of solutions, first proposed on The Big Questions by commenters Jonatan and Nawaaz.
It will be enjoyable to see if this is either correct or wrong in some devious way.
Update: Prof. Landsburg has now continued his posts on the problem, here and here (with lots of interesting comments), and revealed the hole in the proof of the solution above:
The error is the unstated assumption that every pirate will always vote for his preferred outcome. This is just the sort of commonsense, but false, assumption which leads so frequently to fallacies. This assumption is false because, if a pirate knows that his vote will not affect the outcome, there is no logical reason to predict that he will vote either way.
Yet, I contend that if we grant the weaker assumption that a pirate will vote his interest unless he can prove that his vote is meaningless (i.e., not decisive for the outcome), the above solution still holds. The proof needs only to change to note that indecisive votes are not predicted (but of course those are just the votes that do not need to be predicted to determine the outcome).
