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:
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, 71493915
Alexander Bogomolny