Hmm. Since when has cutting the cake become such a problem? Quick Gun Murugan, Revolver Rita and Bogustatistix are wondering how to split the cheesecake sitting on the table. Each wants the maximum share possible. Since the three are alone at home, a neutral and certified third person (such as Agmark Mano (further clearance granted through ISO 9000 certification))cannot help in evenly splitting the cake. Each cannot be trusted to act in good faith (implicitly).
Question: Can you help by suggesting a mechanism to split the cake evenly?
Thursday, February 28, 2008
An eating dilemna
Posted by Mad Max at 11:21 PM
Subscribe to:
Post Comments (Atom)
Posts
15 comments:
You havent stated the size or shape of the cake or the specific likes and dislikes of people. If the size is too big, it doesnt matter because you can given enough to all of them and everybody will feel like they got the maximum possible... If the size is too small, no matter how evenly or unevenly it is split, everybody is going to be unhappy... Assuming some "reasonable" size, the shape might matter. It is probably tricky to split it equally... Contents could be another thing. If someone likes the topping-cream versus the first layer cake or the second layer or the nuts and raisins, they could get what they want (unequal portions) but still feel contended as long as they get what they want in the quantities they want... So, my answer is, it depends...:)
Wrong answer.... oops this is not my puzzle
:)
Yes, u r not the puzzle master...U r the Agmark Mano that cant be trusted...:)
I thought more...Mathematically speaking, throw away the cake... So, there is no cake...So, everyone gets equal share...Or, kill all 3...Now, the cake is divided by zero people and hence, virtually they get infinite cakes...:)
@ Mindframes: hmm..okie i guess we can add this without losing generality...the cake is of sufficient size,such that each one has incentive to get the largest piece and nuts/raisins etc are evenly distributed..apart from cutting the cake evenly, there are no other options available...killing or throwing away the cake is not an option :-)...
Now is there a mechanism to ensure even partition?
BTW: This is an extra credit problem that I have given to students in my class. The answer is very very simple.
okay, here is my take... I will ask revolver rita to cut the cake into 2 pieces (1/3 and 2/3) and ask bogustatistix to cut the 2/3 into 2 equal halves (1/3 each) [both of which are perceived by the cutter to be a fair share]. I will then ask quick gun murugan to pick 1 of the 3 pieces followed by the other 2... This, I think will make everyone feel like they got the fair share... In short, it is dividing the cake equally into 3 pieces but at the same time, involve the 3 people's perception of fair share...
@ Mindframes: you are close but still a little far. First, why make two people cut the cake? What is the advantage? Also you cannot request for equal shares because everybody is out to maximize their take... hehehe...ur so so close yet so far...here is a simple clue...think how you can solve the problem by making one person cut the cake...alternatively your solution (more complex) will work but you need to place one more restriction..what is that????
@mad-max: ur clue sounds complicated than the problem itself..:)
U r right...I think 1 person cutting the cake should be fine... The more I think about it, I am sensing some sort of a recursive solution. This is why...
Assume Person A cuts the cake into 3 pieces, say X,Y,Z. Now, we can ask everyone on their preference for what they want to choose. If everyone chooses one of the three without contention, problem is solved. Else, we may have a contention. There could be 2 cases. One in which everyone vies for a single piece and leave out the remaining pieces OR 2 people eyeing for a piece and the third person picks from one of the other 2 pieces (in which case, there is contention only among 2). When there is contention, we could again divide the cakes in to "n" pieces (n=2 or 3 in the above case) and repeat the same process. As long as someone picks the 1/3 equivalent of a piece, he will be taken out of the choosing process. If we do this recursively, eventually, we will have all 3 getting what they want, without preferential treatments....What do u think?
@ Mindframes: hmm..that cannot be the case becoz there is no space for contention...in fact there is no need for contention...the solution is way simpler...hmm in fact the answer is really staring at u (from ur previous solution)...just think a little out of the box there...
when I meant contention, what I was trying to convey is that, 2 people who think that a given piece is bigger/attractive in some sense...
I think this will be my last try..:)... I "think" solving for 2 people is easy. Person A divides a cake into 2 pieces and asks the other person to choose from one of the 2 pieces. This way, fairness is achieved for both parties concerned since the cutter divides based on his perception of fairness and the chooser decides based on what he thinks is a fair piece to him. When the number of people involved become more, divide them into subgroups of 2 and apply the same procedure. So, in this case, if we have X,Y and Z, XY will resolve first, followed by XZ and YZ. Out of 3 iterations, the splitting can be achieved. However, this is based on the premise that XY can resolve by 1 person cutting and the other person choosing a piece that he considers "attractive/fair"... In this scheme, for n-people contending, the number of iterations will be nC2...
@ Mindframes: Again you are quite close. In fact there is no need to divide into subgroups of two. Think of this case.
There are three people A, B and C. Suppose C is chosen to cut the cake (one person cuts), fairness can be ensured as long as C is the last person to take (order restriction). There are no other restrictions required.
Why is this so? Proof by contradiction. Suppose that C does not divide it equally and the cut is uneven, C knows that either A or B will take the largest piece followed by the second largest piece, leaving him with the smallest piece. Hence he knows that the maximum he can do is get 1/3 of the cake...therefore he just splits the cake evenly...
That's exactly what I tried to convey in my original solution. But, looking back at my comment, it looks like I didnt word it quite right... Also, involving 2 people makes it look convoluted.
@ Mindframes: Which is why i said..the solution was staring at your face...you did solve the problem...you can do it with two people also except that the order restriction will then change...
You two should get a room.
@mano: asingama pesadha da agmark mano...;)
@ Mano: Room aaa?????? Manooooooooooooooo....
Post a Comment