Proportionales Cake-Cutting

How did you divide a christmas stollen fairly?

Today we would like to deal with an important problem, especially at Christmas time, which is not so easy to solve: How do you divide a cake, for example a Christmas stollen, fairly among any number of people so that everyone is satisfied with their piece and not envious of someone else?

In fact, "fair sharing" is a mathematical discipline that tries to solve such problems through modeling and intelligent calculation steps. We would like to explain to you here briefly and understandably how the so-called Proportional Cake Cutting problem can be solved with a simple algorithm.

Initial situation

The siblings Anna and Tim want to share a Christmas stollen and divide it into two fair pieces. The Christmas Stollen has an irregular shape so that the middle is not immediately recognizable. What is the best way to proceed so that everyone gets a piece with which they do not feel disadvantaged?

People
2

split by three

Even before Anna and Tim can put their idea into practice, a third person, Max, is added. He also wants to have a piece of the tunnel and the three of them decide to divide the tunnel fairly among three people.

People
3

Any number of persons n

The procedure described above can be extended for any number of people. Now let us assume that we do not have only two or three persons, but any but fixed number n of persons among whom the Christmas Stollen should be divided fairly.

People
n

Further thoughts

In the last scenario we have seen how to divide the Christmas Stollen fairly among any number of people. Mathematicians and also computer scientists are now also thinking about how many notches are made in this procedure in total. This number provides information about the duration of the procedure. We can consider that with n persons

  • n notches must be made to cut off the first section, then
  • (n-1) notches to separate the second section, then
  • (n-2) notches to separate the third section, etc.
  • until at the very end 2 more notches have to be made to divide the gallery among the remaining two people.

So all in all we make n + (n-1) + (n-2) + .... + 2 = ½ n (n+1) -1 many notches . The number of notches thus grows quadratically with the number of persons. If 1000 people wanted to get a fair piece at a village festival, where a huge stollen was baked by the local bakery, more than half a million notches would have to be drawn with the procedure.

There is also another fair sharing procedure based on the principle of "divide and rule". In this method, only in the order of n log n many notches are drawn. This would reduce the number of notches to be drawn at the village fair to about 10,000.

Have we aroused your interest?

Mathematics is the basis for every technical achievement and an indispensable component of innovative topics. In today's fast-paced and complex world, there is more demand than ever for those who have studied mathematics. Whether in the financial sector, the automotive industry, management consultancies, medical technology, IT and telecommunications or mechanical engineering: Mathematics opens the door to almost every industry and opens up excellent opportunities on the job market

No matter whether you choose the classic or cooperative study option: At the HFT Stuttgart we train you as a structured problem solver, mathematical creative thinker and communicative team player. There are two specialisations to choose from: Algorithm Engineering (computer science focus) or Financial and Actuarial Mathematics (business mathematics focus).

More about math at the HFT
Publish date: 19. November 2020