wsp (10/20/82)
We all know that the best way to divide a candy bar between two people is to have one break it in what he thinks are equal pieces and have the other choose which of these equal pieces she wants (or vice versa). But what if you have three people? Once, after he had given a colloquium at the University of Michigan, Michael Rabin remarked that there existed an algorithm which would allow any number of people to share a heterogeneous substance in such a way that everyone got an equal amount of what they wanted. He left without telling the answer. I have thought long and hard about this, using it as my insomnia reliever, and have no solution. But I am not very good at these types of problems. Does anyone have the solution, a solution, or even a good idea? It seems to me the operating principle is that everyone has to feel its in his/her best interest to deal fairly and for there to be an implicit penalty for not acting fairly. Peter Benson ittdcd-west
luigi (10/20/82)
The problem has been presented a long time ago by Martin Gardner, together with the solution. The algorithm is iterative, and needs to be repeated until convergency. The first person takes a piece of cake, that he believes to be of appropriate size. All the remaining persons, one at the time, take away portions from the piece to reduce it to their idea of appropriate size. The portions go to a common pool. Then the same thing is done with the second person, and so on. When all persons are taken care of, the algorithm is restarted with the common pool. It is pretty obvious that this should satisfy everybody, except those who consider excessive fragmentation of the cake a degrading factor. Luigi Semenzato/HP Labs
luigi (10/20/82)
Whoops! I forgot an important part of the algorithm! The last person who takes away a portion from the piece of cake, is the one who gets it.
coltoff (10/20/82)
When I was in grade school (all those many years ago) the question was how to split 6 apples among 7 people. A simple question and a good way to learn fractions. My solution to the problem was to make applesauce. Can something similar be done with the candy bar? Not afraid to squash my name .ps 6 Joel Coltoff lime!burdvax!coltoff
sher (10/23/82)
If candy bars are infinitely divisible and people are infinitely patient then there might be (I don't fully trust myself in this kind of problem) a simple recursive solution. The recursive step is as follows: Assume that the candy bar has already been cut into m pieces and there are k people left. The first person in the queue breaks every piece into k subpieces. The second person in the queue picks m of the subpieces and gives it to the first person. Now the second person becomes the first and you recurse. of course the candy gets cut into N! pieces. -David Sher
mat (10/25/82)
I recall reading about this in Sci. Am. a couple of years ago -- Martin Gardeners column. The Algorithm he presented was attributed to John Horton Conway, and operated as follows: Any person takes the knife, and places it at one end of the Snickers bar. He slowly moves it toward the other end. At any time, one of the people ( including the cutter ) may yell 'CUT', and take for himself the piece that gets cut. If the cutter is the one who takes the piece, he turns the knife over to someone else, otherwise the yeller simply goes away and eats his piece. Is this the same problem, or have I missed something? -Mark Terribile hou5a!mat