Suppose 2 prisoners are given a pie by the warden. The prisoners need a procedure to ensure that each one, by his own action alone, can ensure at least his fair share. The solution is that one prisoner divides the pie in 2, and the other prisoner chooses a piece. If p1 divides precisely in half, then no matter how p2 chooses, he is ensured no less then half. If p2 chooses correctly, no matter how p1 cuts, he too is ensured at least 1/2.
So, what procedure could be followed by 3 prisoners so that each could guarantee by his own action(s) alone to get at least 1/3 of the pie?
I lost a lot of time on this one a few years ago but never figured it out. If anyone has a reference to where this problem appears I’d love to know it.
I might be breaking the “by his actions alone” clause with this one. Here is a go anyway.
First, each prisoner puts his name in a hat.
Next, each prisoner makes a single (radial) cut in the pie.
Third, the name of each prisoner is drawn from the hat randomly, and the prisoners select their slices in the order in which the names were drawn.
The idea is, no prisoner has an incentive to make a bigger piece, since their chances of ending up with the smallest piece would be equal to their chances with any other piece.
Of course, a prisoner could trust his luck and try to create an oversized piece, but it would be a zero-sum game. In this way my solution is inferior to the two-prisoner solution, in which cheating (creating an oversized piece) is always punished, unless the other guy doesn’t like pie.
Pass the pie around twice. The first time the prisoners each make a radial cut. The second time they select a piece of pie. As long as its the same order is followed both times, each should get one-third.
My math book from last semester, Excursions in Modern Mathematics, by Peter Tannenbaum and Robert Arnold, described three methods of dividing something fairly between three or more people, but none of them were as simple as the last two offered. I’m rather disillisioned
For two parties. I divide–you decide is fair.
For more than two:
P1 takes the knife and cuts what he thinks is a fair piece.
Each party in turn can pass (if he thinks the piece is fair or small) or take the knife and shave off some pie. The last party to take the knife gets the piece. P1 cannot complain if he gets the piece–he cut it. Nor can he complain if someone takes a smaller piece of it. The last one to shave off some cannot complain; if the piece is small, he it’s his own fault for not passing.
Repeat the procedure until two remain, then play divide/decide.
I just saw FortMarcy’s solution; The problem with that solution is if P2’s cut leaves the pie with a slice more than 1/3 but less than half, then P1 will get the bigger piece no matter what P3 does. That is, P3 might not be happy with the piece P1 gets.
I was working under the assumption that each prisoner would attempt to maximize the amount of pie he received. That way P2 would be shortchanging himself with a cut greater than 1/3.
The solution that I have heard is that you make one radial cut, then move the knife around the pie, in cutting position (as it were). At any point, anyone of the three can call “Stop”, at which point the second slice is made and the minor segment given to the person who called “Stop”. That person must be happy as they decided that the slice was a fair third before calling. The remaining 2/3 are divided in the “traditional” way, with one person cutting and the other choosing.
1st P1 and P2 cut the pie in half as in the OP
2nd P1 cuts his 1/2 in 1/3rds - P3 takes the 1/3 he wants
3rd H*O!
4th P2 cuts his 1/2 into 1/3rds - P3 takes the 1/3 he wants
For any number of prisoners: number them (P1, P2, p3 … PN). P1 cuts one portion, P2 cuts another portion, etc, all the way to P(n-1) who cuts the last portion making a total of n portions. Now, Pn chooses one portion, P(n-1) chooses the next, all the way back to P2 who has the last choice and P1 gets the last portion. This works for any number between 2 and 120.
“Excursions in Mathematics” is a neat book that addresses lots of interesting math problems like this one. Like JadedNaive said, there are 3 methods for solving this problem that are included in the book… k2dave described the “Lone Chooser” method… DrMatrix described the “Last Diminsher” method… Here’s the last one described in the book, called the “Lone Divider Method”. (What I like about these methods, is that if you make a poor cut, it ends up hurting you, not someone else.)
“Cutter” cuts pie into what he considers 3 equal pieces. He gets what’s left over, so he’ll be cutting fairly. “Charlie” and “Cheney” will do the choosing.
“Charlie” and “Cheney” write on a piece of paper which slice or slices each would not mind having (the ones each thinks are at least 1/3 of the pie.)
Case 1: Charlie chose (Pie1, Pie2) and Cheney chose (Pie1). Answer: Give Pie1 to Cheney, give Pie2 to Charlie, give Pie3 to Cutter.
Case 2: Charlie wants (Pie1, Pie2). Cheney wants (Pie1, Pie2). Answer: Give Pie3 to Cutter. Charlie and Cheney both should be happy with either Pie1, or Pie2.
Case 3: Charlie wants (Pie3). Cheney wants (Pie2). Give 'em what they want. Let Cutter have Pie1.
Case 4: Charlie wants (Pie1). Cheney wants (Pie1). Let Cutter pick Pie2 or Pie3, which should satisfy him. Charlie and Cheney must think that Pie2 and Pie3 are both smaller than 1/3 or they would have written it down. So they must think that the two pieces that they are left with are bigger than 2/3. Put the last two pieces together and use the “You-cut-I-pick” method to re-divide the pieces.
Every case is a variant on one of these (I think) and everyone gets a slice they are happy with.
I’m sorry but why do they have to be prisoners? Why not just three guys/girls? I guess prisoners are more likely to steal and thieve and try to get more pie. HA, I just answered my own question. It all makes sense now…
Some of the solutions so far cover the possibility of two prisoners ganging up on the third, trying to ensure that between the two of them they receive more than 2/3 of the pie. Some of them don’t. Does a solution have to cover this to be valid?
I actually read an article about this in Scientific American some years ago. You’re right about one thing: Speaking in a strictly mathematical sense, it’s guaranteed to work for any number of parties dividing something fairly finely divisible. (It’s a beter solution than any other in this thread in that regard).
However:
Practically speaking, some things cannot be divided in this way, either because there are irregular discrete units (say, N-1 diamonds, where nobody wants to powder the largest diamond as part of the “solution”) or because the adjustments result in wasted value (those diamonds again, or the litle shavings of pie that are going to result from lots of people adjusting things).
As a practical matter, for large N dividing a finite resource, the last person is going to be stuck with mostly “pie shavings” as his share. There are plenty of situation where this share is valueless: no amount of pie shavings is equivalent to a whole piece of pie. In these cases, deliberate avoidance of the final share (by all parties involved) is going to skew the sizing of the early shares in one way or another.
For more abstract problems, it works quite well, however, there are cases where your solution will be inadequate.
I think I just came up with an original solution that doesnt seem too complicated. Can anyone punch a hole in this?:
p1 cuts the pie into sixths.
<p1 guarantees 1/3 by making perfect sixths>
p2 designates the 2 smallest sixths.
<p2 guarantees he will get to choose half of the ‘biggest’ 4 sixths>
P3 takes the designated sixths or gives them to p1
<depending whether he thinks p2 chose wrong or right, either way he is assured he can get at least 1/3>
Now the 2 prisoners without pie (P2 and ??) do the 2-person procedure on the remaining 4 sixths, either by first amalgamating them into one, or doing cut/choose on each piece.
Not really. The prisoner with the knife has to sleep doesn’t he? And then there will be two hungry prisoners and one sleeping prisoner with a full pie inside him. You do the math.
