The British Informatics Olympiad is the computing competition for schools and colleges. We are proud to present BIO'99.

The 1999 British Informatics Olympiad Final
A piece of cake

Time allowed: 1 hour

1. Once upon a time...

Romulus and Remus have been given a cake to share and they are trying to decide how to divide it. Romulus has suggested that he will cut the cake in half and then give one of the pieces to Remus. Remus is not happy with with this. He trusts Romulus to cut the cake fairly but he fears they may disagree over the 'value' of the pieces of cake; Remus is particularly fond of the marzipan topping and the chocolate filling, Romulus prefers the sponge but also loves chocolate. If Romulus cuts it fairly he will believe the two halves to be equivalent (to his tastes), but Remus might have a low opinion of one side and be unhappy if Romulus gives it to him.

A friend has offered to cut the cake in half and then choose who receives which piece. Romulus and Remus are both unhappy with this arrangement. Their friend could divide the cake into two halves, Romulus might feel the pieces are worth 1/3 and 2/3, Remus might feel the value of the pieces is the other way around. It would be possible for them both to receive a piece worth, in their respective opinions, 1/3.

The method they settle on as being fair has Romulus cutting the cake and Remus choosing which piece he wants. This is fair because each person can guarantee receiving a piece worth, in their own estimation, 1/2. This method is called cut and choose.

Question 1.1
Using the cut and choose method, if Romulus is being fair, would you prefer to be Romulus or Remus, or does it not matter? Why?

Question 1.2
Romulus is thinking of cheating: he is planning to cut the cake so one piece is, in his opinion, larger than the other. How will this affect Romulus and Remus?

Question 1.3
Suppose the cake that Romulus and Remus receive has already been cut into n pieces. Romulus values the ith piece at value[i]; the sum of these values is 1, and every piece has non-negative value. Romulus wants to divide the cake into two piles, each of total value 1/2. Outline an algorithm that does this, using at most one additional cut.

2. How many cuts are necessary?

Cutting a cake fairly for n 'players', i.e. so that every player receives a piece worth at least 1/n in their own estimation, is not so simple when n>2. There are different algorithms which will allow us to solve the problem, and we can ask ''How do we minimize the number of cuts?''

The successive pairs algorithm is a recursive solution. It solves the problem for n players by using its solution for n-1. If n=2 we use the cut and choose method, otherwise:

1. Players P(1),...P(n-1) perform the algorithm for the n-1 case. (This will leave each of them with, in their own opinion, at least 1/(n-1) of the cake; if n>3 these portions will be composed of a number of pieces.)

2. Each player P(1),...P(n-1) cuts each of their pieces into n equal parts.

3. Player P(n) chooses one part from each of the pieces cut in step 2.

Since P(n) can take, in his own opinion, at least 1/n of each player's cake, it does not matter how much cake he believes each player has. The total of the pieces he takes will always be at least 1/n of the entire cake.

Question 2.1
If there are n players how many peices does this algorithm produce in total? How many cuts are made?

Step 2 in the successive pairs algorithm asks each player to cut each of their pieces into n equal parts. This is to enable P(n) to take 1/n of each player's cake. All we really need is to ensure each of P_1,...P(n-1) have divided their cake into n equal parts.

Question 2.2
(a) In question 1.3 you showed how a collection of pieces can be split into two equal piles using at most one additional cut. This principle, called one cut suffices, also enables you to split the pieces into two piles of any ratio. Show how this can be used to modify steps 2 and 3, and hence reduce the number of cuts.
(b) How many cuts does your new algorithm require?

Question 2.3
How could you modify the original successive paires algorithm so that P(n) does the cutting in step 2?

The successive pairs algorithm works by splitting the players up into groups of size n-1 and 1. If we split the players up into more equal groups, by designing a divide and conquer algorithm, we can share the cake using fewer cuts. Again, if n=2 we just use cut and choose.

Let us consider the case where n is even. We ask P(1),...P(n-1) to make parallel cuts in the cake, so that the portions on either side are equal. For simplicity we will assume none of these cuts coincide. [The example below shows possible cuts when n=4.]

We now ask P(n) which of the two portions on either side of the middle cut they think is the largest. If P(n) prefers the left side we let P(n) and all the players who made cuts to the left of the middle cut share out the cake to the left of the middle cut. The remaining players share the cake to the right of this cut. We can distribute the cake in a similar fashion if P(n) prefers the portion to the right.

This works (in the first case) because P(n) believes the left portion to be half of the cake, and each player with a cut to the left of the middle cut believes the portion to be worth at least half of the cake (since it includes all the cake to the left of their own cut). We therefore have half the players sharing what they all believe to be at least half the cake. Similarly the middle player believes the right portion to contain half the cake, and the other players receiving this side believe it contains at least half the cake.

Question 2.4
How do we split the cake if n is odd?

Question 2.5
Calculate how many cuts are required by this algorithm when there are 3 players? How about 9 players?

3. Consultation cake cutting

The cake cutting problem we have looked at so far does not allow the players to consult with each other before cutting the cake. Suppose we let each of the n players mark the cake into n equal pieces; is it possible to cut the cake, using these marks, so that every player receives a piece they are content with? [We will assume that each mark is a straight line delineating the cake into two pieces, and that all the marks are parallel to the y-axis.]

Romulus and Remus are dividing a cake. They mark the cake and find that their marks do not coincide - i.e. they are evaluating the cake differently.

Romulus believes that the pieces to the left and right of the solid line are both equal, Remus holds a similar belief for the dotted line. If Romulus receives the piece to the left of the solid line and Remus receives the piece to the right of the dotted line they will both believe they have 'half' of the cake. Furthermore there is some cake between these two lines which can then be shared between them; in other words they can both end up with more than 'half'.

Question 3.1
(For this question ignore any pieces that are left over.)

(a) A, B and C have each marked a cake into three equal pieces, where none of the marks coincide. We can denote this by just giving the order of the marks, |ABCBAC|. The | is just to emphasize the edge of the cake. How can this cake be divided amongst the three players, so that each receives a piece they believe to be exactly 1/3?

(b) A, B, C and D have marked a cake as |ABCDBACADDBC|. List all the ways the cake can be divided, so that each receives exactly 1/4.

Question 3.2
A cake is to be divided by n players, each of whom has marked the cake into n equal pieces. None of the marks coincide. Outline an algorithm for distributing the cake, so that each player receives at least 1/n. [Your algorithm may distribute any additional cake.]

Question 3.3
Suppose some of the marks coincide. How would you modify your algorithm?

• Index of BIO'99 final