As humans we tend to own everything. When dividing something among people we need to own a fair portion, if not a bigger portion. Thus problems regarding dividing has become the source of many conflicts, wars and sometimes crimes. Cake Cutting problem is an interesting thing in mathematics which deals with dividing a cake between several people such that each person is fully satisfied with the piece he gets.The generalized dividing problem is also known as the fair division problem and there are several algorithms to solve this. This problem is very much associated with real life problems.

### Basics

Also the criteria to decide the value of each portion is important. In the simplest case the value of each piece is based on its size. But in complex (and practical) cases the value of each piece will be different to each participant. One participant may value a piece of cake with more icing on it while one prefer a piece with cherries. Even under these conditions the definition of fair will help us to tackle the fair division problem easily.

### Simplest Case

The simplest case is the division of a cake between two people. This can be easily solved using the divide and choose method. In this scenario one person divide the cake into two pieces which he thinks that is fair. The other person gets the chance to select a piece he like. The other piece is left to the first person. As the first person initially divided the cake in to two fair parts he gets a fair portion. Although second person do not agree with the division of the cake in to two as fair he gets the chance to select any piece. Thus he will also be satisfied with the piece he gets.

The next case is the division of a cake between three people. There are several methods to solve this fair division problem for three people. Almost all these methods can be generalized to solve problems containing more than three people.The divide and select approach which was used for two person case can not be extended to solve this. And there are solutions which seems plausible but proved wrong when thoroughly analyzed.

Let's now analyze one such incorrect approach. Let the three people be named as A,B and C. This solution includes following steps.

### The Case of Three

Let's now analyze one such incorrect approach. Let the three people be named as A,B and C. This solution includes following steps.

- A cuts the cake in to two pieces where he thinks one is 1/3 and the other is 2/3 of the cake.
- B cuts the 2/3 part of the cake in to two fair pieces.
- C chooses any piece he likes.- So C is satisfied
- Then A chooses.
- Finally B chooses.

Now lets analyze the above solution. Since C selects first, clearly C is satisfied. If C has chosen a piece that is cut by B then A can select the initial piece he cut. If C has selected the initial piece cut by A, then A can select one of the pieces cut by B. As A initially divided in to 1/3 and 2/3 parts, at least one piece cut by B should be 1/3. So A is satisfied in any case. The problem is with B. If B thinks the initial cut by A is not fair (ie. The smaller piece is larger than 1/3 of the cake) B is only satisfied with that piece. Thus if that piece is selected by A or C then B is left unsatisfied. Thus the solution given here is not correct.

Thanks you for this post… great information.

ReplyDeleteworldcup live stream score t20

T20 WC 2016 Live Streaming Score

This blog is a great source of information which is very useful for me.

ReplyDeleteRising Pune Supergiants Team Squad Captain Name

DD New Players List

Kings XI Punjab New Jersey Logo Images

This blog is a great source of information which is very useful for me.

ReplyDeleteAsia Cup T20 2016 Schedule Time Table

Watch Asia Cup T20 Live Streaming Online & Broadcasting List

New Zealand Team Squad Players List

Nice to see read that you have some knowledge about acne treatment cure...

ReplyDeleteICC T20 World Cup 2016 Womens Points Table

Australia Team Captain Name T20 World Cup 2016

Ind VS Pak 19th march T20 WC 2016

ReplyDeleteThanks.... This website is very helpful for me... I'm looking this website for a long

IPL t20

IPL t20 2016

IPL t20 2016 live

IPL t20 2016 Live streaming

IPL Live Streaming

IPL Live

IPL t20 2016 Streaming

IPL t20 live Streaming

IPL t20 live

gseb

gseb result

gseb result 2016

maru bharat

maru bharat

icc t20 world cup

icc t20 world cup 2016

icc t20 world cup 2016 live

icc t20 world cup 2016 live streaming

icc t20 world cup live

t20 world cup 2016

t20 world cup

t20 world cup 2016 live

t20 world cup 2016 live streaming

t20 world cup live

rio olympic game 2016

rio olympic schedule 2016

rio olympic games

I'm gonna to share with my friends...

Cbse Hyderabad 10th Results

ReplyDeleteCbse Bihar 10th Results

Cbse Allahabad 10th Results