Real MATHEMATICS – AlgorIthm #4

Fair Cake Division

Is there a bullet-proof method for cutting a cake fairly?

This became a legitimate problem in mathematics back in 1944. A mathematician named Hugo Steinhaus published a paper for fair cake-cutting. According to him solution is trivial for two people. Method for two people is today commonly known as “one cuts, other picks”:

 

First person cuts the cake in half (on his/her point of view) and other person gets to pick any piece he/she wants. In this method both of them are happy and envy-free as first person believes the pieces are equal and second person picks the biggest piece on his/her view. Steinhaus’ answer is the first envy-free answer for fair cake division.

What if there are three people? Is there an envy-free method for cutting a cake for three people?

Incredible but answer wasn’t that obvious. Only 18 years after Steinhaus’ work (1962) J. H. Conway and J. Selfridge (independently) found an answer.

Ali, Steve and Jane

General method:

1. Ali cuts the cake into three equal (that he considers equal) pieces.
2. Steve evaluates the pieces. If he decides to do nothing Jane takes the turn.
3. Jane selects any piece she wants. Steve picks as second, Ali gets the last piece.

Obviously things are never this easy. Let’s examine the method in details and show how ingenious it is:

Step #1: What should Ali do?

First step is easy: Ali cuts the cake into three equal pieces. Since he cuts them, he will be pleased to receive any of the pieces.

 

Step #2: What should Steve do?

Steve checks the pieces. Here, there is more than one possibility depending on how Steve sees Ali’s cuts:

1. If Steve decides that at least two of the pieces are the best ones (best as in biggest) he does nothing and process continues with Jane selecting her piece.
   a. In case Steve thinks that all three pieces are equal, whichever Jane selects, he will get the best piece according to him:

b. In case Steve thinks that two of the pieces are equal and best, even if Jane selects one of them, he will get to select the other best piece. He will be happy in either case.

• If Steve thinks one piece is bigger than the other two, he needs to do something. Otherwise Jane would get the biggest piece:

  

  In such situation Steve trimmers the biggest piece which will result in a trimmed piece and a leftover:

   

  

  

  This way trimmed piece will be equal to at least one of the two remaining pieces which means at least two (trimmed and one of the other two) of the cake pieces are the best ones. Now Steve is ready to let Jane select her piece.

 

Step #3: What should Jane do?

Here, Jane is free to choose whichever piece she’d like to:

1. If Steve did nothing, Jane will select any of the pieces. Steve goes after her and Ali will get whatever is left. Everyone will be content with his/her choice.
2. (Steve trimmed a piece.) In such situation Jane is still free to choose. But now her choice determines the rest of the game. There are two possibilities at this state:
   a. Jane selects the trimmed piece. Then Steve and Ali will get their pieces in that order. In this situation Steve gets to cut the leftover into 3 equal pieces. Then Jane, Ali and Steve each select a piece of the leftover in that order:
    
   

   

   b. Jane selects any of the untrimmed piece. In that case Steve must select the trimmed piece and Jane gets to cut the leftover into 3 equal pieces. Then Steve, Ali and Jane each select a piece of the leftover in that order.

One wonders…

Is this really envy-free?

(Give yourself some time to think before you read the answer.)

*

*

*

Answers

For Ali: Yes, because Ali cuts the cake in three equal pieces on his view. He will be content with any of the pieces. Also he will not mind getting a part of the leftover.

For Steve: Yes, because Steve decides that there are at least two best pieces and he will be content with any of them. Also he will get to cut the leftover into 3 equal pieces which means he knows that he can get any of the leftover pieces.

For Jane: Yes, because she gets to select first for the original and leftover cake.

M. Serkan Kalaycıoğlu