Cake Cutting
Ten people want to divide a cake among themselves. Each person likes some parts of the cake and dislikes other parts. The goal is to divide the cake with 9 knife cuts in a way that each person gets at least one-tenth of the parts they like. How should we cut the cake?
Assume that each knife cut is a straight line on the surface of the cake.
The algorithm for this problem is known as “the moving knife
algorithm".
Let us move a vertical knife from the left-most point of the cake to the
right. We stop as soon as any of the ten people is happy with receiving
the portion of the cake to the left of the knight. At that point, we cut
the cake vertically and give the portion of the cake to the left of the
knife to the person who is happy with receiving that portion. After
that, we again move the knight to the right until a person among the 9
remaining people is happy with receiving the portion of the cake to the
left of the knife. We proceed until each person receives one portion of
the cake.
The above algorithm works because of the following fact: Every time we cut the cake vertically, each of the people loses at most 1/10 of the parts of the cake that he likes (otherwise we would stop the knife earlier). Thus, this algorithm allocates the desired pieces of the cake to all 10 people.