Dividing the Cake

 THERE IS a simple procedure by which two people can divide a cake so that each
is satisfied he has at least half: One cuts and the other chooses. Devise a general
procedure so that n persons can cut a cake into n portions in such a way that
everyone is satisfied he has at least 1/n of the cake.




Several procedures have been devised by which n persons can divide a cake
in n pieces so that each is satisfied that he has at least 1/n of the cake. The
following system has the merit of leaving no excess bits of cake.
Suppose there are five persons: A, B, C, D, E. A cuts off what he regards as
1/5 of the cake and what he is content to keep as his share. B now has the
privilege, if he thinks A’s slice is more than 1/5, of reducing it to what he thinks
is 1/5 by cutting off a portion. Of course if he thinks it is 1/5 or less, he does not
touch it. C, D and E in turn now have the same privilege. The last person to
touch the slice keeps it as his share. Anyone who thinks that this person got less
than 1/5 is naturally pleased because it means, in his eyes, that more than 4/5
remains. The remainder of the cake, including any cut-off pieces, is now divided
among the remaining four persons in the same manner, then among three. The
final division is made by one person cutting and the other choosing. The
procedure is clearly applicable to any number of persons.
For a discussion of this and other solutions, see the section “Games of Fair
Division,” pages 363–368, in Games and Decisions, by R. Duncan Luce and
Howard Raiffa, John Wiley and Sons, Inc., 1957.
The problem of dividing a cake between n persons so that each person is
convinced he has his fair share has been the topic of many papers. Here are three:
“How to Cut a Cake Fairly,” by L. E. Dubins and E. H. Spanier, in American
Mathematical Monthly, Vol. 68, January 1961, pages 1–17.
“Preferred Shares,” by Dominic Olivastro, in The Sciences, March/ April
1992, pages 52–54.
“An Envy-Free Cake Division Algorithm,” by Steven J. Brams and Alan D.
Taylor, preprint. More than fifty references are cited in the bibliography.
29. The first sheet is folded as follows. Hold it face down so that when you look
down on it the numbered squares are in this position: 2365/1874
Fold the right half on the left so that 5 goes on 2, 6 on 3, 4 on 1 and 7 on 8.
Fold the bottom half up so that 4 goes on 5 and 7 on 6. Now tuck 4 and 5
between 6 and 3, and fold 1 and 2 under the packet.
The second sheet is first folded in half the long way, the numbers outside, and
held so that 4536 is uppermost. Fold 4 on 5. The right end of the strip (squares 6
and 7) is pushed between 1 and 4, then bent around the folded edge of 4 so that 6
and 7 go between 8 and 5, and 3 and 2 go between 1 and 4.
For more puzzles involving paper folding see “The Combinatorics of Paper
Folding,” in my Wheels, Life and Other Mathematical Amusements (W. H.
Freeman, 1983).

Enregistrer un commentaire

Plus récente Plus ancienne