Cut the cake

[Arjun Shastry]

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 atleast half of the cake.
Ofcourse knife is given for cutting.

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

[fred rosenberger]

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...

[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 ]

[Rachel Swailes]

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

[Arjun Shastry]

{
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.

[Rachel Swailes]

Yes, but boys will agree that the more cake they get the better it is for them. So why not team up to get the most cake?

[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).

[Arjun Shastry]

{
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.

[Arjun Shastry]

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.

[Deepak Mahbubani]

Peanuts for me. Too much for you kanjoos malbari.

[Hu Jiabao]

Deepak,aim here is to solve the problem and not to display your wealth.

[fred rosenberger]

Should we assume the boys will not team up? A and B cannot form an alliance to give C only 25%, while they split (perhaps un-evenly) the remaining 75%?

[Arjun Shastry]

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 ]

[Stefan Wagner]

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

A cuts a piece off.
If B likes to have it he can grab it.
If he doesn't like, C may have it.
(and so on, for more than 3 persons).
If nobody likes to have it, the cutter has to take it.

If A took the piece, B is to cut the next piece.
Else A is cutting again.

[Arjun Shastry]

.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 ]

[fred rosenberger]

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.

[Stefan Wagner]

You're right, Fred.
But Arjun's solution seems good to me.

[Arjun Shastry]

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.

[Warren Dew]

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 ]

[Arjun Shastry]

.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

[Stan James]

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.

[Tina Desai]

yum yum
Im A!

Tina

[Marc Peabody]

Solution:

I cut the cake.
I eat the cake.
A, B, and C keep quiet because I have the knife.

[Arjun Shastry]

You don't need to cut the cake to eat the whole in that case
[ August 27, 2004: Message edited by: Arjun Shastry ]

[Arjun Shastry]

Ok,Now suppose cake needs to be divided between A,B,C in the ratio 2:3:4,
How will be the approach?

[Arjun Shastry]

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 ]

[Chan San]

Arjun san,

You ask question and you reply. I do not understand.

[Arjun Shastry]

Originally posted by Chan San:
Arjun san,

You ask question and you reply. I do not understand.

But you understood the solutions given by different people,right?Thats the purpose of this forum.