Subject: Re: Dividing a cake
Date: Sun, 5 Oct 1997 01:18:06 -0400
From: Alex Bogomolny

Dear Nilo:

The problem is not new and I am quite certain I saw a published solution which I disliked and, therefore, did not make an effort to memorize. I couldn't located the book though. Here is another solution:

The solution is by induction. For n=2 you know it. Let for all k

Choose a fellow (say, #1) and ask him to divide the cake in such a way that he would be satisfied with getting any piece. (This is your assumption 1: the thing is possible.)

Consider remaining n-1 guys who each having a notion of desirability of every piece. You make here a second tacit assumption that each will be satisfied with at least one of the pieces because the only sensible definition you can give is that a piece is desirable in somebody's eyes if the fellow thinks the piece is not less than 1/n-th of the cake. But surely a fellow can't think of each of the n pieces as being smaller than 1/n-th.

Consider three cases:

1. There is a piece no one (excluding, of course, #1) likes. Give to #1, put the remaining pieces together. The (n-1) guys must all think they got more than (n-1)/n-th of the cake. Use the inductive hypothese.
2. There is a piece liked by exactly one fellow (other than #1). Let him have it. Put everything together and again reduce the problem to n-1.
3. Each piece would be accepted by at least two fellows.

In the latter case, draw a bi-graph with nodes corresponding to pieces and (n-1) fellows. There bound to be a loop:

Start with any "fellow" node, walk along one of the emanating edges to a "cake" node. From there return to another "fellow", and so on. Do not go along the same edge twice. Sooner or later you'll get to an already visied node. If it's the starting one - we are done. Otherwise, forget about the chain which is a part of your trail but which does not fit into the loop.

In a loop, each fellow can get a piece to his satisfaction. Remove the loop from the graph. The fellows who staid couldn't feel bad about this for each still has a chance of getting an acceptable piece.

Regards,
Alexander Bogomolny