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

**The 1999 British Informatics
Olympiad FinalA piece of cake**

**Time allowed: 1 hour**

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 *i*th 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.

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:

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.)Each player

*P(1),...P(n-1)*cuts each of their pieces into*n*equal parts.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?

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?

The British Informatics Olympiad