In these days, in some parts of the world, we are coming out of the Carnival celebrations, often associated with typical sweets made specifically for this period. Some of these sweets are homogeneous, while others represent peculiarities, such as the presence of candied fruit or strawberries, or strong differences in structure depending on the portion you eat. How many times has it happened that someone did not agree on how to divide the cake or which piece to choose?
So here comes a quite common everyday life problem, how to fairly divide a cake among those people? For homogeneous cakes, the problem is quickly solved; you make an equal division, and no one will envy the piece chosen by another, meaning no one will want to exchange their piece with an already chosen one. But what about a non-homogeneous cake? Is there a way to divide a cake into parts so that each person’s choice is without mutual envy? Surprisingly, the answer is yes, and the division algorithm uses Sperner’s Lemma, a combinatorial tool in graph theory.
The problem was exhaustively addressed by S. J. Brams and A. D. Taylor in 1996, and the resolution not only demonstrates the existence of the optimum, i.e., a division that satisfies everyone, but also presents an operational algorithm to achieve it or at least approximate it.
Imagine the cake viewed from above, and let’s decide on parallel cuts. A number N of portions will correspond to a choice of how to apply N-1 parallel cuts. The first portion, therefore, corresponds to the piece of cake identified between the left edge of the cake and the first cut. The second portion corresponds to the piece of cake identified between the first cut and the second cut, and so on. The choice of how to make the N portions can be reduced simply to how to decide the distance from the left edge to make the N-1 cuts. We can now think about quantities d1, d2, d3, …, dN, where d1 is the distance of the first cut from the left edge, d2 is the distance of the second cut from the first cut, and so on. Since the sum of these distances must be the length of the cake L, we have d1+d2+d3+…+dN=L. Therefore, the set of choices is an N-1 simplex, and each point of the N-simplex corresponds to a different way of cutting the cake (a 2-simplex is a triangle, a 3-simplex is a tetrahedron, and so on).
The algorithm for selecting the optimal cut is obtained by triangulating the N-1 simplex obtained and asking a different person at each vertex of the triangulation which slice of cake they would choose in that particular division. So, you label the triangulation with 1, and the person in that division would choose the first piece; label 2 if they would choose the second, and so on, obtaining a labeling with numbers from 1 to N.
This is a Sperner labeling, and you can apply Sperner’s lemma to find a little triangle where all the vertices have different labels. These, if small enough, correspond to a cut of the cake where each person wants a different piece from the others, thus a division of the cake without envy. In the figure, you can see how to identify the triangle with different labels, using the trapdoor method: the sides of the triangle with label 1 and 2 are the doors to open, leading to the little triangle or another side on the edge with label 1 and 2. Since the sides on the edge are always an odd number, at least one will not lead to another side but will instead lead to a little triangle with different labels (in the figure, the path to the optimal triangle is shown in green, and one exiting in blue).
Did you enjoy this article? Follow Visit Math for more mathematical curiosities!