[net.math] Splitting Candy Bars

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