# Cut the cake

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

Cake needs to be divided between two boys:A and B.It should be cut in such a way that each of them should feel that he has got

Ofcourse knife is given for cutting.

[ August 18, 2004: Message edited by: Arjun Shastry ]

[ August 18, 2004: Message edited by: Arjun Shastry ]

**half of the cake.***atleast*Ofcourse knife is given for cutting.

[ August 18, 2004: Message edited by: Arjun Shastry ]

[ August 18, 2004: Message edited by: Arjun Shastry ]

MH

posted 12 years ago

Let boy A cut the cake. But let B get to choose which piece he wants. B will be happy, because he got to choose the piece that was at least 1/2 the cake.

boy A will be happy, because if he cuts one piece bigger than the other, he knows B will take that piece. So, he cuts the cake exactly in half.

Now where it gets interesting is if you have 3 boys, and each should get exactly 1/3 of the cake. or 4 boys...or 5 boys...

boy A will be happy, because if he cuts one piece bigger than the other, he knows B will take that piece. So, he cuts the cake exactly in half.

Now where it gets interesting is if you have 3 boys, and each should get exactly 1/3 of the cake. or 4 boys...or 5 boys...

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

{

Let boy A cut the cake. But let B get to choose which piece he wants. B will be happy, because he got to choose the piece that was at least 1/2 the cake.

boy A will be happy, because if he cuts one piece bigger than the other, he knows B will take that piece. So, he cuts the cake exactly in half

}

{

Now where it gets interesting is if you have 3 boys, and each should get exactly 1/3 of the cake. or 4 boys...or 5 boys...

}

.You wrote on my behalf.

There are few methods or algorithms when N = number of boys exceeds 2.

Some of those are:;

1)Trimming algorithm

2)divide and conquer

3)Ramsey partition.

Problem becomes interesting when cake needs to be divided not equally but in some another ration,k1:k2.

Problem becomes even more interesting when cake needs to be cut with minimum number of cuts.

Details later.....

[ August 18, 2004: Message edited by: Arjun Shastry ]

Let boy A cut the cake. But let B get to choose which piece he wants. B will be happy, because he got to choose the piece that was at least 1/2 the cake.

boy A will be happy, because if he cuts one piece bigger than the other, he knows B will take that piece. So, he cuts the cake exactly in half

}

{

Now where it gets interesting is if you have 3 boys, and each should get exactly 1/3 of the cake. or 4 boys...or 5 boys...

}

.You wrote on my behalf.

There are few methods or algorithms when N = number of boys exceeds 2.

Some of those are:;

1)Trimming algorithm

2)divide and conquer

3)Ramsey partition.

Problem becomes interesting when cake needs to be divided not equally but in some another ration,k1:k2.

Problem becomes even more interesting when cake needs to be cut with minimum number of cuts.

Details later.....

[ August 18, 2004: Message edited by: Arjun Shastry ]

MH

Rachel Swailes

Ranch Hand

Posts: 434

posted 12 years ago

I think that any addition to the number of boys doesn't make it more of a mathamatical problem but more of a social experiment.

See, if you had A and B, then

A - cuts the cake

B - chooses for himself

This maintains that no boy chooses his own piece of cake. If we follow this then,

If you had A, B and C

A - cuts the cake

B - chooses for C

C - chooses for B (and A gets the last piece)

And if you had A, B, C, D

A - cuts the cake

B - chooses for C

C - chooses for D

D - chooses for B (and A get's the last piece).

I was trying to think of a way that the boys could form aliances with each other to end up with more cake.

For example with the three boys if A and B are together then, 'A' could cut two big pieces and one small piece, then B would choose the small one for C and A and B would get the big ones.

I should really be working!!

Rachel

See, if you had A and B, then

A - cuts the cake

B - chooses for himself

This maintains that no boy chooses his own piece of cake. If we follow this then,

If you had A, B and C

A - cuts the cake

B - chooses for C

C - chooses for B (and A gets the last piece)

And if you had A, B, C, D

A - cuts the cake

B - chooses for C

C - chooses for D

D - chooses for B (and A get's the last piece).

I was trying to think of a way that the boys could form aliances with each other to end up with more cake.

For example with the three boys if A and B are together then, 'A' could cut two big pieces and one small piece, then B would choose the small one for C and A and B would get the big ones.

I should really be working!!

Rachel

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

{

If you had A, B and C

A - cuts the cake

B - chooses for C

C - chooses for B (and A gets the last piece)

}

A cuts the cake into 3 pieces,1/3 each according to his mind.B and C might not think that way.Now if B chooses for C,its not necessary that both agree on that piece that its 1/3 of the cake.Similarly when C chooses for B.

If you had A, B and C

A - cuts the cake

B - chooses for C

C - chooses for B (and A gets the last piece)

}

A cuts the cake into 3 pieces,1/3 each according to his mind.B and C might not think that way.Now if B chooses for C,its not necessary that both agree on that piece that its 1/3 of the cake.Similarly when C chooses for B.

MH

Rachel Swailes

Ranch Hand

Posts: 434

Deepak Mahbubani

Ranch Hand

Posts: 68

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

{

For example with the three boys if A and B are together then, 'A' could cut two big pieces and one small piece, then B would choose the small one for C and A and B would get the big ones.

}

How big are these two pieces? If they are 45%,45% of the cake then C is going to complain that he got only 10% of the cake.Condition is everybody should feel that he has got atleast 1/n th of the cake where n = number of boys.

For example with the three boys if A and B are together then, 'A' could cut two big pieces and one small piece, then B would choose the small one for C and A and B would get the big ones.

}

How big are these two pieces? If they are 45%,45% of the cake then C is going to complain that he got only 10% of the cake.Condition is everybody should feel that he has got atleast 1/n th of the cake where n = number of boys.

MH

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

Problem is boys want only $89.99,Bellerina Cake.

Originally posted by Deepak Mahbubani:

I'd rather buy 1 cake for each of the boys and let everyone be happy. I have the money, so I don't waste my time and energy for such futile things. I have other important things to do (like make more money).

Problem is boys want only $89.99,Bellerina Cake.

MH

Deepak Mahbubani

Ranch Hand

Posts: 68

Hu Jiabao

Ranch Hand

Posts: 39

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

Yes.

No alliance is allowed.Everybody should feel that he has got atleast 1/n th of the cake.

Ok,for N = 2,its Cut and Choose method as you mentioned correctly.

For N >2,we can use Moving Knife algo.

1)One boy will take a knife,and moves the knife from left to right of the cake.

2)The moment anybody feels that left part is 1/N th,he will say 'Stop'

3)That part is cut and given to him and he will drop out.

4)If N = 2 ,use Cut and Choose or Go to step 1(N = N-1)

Number of cuts will be N-1.This is continuous algo and not discrete one I think.

[ August 19, 2004: Message edited by: Arjun Shastry ]

[ August 19, 2004: Message edited by: Arjun Shastry ]

No alliance is allowed.Everybody should feel that he has got atleast 1/n th of the cake.

Ok,for N = 2,its Cut and Choose method as you mentioned correctly.

For N >2,we can use Moving Knife algo.

1)One boy will take a knife,and moves the knife from left to right of the cake.

2)The moment anybody feels that left part is 1/N th,he will say 'Stop'

3)That part is cut and given to him and he will drop out.

4)If N = 2 ,use Cut and Choose or Go to step 1(N = N-1)

Number of cuts will be N-1.This is continuous algo and not discrete one I think.

[ August 19, 2004: Message edited by: Arjun Shastry ]

[ August 19, 2004: Message edited by: Arjun Shastry ]

MH

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

.We can extend Cut and Choose method to more than 2 people also.Number of cuts will be N-1.We need to minimize those afterwards.Also Cut and Choose method is not necessarily Envy Free.i.e. If A cuts,B accepts the piece.Then A again cuts and C chooses.Here A might cut(2/3 of cake) in the ratio say 70:30 instead of 50:50 according to B's thinking.So B feels that although he has got 1/3 of cake,A has recieved more than 1/3rd.

Trimming algo or 3 people algo or Ramsey partition are possible solutions.Details later...

[ August 20, 2004: Message edited by: Arjun Shastry ]

Trimming algo or 3 people algo or Ramsey partition are possible solutions.Details later...

[ August 20, 2004: Message edited by: Arjun Shastry ]

MH

posted 12 years ago

But what if C thinks the first piece is bigger than 1/3? C thinks the first piece was 40%. then there's only 60% left. A cuts than in half, C only gets 30%. C is not happy.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Originally posted by Stefan Wagner:

For A,B,C (,D,...):

A cuts a piece off.

If B likes to have it he can grab it.

...

But what if C thinks the first piece is bigger than 1/3? C thinks the first piece was 40%. then there's only 60% left. A cuts than in half, C only gets 30%. C is not happy.

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

Divide and conquer goes by cutting the cake in the middle and repeating it until ratio becomes 1:1,and then use cut and choose method.

Suppose cake needs to be divided in ratio 5:12,5 parts for A and 12 parts for B

1)A(person recieving smaller part) takes the knife and cuts the cake in ratio 8:9

2)B chooses whichever parts he 'feels worth'.(He must choose one as he can't say 'both are not worth'!).

Suppose B has choosen 8 parts.Now he expects 4 parts of remaining cake.

3)Now B takes the control of knife and cuts the remaining part(9/17th) in ratio 4:5

4)A chooses 4 parts.Now he expects 1 part.

5)Now A takes the knife and divides the remaining cake into 2:3

6)B chooses 2 parts(i.e. he thinks 2/17th is worth and not 3/17th)

7)Now remaining cake ,3/17th must be divided in ratio 1:2. A again cuts in ratio 1:2

8)B chooses 1/17th part.Now he and A both expect 1 part each.

9)Now anybody can grab the knife and apply cut and choose method.

10)A and B both get 1/17th each.

Total number of cuts = 5

Here number of cuts would be less had A chosen 5 parts in step 4.

Suppose cake needs to be divided in ratio 5:12,5 parts for A and 12 parts for B

1)A(person recieving smaller part) takes the knife and cuts the cake in ratio 8:9

2)B chooses whichever parts he 'feels worth'.(He must choose one as he can't say 'both are not worth'!).

Suppose B has choosen 8 parts.Now he expects 4 parts of remaining cake.

3)Now B takes the control of knife and cuts the remaining part(9/17th) in ratio 4:5

4)A chooses 4 parts.Now he expects 1 part.

5)Now A takes the knife and divides the remaining cake into 2:3

6)B chooses 2 parts(i.e. he thinks 2/17th is worth and not 3/17th)

7)Now remaining cake ,3/17th must be divided in ratio 1:2. A again cuts in ratio 1:2

8)B chooses 1/17th part.Now he and A both expect 1 part each.

9)Now anybody can grab the knife and apply cut and choose method.

10)A and B both get 1/17th each.

Total number of cuts = 5

Here number of cuts would be less had A chosen 5 parts in step 4.

MH

Warren Dew

blacksmith

Ranch Hand

Ranch Hand

Posts: 1332

2

posted 12 years ago

If allowed three cuts for three people:

A uses two cuts to divide the cake into what he believes are equal thirds.

B then decides which of the three pieces is least desirable.

If C thinks the piece B doesn't like is at least 1/3 of the cake, C takes it. B then takes one of the remaining pieces, and A takes what's left.

If C agrees that the piece B doesn't like is less than 1/3, A takes the piece. Then, B "adjusts" the cut between the two remaining pieces, if he thinks they are unequal, by cutting a bit from the larger piece and putting it with the smaller piece. C then selects which of these two servings he thinks is better, and B takes the remainder.

Note that while this method guarantees that each person gets what he thinks is 1/3 of the cake, it doesn't guarantee that each person gets what he thinks is the largest (or tied for largest) piece, as the two person algorithm does. Intuitively it seems to me it should be possible to make that additional guarantee....

Edit: there's also the issue that some boys might prefer pieces that are in one piece.

[ August 23, 2004: Message edited by: Warren Dew ]

A uses two cuts to divide the cake into what he believes are equal thirds.

B then decides which of the three pieces is least desirable.

If C thinks the piece B doesn't like is at least 1/3 of the cake, C takes it. B then takes one of the remaining pieces, and A takes what's left.

If C agrees that the piece B doesn't like is less than 1/3, A takes the piece. Then, B "adjusts" the cut between the two remaining pieces, if he thinks they are unequal, by cutting a bit from the larger piece and putting it with the smaller piece. C then selects which of these two servings he thinks is better, and B takes the remainder.

Note that while this method guarantees that each person gets what he thinks is 1/3 of the cake, it doesn't guarantee that each person gets what he thinks is the largest (or tied for largest) piece, as the two person algorithm does. Intuitively it seems to me it should be possible to make that additional guarantee....

Edit: there's also the issue that some boys might prefer pieces that are in one piece.

[ August 23, 2004: Message edited by: Warren Dew ]

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

.I think trimming algo goes similar to the above.

1) A cuts the cake into 3 parts.(X1,X2,X3)

2)B arranges the pieces from largest to smallest.

3)B then cuts extra portion from largest piece.

4)So order is now say X2'(X2-E),X1,X3

4)C chooses any piece he wish.

5)If C does not choose X2',B must choose X2'

6)A chooses the remaining.

7)Extra portion E is again divided by B and chosen in order C,A,B

1) A cuts the cake into 3 parts.(X1,X2,X3)

2)B arranges the pieces from largest to smallest.

3)B then cuts extra portion from largest piece.

4)So order is now say X2'(X2-E),X1,X3

4)C chooses any piece he wish.

5)If C does not choose X2',B must choose X2'

6)A chooses the remaining.

7)Extra portion E is again divided by B and chosen in order C,A,B

MH

Stan James

(instanceof Sidekick)

Ranch Hand

Ranch Hand

Posts: 8791

posted 12 years ago

One of my favorite Sesame Street bits: Ernie cuts the cake in two pieces. He sees that one is a little bigger than the other, so he eats a little of it. Now the other one is bigger so he eats a little of it. Now they match, so he gives Bert one.

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi

Tina Desai

Ranch Hand

Posts: 365

Arjun Shastry

Ranch Hand

Posts: 1901

1

Arjun Shastry

Ranch Hand

Posts: 1901

1

Arjun Shastry

Ranch Hand

Posts: 1901

1

posted 12 years ago

A and B divide the cake in ratio 2:3 as discussed by earlier method.

Now C's total share should be 4/9

so C will ask each of A and B to cut their part in ratio 4:5 and C will take lesser part.

Number of cuts will be more as expected.

No perfect algorithm has been known if number of persons exceed.

[ September 02, 2004: Message edited by: Arjun Shastry ]

Now C's total share should be 4/9

so C will ask each of A and B to cut their part in ratio 4:5 and C will take lesser part.

Number of cuts will be more as expected.

No perfect algorithm has been known if number of persons exceed.

[ September 02, 2004: Message edited by: Arjun Shastry ]

MH

Chan San

Greenhorn

Posts: 7