Forums Register Login

Cut the cake

+Pie Number of slices to send: Send
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 ]
+Pie Number of slices to send: Send
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...
+Pie Number of slices to send: Send
{
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 ]
+Pie Number of slices to send: Send
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
+Pie Number of slices to send: Send
{
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.
+Pie Number of slices to send: Send
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?
+Pie Number of slices to send: Send
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).
+Pie Number of slices to send: Send
{
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.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
Peanuts for me. Too much for you kanjoos malbari.
+Pie Number of slices to send: Send
Deepak,aim here is to solve the problem and not to display your wealth.
+Pie Number of slices to send: Send
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%?
+Pie Number of slices to send: Send
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 ]
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
.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 ]
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
You're right, Fred.
But Arjun's solution seems good to me.
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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 ]
+Pie Number of slices to send: Send
.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
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
yum yum
Im A!

Tina
+Pie Number of slices to send: Send
Solution:

I cut the cake.
I eat the cake.
A, B, and C keep quiet because I have the knife.
+Pie Number of slices to send: Send
You don't need to cut the cake to eat the whole in that case
[ August 27, 2004: Message edited by: Arjun Shastry ]
+Pie Number of slices to send: Send
Ok,Now suppose cake needs to be divided between A,B,C in the ratio 2:3:4,
How will be the approach?
+Pie Number of slices to send: Send
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 ]
+Pie Number of slices to send: Send
Arjun san,

You ask question and you reply. I do not understand.
+Pie Number of slices to send: Send
 

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.
Blueberry pie is best when it is firm and you can hold in your hand. Smell it. And smell this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com


reply
reply
This thread has been viewed 1960 times.
Similar Threads
passion crime: your opinion
Calculating a satisfying bite
The nominations for Most Beautiful Eyes are
Reputation of IT guys
how to cut a cake which is round into 8 equal pieces with just 3 strokes of a Knife??
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 16:18:59.