I once received the following question on an entance test into a computer course. It was the only question I couldn’t answer. After I was accepted, I asked for the answer, but forgot it only a few hours later. Does anyone else know the answer? The question went like this:
When two children want to share a piece of food, a common procedure is for one of them to divide it into two supposedly-equal portions, and the other can choose whichever he wants.
With this system, neither child can complain of recieving the smaller piece. The first one can’t complain, because he signed off on their being equal. And the second can’t complain, because he had the option of choosing whichever he thought was the larger.
The question: How can this logic be adapted to allow THREE children to divide something so that none can complain of unfairness?
I read this answer somewhere, I believe the method is named after Conway and someone else, and is hence known as the ?-Conway envy-free division.
Assume three people, A B C and one pie.
A divides pie into three pieces and hands pieces to B.
If B thinks that one of the pieces is larger than the others, B can trim (at most) one piece to make (in B’s opinion) two pieces tying for largest. The three pieces are then handed to C (and the trimmings are discarded).
C takes a piece of their choice.
B takes a piece of their choice, except if a piece had been trimmed by B, and not taken by C, then it must be taken by B.
A gets remaining piece.
Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.
This of course precludes some sort of secret deal between two parties. Otherwize, A could cut e.g. an 80% piece and two 10% pieces; B picks the big piece and kicks back 35% of the original to A. A and B each get 45%; poor C is stuck with 10%
I didn’t mean “precludes”. I meant, “this of course would be messed up by the possibility of a secret deal; we must ban secret deals from consideration.” Beter?
I’ll just complete JRK’s explanation. After the three pieces are taken, the trim is divided using the same method and so on until what’s left is not worth trimming anymore.
Again, not “envy-free”.
Suppose A cuts three “equal parts”, P1, P2, P3.
B botches the job.
P1 is cut into two parts: P11 and P12.
P2 is cut into two parts: P21 and P22.
P3 is cut into three parts: P31 and P32.
Suppose P11 and P21 are bigger? Then C takes those, and A would “envy” C since C got more of the pie (in A’s estimation). The problem is to arrange it so that everyone has control of the portion which they inherit.
P.S. It’s not “JRK’s explanation”, but as I mentioned above, the Somebody-Conway 3-way envy-free division. I wish I was smart enough to come up with that answer! There are probably other methods.
Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.
Again, not an “envy-free” division. It’s a lot easier picking holes into a solution than finding the correct one!
A makes a cut, ending up (in A’s estimation) with 1/3 and 2/3.
Suppose B cuts the 2/3 piece, ending (in B’s estimation) in 1/3, 1/3 and 1/3. But A might not agree, and think the pieces are 1/3 (= 4/12, A’s original piece), 1/4 (= 3/12), and 5/12.
C then picks up largest piece, 5/12. A is left with choosing either 4/12 or 3/12, so A would “envy” C.
Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.
[quote]
I’ll just complete JRK’s explanation. After the three pieces are taken, the trim is divided using the same method and so on until what’s left is not worth trimming anymore.
[quote]
Thank you for the rectification. I had said “the trimmings are discarded”, which is probably not correct.
Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.
A cuts as close to one third out of the pie as he can.
B cuts the remaining two thirds into two thirds.
C picks first.
A picks second.
B picks last.
If A cuts more than a third, it will go to C and his peice will be too small.
If A cuts less than a third, B realizes this will end up his peice if it is smallest, so he would cut the remaining two thirds so that one of the slices was the same size as A’s slice. A and B would get small slices, C would cash in.
If A cuts even then B will get the smaller of the two peices that he cuts. So he will want to cut as close as even as possible.
The idea is not to make sure all thirds are equal, but rather to insure that an inequal cutting is to the detriment of the cutter.
Actually when no one is looking A will take the pie and eat it all. If someone is looking then A will kick the butts of B and C and still eat the pie, but this scenario gives A more of an appetite than does the first one.
Problem solved. A is full and happy and B and C are happy that they did not get beaten up worse.
That is the same method that Narile proposed above, and for the reasons mentioned above, is not an “envy-free” division. Depending on B’s cutting, C might get (in A’s opinion) a larger piece.
Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.
How about this… Individual A makes an initial cut from the center of the pie to the edge. A then holds the knife above the pie (tip of the knife abive the pie’s center) and slowly rotates it about the center point at a constant pace. Whenever someone (including A) says stop, their piece is cut at the knifes current position. The remaining pie could be divided using the previously described two-person method.
A cuts the cake in half.
B picks one. A gets the other.
C then cuts each of the others pieces into thirds and A and B each pick which 2 thirds of their original halves they want to keep. C gets the remaing two thirds.
A feels this is fair b/c A made the original cut to create two equal pieces and took the two pieces at the end.
B feels this is fair b/c B got to pick which half they wanted and B got to pick which two thirds they wanted.
C feels this is fair b/c they cut the two halves into what they thought were equal pieces so C should be happy with whatever two are left.