For two people, this is a quite simple and well known answer. One divides, the other decides.

However, when you have more than two people, it gets trickier. So, picture a round cake of equal height.

  • Designate a cutter.
  • Make a single cut from to the center of the cake.
  • Slowly move the knife clockwise.
  • At any point, anyone may say "Now".
    • This stops the knife
    • Makes the cut
    • Gives the cut piece of cake to the person who said "Now"
    • Removes the person with cake from saying "Now" again
    • If it is the cutter that said now, reassign the cutter.
  • Repeat until down to 2 people.
This method works based on the idea that each person wants an equal part of the cake. Once it gets to 1/Nth of the cake, it is best for people to say 'Now', otherwise someone else will have a larger piece than 1/Nth of the cake meaning that there will be less cake for you.

Mathematically, this relies on the Frobenius-Konig theorem.

Usually, this issue surfaces when you have two or more children, all of whom want cake. Well, really, they want all the cake, and don't really want to share it. So it's up to you to make them share, and share evenly enough that neither one is crying at the end.

Important Note: This should only be done with children who are old enough to be trusted with knives but not old enough that they might kill the other child with the knife.

  1. Have the cake, children, and knife present.
  2. Hand the knife to the first child, and say, "You get to cut the cake in half."
  3. The child will squeal in anticipation of leaving a tiny piece for the second child.
  4. Then say, "But <insert second child's name here> will get to pick their piece first."
  5. The first child will then have to cut the cake in such a way that they will be satisfied with whichever piece they get.
  6. Both children are, if not happy, at least not crying.
To extrapolate this to more than two children, make it more complicated versions of the above whose recursive cases have the above as a base case. (I couldn't remember the algorithm offhand, but m_turner, above, did.)

There's another solution that works even when n different people have different ideas of what 1/nth of the whole is. One person is chosen randomly to start, and takes out for himself what he considers to be 1/nth of the whole. If someone thinks that what he took out was more than 1/nth, that person removes some from what the first person thought was 1/nth (he thought it was bigger than 1/nth, right?), and claims the rest for himself. We repeat this challenge process until everyone agrees that this is at most 1/nth, and we recursively divide the rest of the whole among n-1 people.

To adapt this to cutting a cake, instead of actually cutting out 1/nth of the cake, we just indicate where the cut would go, and others make the indicated cut smaller as appropriate. This avoids passing around slivers of cake (thanks mblase). Really, this algorithm is best suited for dividing many discrete items among a few people.

Log in or register to write something here or to contact authors.