Sorry to intrude. Curious. May I ask what you assign for reading before the discussion?
And do your students distinguish between a division procedure that everyone accepts as fair versus a logical procedure that produces verifiably equal pieces matched after accounting exhaustively for competing personal cake claim preferences?
This is usually in a āsurvey of mathā course, and we usually have a text, none of which I would recommend for a casual reader. I supplement with lecture notes. As a general survey of results you could do worse than start with Cake-cutting algorithms : be fair if you can by Robertson and Webb, or Fair Division: From Cake Cutting to Dispute Resolution by Brams and Taylor.
For something shorter that will give you some flavor of the area, there is this nice article by Theodore Hill in American Scientist (it starts with the Talmud!)
And do your students distinguish
The problem of cutting the cake into n pieces which is exactly 1/n of the cake by every studentās measure is slightly harder than an āenvy-freeā procedure (where chooser i thinks that s/he gets at least 1/n of the cake, but chooser j gets no more than 1/n of the cake by iās measure). The more such requirements you put on the outcome, the less realistic the algorithms are, and the more the result is what mathematicians would call a ānonconstructive existence argument.ā Few of the students in my class are mathematically sophisticated enough to appreciate such arguments.
The most venerable such problem I know of is the āProblem of the Nileā (hmm, there are other threads where I might have raised thisā¦) due to the well-known statistician R. Fisher in 1938:
Each year the Nile would flood, thereby irrigating or perhaps devastating parts of the agricultural land of a predynastic Egyptian village. The value of different portions of the land would depend upon the height of the flood. In question was the possibility of giving to each of the k residents a piece of land whose value would be 1/k of the total land value no matter what the height of the flood.
The fact that this can be solved is a consequence of a theorem by a Russian named Liapounoff in 1940. The first proof in English of that theorem was by quite an eminent American mathematician, who made an elementary error in the published proof (screwed up the first step in a mathematical induction), a fact that I like to point out to more advanced students both to emphasize how important care is in such proofs and also to reassure them that even top mathematicians can make stupid careless errors.
Thank you! Thatās a whole new and interesting perspective for me on that sort of problem.
I think you are reading it a little too strictly, they do not actually have to be correct that they have at least 1/n of the cake.
On the other hand you are reading it a little loose, because even if the cake is perfectly divided, one or more parties might still be convinced that they didnāt get their fair share.
So itās not really anything to do with getting the divisions precisely accurate, and if it were thatās just a geometry problem anyway. What it really has to do with is IMO giving everyone agency regarding every piece. The various āI cut, you chooseā algorithms necessarily fail to guarantee everyoneās satisfaction because there is always at least one person who is not free to exercise agency in a way that demonstrates that they are accepting a satisfactory piece, e.g. in a three person problem, if the first piece cut is considered too large by the other two, they canāt both exercise agency to select that piece and by default whoever misses out on that piece will be stuck with a piece they consider too small. Note that this problem exists whether or not the cut was actually unfair in a geometric sense!
So the only real solution is one where everyone had some agency over the size of every piece; therefore the Dutch auction from toward the top of the comments. A cutter makes one cut and rotates the knife until any person says stop (himself included). A cut is made there and we have one piece that at least one person says they are satisfied is at least 1/n. Remove whoever got the slice, repeat until you have n pieces. By definition no one ends up with a piece that they think is less than 1/n.
But what if, when you get to point where half the cake is gone, there are still more than n/2 people left? Clearly, no one in the second group is going to be satisfied that they have 1/n of the cake, since they know that their portions would have to be smaller.
If you reduce this to n=2, then it becomes a game of chicken- the goal isnāt to get exactly half, itās to call āCutā exactly the moment before the other person does, and to postpone that moment for as long as possible. The longer you wait, the better the prize.
Depends.
Did I bake the cake?
Did the Hen, the Bear, the Cat, the Pig, the Dog and the Monkey help to bake it?
Put the cake in a blender.
Add milk.
Blend.
Pour out equal portions, measured using a liquid measuring cup.
Enjoy.
Use the BanachāTarski paradox to divide it into n identical cakes, then pass them out.
I was thinking along the very same lines 
Which reminded me of descriptions of Buddhist monks eating
The monks walk barefooted into a village and then from house to house, not favoring rich or poor neighborhoods, accepting, but not requesting, what is freely donated, that is, dropped into oneās bowl. Everything dropped into the bowl, according to ancient tradition, is simply mixed together, since monks are asked not to favor one food over another, and by extension should not favor one blend of foods over another, just as their stomachās will not a few seconds later.
Feeding the Monks | Buddha-SÄsana
From the land of the pork donut, I am not surprised:
[quote=ānimelennar, post:66, topic:77643ā]
But what if, when you get to point where half the cake is gone, there are still more than n/2 people left?[/quote]
Half according to whom? Each of the remaining n/2 people think that more than half is left at this point.
This algorithm is sometimes called the āMoving Knifeā algorithm, and is due to Dubins and Spanier in 1961. (Correction: Banach and Knaster, 1940-something) It really does work, but it is not envy-free.
Knowing exactly what constitutes 1/14 is hard. Knowing what constitutes 1/2 is easy - itās a diameter through the cake. If, when youāve cut a diameter, you still have 8 people left, each of them has to know that some of them will be getting less than 1/14 of the cake.
Iām afraid youāre not understanding the premise of the problem. It isnāt a geometry problem, it is a fair allocation problem. Each of the n people is supposed to have his or her own way of judging a piece of cakeās value: it might just be area (especially for a simple cake), but there might be frosting and one person prefers more frosting, another less; or the people might differ in their abilities to judge area.
The geometric problem is conceptually much simpler, and while the knife algorithm works for it as well (ie, if you assume that the cake is a perfect disk and everyone just wants 1/n of the area) it is not necessary, you can just use whatever geometric dissections are available to you.
If you are a participant in the knife process, then if you are not the first one to say āstop!ā then at that moment you believe that at least (n-1)/n of the cake remains, while the first person is satisfied that he has 1/n of the cake. The remaining n-1 of you now divide this remainder up, and by induction you should each believe that you have at least 1/(n-1) of the at least (n-1)/n of the cake that was there, ie at least 1/n.
Finally, you are correct that one or more of the eaters might believe that some other eater got less than 1/n of the cake; likewise one or more of the eaters might believe that some other eater got more than 1/n of the cake. This algorithm dosnāt solve that problem, it only solves the problem of making sure that every eater gets what she believes is 1/n of the cake for herself.
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
Of course, this either means every has to have 1/n of the cake, or at least think that they do.
Serve it on mirrored plates?
Yes, they have to think that they do, however they choose to make that evaluation.
As Dubins and Spanier say in the article I cite above,
Whether or not the two people agree as to what constitutes half the cake makes no difference as it is always possible to divide the cake in the desired manner.
(However, I have to correct something I said above; while I said the moving knife method is due to Dubins and Spanier, in fact that is a generalization, and the original algorithm is due to Banach and Knaster in the 1940s; see H. Steinhaus, Sur la division pragmatique, Econometrica (supplement), vol. 17, 1949, pp. 315-319.)
In theory, maybe it works, but I just have this image in my mind of, "Oh, shit. Half the cakeās gone now, and I missed my opportunity to get a full-sized piece. Oh, well, Iām going to have to settle for (1/2(n-c)) of the cake (where c is the number of people who have already taken a piece of cake). That is, their impression of what constitutes a fair-sized slice might change as the cake grows smaller.
Doesnāt the puzzle necessarily include a political element?
All procedures are disputed. The group needs to also accept a means of resolving disputes as fair for the division to be accepted as fair.
So members of the group should identify and agree which procedure will produce a fair outcome before any cutting is done.
Exactly. Which is why the fully objectivist man will seize the cake and shoot anyone who objects, unless they are women of course, in which case he will allow them to have some cake after impregnating them. Itās the only fair way.
Praise St. Reagan and St. Rand!
Like all mathematical problems, there is an element of idealization; we probably also have to assume that all the eaters are perfect spheres of infinitesimal radius.
Seriously, I donāt know if the problem has a solution at all if individual measures can change in this way, but this knife solution doesnāt work. There is a modification, due to Walter Stromquist in 1980, where all the eaters have knives and do cuts at the same time; this would answer your concern, and also produces an envy-free solution, but it only works for n=3 people.
Sure. The mathematical problem is to find one or more procedures that satisfy some set of conditions, or prove that they donāt exist. The decision of which one to use in practice is based on which conditions the people involved most want to satisfy.
This is an ongoing problem with voting systems. Thanks to a variety of āimpossibility theoremsā we know that all voting systems are crap in the sense that they all violate one or more fairness axioms, and that the most common āplurality wins/first past the postā voting system is probably the crappiest of all. Since you canāt adopt a perfect voting system, you figure out which axioms you are least willing to violate, and choose a system respecting those (or just choose a system which is easy to implement and understand, like FPTP).
The Qix solution?
