Well,

In the last post we have seen how can we have a **fair** share division of a cake for two contenders. However, life is not as simple as we believe it to be.

Let’s introduce a new character to our drama. Chinku joins in the party so he also need a fair share of the cake. What do we do now? Let us try examining possible solutions one by one.

** Method 1**:

Let’s assume that Pinku and Rinku already have their fair share. When Chinku joins in, the cake has to be divided in a way so as to make everyone believe that they got 1/3rd of the cake. We can let Chinku take 1/3rd piece from Pinku as well as Rinku’s share.

This method will fail for obvious reason because Chinku’s evaluation of a piece may differ from that of Pinku and Rinku’s.

**Method 2**:

Actually, we can again play **Cut and Choose **with a bit of modification. Let Pinku and Rinku divide their respective pieces into 3 equal pieces ( from Pinku’s perspective, similarly from Rinku’s perspective). and Let Chinku choose one piece from and one piece from .

It is clear that with such a strategy Pinku as well as Rinku will be satisfied. Because and same can be argued for . Now, we need to see whether Chinku will get a fair share or not. Because, Chinku is the chooser, he will choose a piece and . Chinku will get a fair share because

Okay, so far so good. What will we do if Dinku joins the party??? We can go on and on about adding more and more contenders. So let us generalize this algorithm.

- Assume cake is divided fairly amongst persons. Obviously, for he/she has the whole cake.
- When person joins, let everyone but divide his/her share into equal pieces from their perspective.
- Let choose one piece from each person ‘s share.
- is happy because he/she originally had share and after the new person takes one piece he/she has
- Person is happy because he has

The above mentioned algorithm is called **“Successive pair algorithm”. **In the next post,** **we will look at more algorithms for fair share division where more than two contenders are involved.

### Like this:

Like Loading...

*Related*

Tags: cake-cutting algorithms

This entry was posted on April 3, 2008 at 6:20 pm and is filed under algorithm, math. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

April 7, 2008 at 5:20 pm |

[…] Me, Myself and Mathematics Saurabh Joshi’s Blog about math, algorithms, theorems, puzzles …. « Cake Cutting Algorithms – 2 […]