Conference rusure::math

    How about having the first person make some cuts to divide the cake
    into a 1/3 portion and a 2/3 portion, then letting the second person
    vut the 2/3 person into two 1/3 portions, then letting the third person
    say who gets which pieces.

    	No.  If the first and third work together, the first cuts out
    a tiny 1/3 piece, and the second get a very small piece (since the
    third chooses)...
    
    Dave E
    

    re .0
    
    I could have sworn that this has been discussed in here before but I
    couldn't find it. Perhaps someone with a faster connection can.

    How about brute force: cut the cake in tiny pieces and let each person
    in turn take a crumble. Generalises to any number of persons.
    
    Seriously, I suspect that any solution would involve cutting the cake
    into more than three pieces.

    The first person cuts his or her piece.  The others, in turn, vote "OK"
    or "too big".  If everyone votes "OK", the first person takes his or
    her piece and the problem is reduced to N-1 people sharing a smaller
    cake via the same algorithm.
    
    Anyone who wants to can vote "too big" but then THEY have to take the
    piece of cake and cut it smaller AND be willing to accept the smaller
    piece of cake.  The others get to vote on this procedure as well, just
    as if that were the first person's first slice.
    
      John

    But if both people vote "too big", who has to take the piece?

When I was young and cruel to my brother, we had the following sort of
conversation (his name is Willie):

Mom:	o.k., now you two boys can share this candy bar.

Me:	o.k. Willie, here's half.

Willie:	Hey, your half is bigger !

Me:	<CHOMP!  as I bite off some>  More even now ?



/Eric

    I think I read about this problem in a Martin Gardner book...
    
    The solution there was that the first person cuts off a 1/N slice.
    The next person may either take that slice, or enlarge it.
    Eventually someone takes the slice (plus crumbs!), and we've
    reduced the problem to a previously-solved case...

    Well, if the second person enlarges that slice, wouldn't they be able
    to get as large a slice as they want?

    If they enlarge it, they don't get to take it (yet).

                                    Topher

    Well, my solution (.8) doesn't work if two are in league against
    a third:  One of them cuts a large slice and the other takes it
    before the third person has a chance to object.
    
    I like the procedure in .6 better.  One person cuts a slice, and
    we go around the table with each person permitted to shrink it.
    When we've gotten back to the start, the past person to touch the
    slice keeps it.  (Perhaps this is actually what I read long ago.)

    	Yes, .11 is the solution that seemed to suggest itself as
    simplest and fair to all participants.  For more than two
    participants this makes for potentially a few shavings,
    but I see no way to avoid that possibility.
    
    Thanks!
    Dave Eklund
    

    I still like .4... just mash the cake up into very little pieces and
    let each person take turns taking one crumb apiece (though who likes
    mashed cake?)

>                          -< Cutting the cake fairly >-

>    	Now, what is the generalization to three people?  How do you
>    divide a cake into three pieces so that all three parties are satisfied
>    as to the "fairness" of the distribution?

	This is an old problem, but I don't remember ever looking at it.

	(1) Ask A to cut off what he considers to be a third of the cake.
It is in his interest to be as accurate as possible, since he will not be
able to control whether he gets this piece or part of the remainder.

	(2) Ask B & C to say whether they consider this piece to be less than
or more than a third.   If both say that it's less than a third, then A will
get that piece, and B & C will divide the remainder in the usual way.   If B
says the piece is too small, while C says it's too big, then C gets that piece,
and A & B get to divide up the remainder.   We only have a complication in the
case where both B & C reckon the piece is too big.   Go to the next step only
in this case.

	(3) B takes the piece, which he has declared is too big, and cuts off
a sliver to reduce it to what he considers to be a third of total cake.   Add
the sliver to the remainder.   C now decides.   If C wants the reduced piece,
he has it, and A & B split the expanded remainder.   If C wants the expanded
remainder, he and A split it, whilst B gets the reduced piece.
    
	Whatever alliances may exist amongst the participants, each is
guaranteed to receive what he considers to be at least a third of the cake.

	The same principle will work with n > 3 participants.   Get one of
them to cut off a piece of (subjectively) 1/n.   Ask all the others whether
they think the piece is too small or too big.   We have complications exactly
when more than one person thinks the piece is too big.   Call those persons
the conflictors.   The others (together with the original cutter) will end up
with part of the remainder (possibly expanded), so they are happy.   Meanwhile,
ask one of the conflictors to trim the piece.   Ask the other conflictors
what they think.   Again, there's only a problem when more than one wants the
reduced piece.   Pick one of these intransigent conflictors, and ask him to
trim the reduced piece, etc...

	This process will end, because the number of participants is finite.
Eventually, we find there is no conflict for the iteratively reduced piece.
Either no-one wants it (in which case the most recent trimmer gets it) or one
person wants it (in which case he is welcome to it).   Either way, the
remaining n-1 participants then hunker down to divide the iteratively expanded
remainder, and each is happy that this portion contains at least (n-1)/n of
the original total.

Andrew.

This all reminds me of one of my old puzzles:

	I eat half a cookie and hand the rest to you.  You eat half off what's
	left and hand the rest to me.  I eat half of what's left and hand
	the rest to you.

	We continue until the remaining crumbs are too small to worry about.

	Approximately how much of the cookie did I eat and how much did you
	eat ?

The boring way to solve this is to say:  I ate 1/2 a cookie and handed 1/2
to you.  You ate 1/4 and handed 1/4 to me.  I then ate 1/8 etc. so I ate

	1/2 + 1/8 + 1/32 ...

The "aha!" way to solve the problem is:  In round 1, I eat 1/2 and you eat
1/4.  In round 2, I eat 1/8 and you eat 1/16.  Hence in every round, I eat
twice as much as you.  Hence I ate twice as much cookie as you, so I must
have eaten 2/3 and you 1/3.

I like the fact that this quickly shows us that

	1/2 + 1/8 + 1/32 ... = 2/3.

It seems like a neat way to easily show the infinite sum without using the
usual math tricks or memorized formulas.

/Eric

Allow me to reply to an old topic...

How about this way ?  Just apply following rule repeatedly.  And it can be 
enhanced for n persons easily.

Rule: Who cuts earlier, gets the piece later.

For three persons:
(1) X tries to cut 1/3 piece out.  If he failed, he would get the smallest
    one.
(2) Y tries to devide the larger piece to two 1/2 pieces.  If he choose 
    smaller piece, he'll get a part of smaller piece.  So Y tries larger 
    one.  Y also tries to devide the pieces to two 1/2 pieces of it of course.
    In the case that X didn't cut 1/3 piece out, X would get the least and Y 
    would get a larger piece than 1/3 at least.  Here is the situation 
    depends on how X cut the cake.
	(2a) If X cut a piece less than 1/3 out, it's obvious that X would 
	     get less than 1/3 because Y would choose the larger piece.
	(2b) If X cut a piece larger than 1/3 out, Y would choose the larger 
	     piece to cut (but Y can choose the smaller piece and get more 
	     than 1/3).
	(2c) If X accurately cut 1/3 piece out, I assume one thing that Y 
	     doesn't hate X.  If Y chose the 2/3 piece and cut it by the rate 
	     of 1:10, Y can still get 1/3 but no more than 1/3.  So Y 
	     shouldn't begin the war.
(3) Z takes the largest piece.
(4) Y takes the 2nd largest piece.
(5) X gets the remained one.

/fusao, a lazy reader.

The current issue of _Discover_ has a discussion of a new solution to this
problem, which is unlike any offered here.  They make it sould like the only
generally accepted generalizable solution.