[bushindo]

3 people are dividing a cake. Each person wants as much cake as possible for himself, but each person thinks that the other two might be colluding. Lets call the three A, B, and C.

A suggests that he will cut the cake into 3 portions, and then C will pick his piece from the 3, and B then would pick his choice from the 2 remaining. and A takes the last piece. B objects to this scheme, saying that A can cut the cake into 1 large piece, and 2 smaller equal pieces. C then would have the largest piece, and B would have to take the smaller piece. In fact, B claims, If A and C were really colluding, this method would allowing them to get the entire cake to share among them two.

Given this distrusting atmosphere, is there a way to divide the cake so that each person is satisfied? Any proposed method would have to convince each person that he would get his fair share even if the other two were colluding.

I know of two solutions to this, but I wouldn't be surprised if the den can come up with a couple extra solutions.

Edited May 28, 2009 by bushindo

[Guest]

if the cake is round..

Have each guy make 1 cut from the outside to the center of the cake.

The guy who cuts first gets to pick first (since he cuts first he has no advantage of the outcome). The next guy will make an even cut since he knows that the first guy picks first. and the third guy will make an even cut for the same reason. If the last two guys try to make awkward cuts they would just screw themselves since the first guy who cut gets first pick.

-or-

If after an hour of trying to decide, then A can just throw it against the wall and ask ok who wants to pick first now!

[bushindo]

My husband cracked me up when he came up with this solution....

The guy with the knife kills the other two and keeps the cake for himself.

I nominate this solution to the Hall of Fame.

[Guest]

My husband cracked me up when he came up with this solution....

The guy with the knife kills the other two and keeps the cake for himself.

I don't think the two dead people would be satisfied with this result which I think was a requirement by the OP. Otherwise I'd say its a foolproof solution!

[plainglazed]

d

I was working on a solution like this, but discarded it because -

if A makes a 49% 48% 3% split, he'd wind up with 48% of the cake, while B and C each get 26%,

-unless B & C collude so that A winds up shafting himself, which is rather poetic

Right of course. Maybe if it's changed as follows:

A cuts the cake in what he feels are three equal pieces. B and C place secret ballots as to which piece they want. They reveal their choice at the same time. If they each choose different pieces, problem solved as all is fair. If they choose the same piece, A chooses one of the other pieces. B and C are then told to place another secret ballot as to which of the two they did not choose should go to A. If they pick the same A gets that one but if they pick different then A gets the slice that B and C had chosen in the first ballot. Now there are two remaining pieces. B cuts one in half and C chooses; C cuts the other in half and B chooses.

I think this revision motivates A to cut the cake as close as possible into thirds. Hard to visualize for me though...

[Guest]

Hey, I just registered so I could offer an answer to this question.

Have person A cut the cake into thirds.

*Person B and C both pick what they think is the largest slice.

**If B and C pick different slices then everyone is happy.

**If B and C pick the same slice then they each need to pick what they think the second biggest slice is.

***If B and C agree on the second largest slice, then A gets the smallest slice. B and C then would each pick a slice, cut it in half, then pick half from the other persons slice.

***If B and C both pick different slice as second largest, then either B or C needs to cut the largest slice in half and the other would select what half they want. Then for B's second largest slice B would cut it in half and A would choose what half he wants. And for C's second largest slice do the same thing, C cuts it in half and A gets to select the largest.

Hope that works out.

Edited May 28, 2009 by elrac

[Guest]

-or-

If after an hour of trying to decide, then A can just throw it against the wall and ask ok who wants to pick first now!

if the cake is round..

Have each guy make 1 cut from the outside to the center of the cake.

The guy who cuts first gets to pick first (since he cuts first he has no advantage of the outcome). The next guy will make an even cut since he knows that the first guy picks first. and the third guy will make an even cut for the same reason. If the last two guys try to make awkward cuts they would just screw themselves since the first guy who cut gets first pick.

The first two could collude against the third. The second guy makes the cut very close to the first. No matter where the third guy cuts he's stuck with a slice that size or smaller, and the first two just share after.

I don't think the two dead people would be satisfied with this result which I think was a requirement by the OP. Otherwise I'd say its a foolproof solution!

I challenge you to get either of the dead people to state their objections. d:

[Guest]

Let each person cut. A and C cut in the vertical direction while B cuts in the horizonal direction. This will result in 18 pieces of cake. When choosing each person will get a chance to go first and each person will select last for the section they are responsible for cutting.

[Guest]

Let each person cut. A and C cut in the vertical direction while B cuts in the horizonal direction. This will result in 18 pieces of cake. When choosing each person will get a chance to go first and each person will select last for the section they are responsible for cutting.

This doesn't work, because the horizontal cuts are not necessarily even.

[Guest]

They don't have to be even.... that is the point. The is the problem in the first place no one trusts someone to cut even. In this case each person will get to cut. if they make two large pieces and one small one, most likely they will get stuck with the small section from their cutting direction because they choose last. But hae the chance to make up ground when they get to choose first. No one will want to be screwed so will do a good job at cutting and if they dont it still isnt possible to cordinate with another person because everyone will get a chance to make a first choice. they will end up with 9 total pieces of cake. three sections each containing 3 pieces.

[Guest]

3 people are dividing a cake. Each person wants as much cake as possible for himself, but each person thinks that the other two might be colluding. Lets call the three A, B, and C.

A suggests that he will cut the cake into 3 portions, and then C will pick his piece from the 3, and B then would pick his choice from the 2 remaining. and A takes the last piece. B objects to this scheme, saying that A can cut the cake into 1 large piece, and 2 smaller equal pieces. C then would have the largest piece, and B would have to take the smaller piece. In fact, B claims, If A and C were really colluding, this method would allowing them to get the entire cake to share among them two.

Given this distrusting atmosphere, is there a way to divide the cake so that each person is satisfied? Any proposed method would have to convince each person that he would get his fair share even if the other two were colluding.

I know of two solutions to this, but I wouldn't be surprised if the den can come up with a couple extra solutions.

I remember reading about a guy who does this kind of problem solving for a living in Discover Magazine back in 1995

http://discovermagazine.com/1995/mar/dividingthespoil479

The answer to this "cake shared by three" problem is explained in the article

[Guest]

This is true... this will work. But now you ask yourself, who is going to eat the trimmings? because we aren't going to throw away any cake are we?

[Guest]

Well this is the first thing that popped into my head:

Have A cut the cake into three equal pieces then label them 1, 2, 3. Then C writes each number on a piece of paper, equal in size. B can pick the first number and one of the others can go next...it doesn't matter who because B thinks A and C are colluding with each other.

[Guest]

How about this:

1. A cuts a piece of size 1/3, passes it onto B.

2. B looks at the piece, if it is bigger than 1/3, he trims it to 1/3 (returning the trimmings to the big cake). After B is satisfied he passes the piece to C.

3. If C considers the piece is at least 1/3, he takes it, otherwise the LAST person (A or B) to trim the piece is forced to take it.

4. Divide the remaining 2/3 of cake among the remaining 2 people by the "usual" method (one cuts, the other picks).

[Guest]

How about this:

1. A cuts a piece of size 1/3, passes it onto B.

2. B looks at the piece, if it is bigger than 1/3, he trims it to 1/3 (returning the trimmings to the big cake). After B is satisfied he passes the piece to C.

3. If C considers the piece is at least 1/3, he takes it, otherwise the LAST person (A or B) to trim the piece is forced to take it.

4. Divide the remaining 2/3 of cake among the remaining 2 people by the "usual" method (one cuts, the other picks).

What happens if B is dissatisfied from the start? E.g. A&C are colluding, so A's first slice is 1%. B has no recourse -- B passes to C who claims to be dissatisfied, and B's pegged with 1% of the cake, leaving 99% for A&C to divide. If the method is modified to offer B a "dissatisfied" option which forces A to take the first piece cut, what if A&B are colluding and A cuts a 99% slice with which B claims to be dissatisfied?

I think the collusion-worry is an extremely interesting and too-often ignored part of the problem. Nice one, bushindo.

[Guest]

A cuts the cake in two. B chooses one of the pieces and cuts it in two. C chooses one of the three pieces for himself. Then, B chooses one of the remaining two pieces for himself. The remaining piece goes to A.

[Guest]

A cuts the cake into two pieces.

B picks a piece.

A and B each cut their piece into thirds.

C picks a piece from both A and B

Let me be the first to say that I believe you have a beautifully simple, workable, collusion free solution!

[Guest]

A cuts the cake into two pieces.

B picks a piece.

A and B each cut their piece into thirds.

C picks a piece from both A and B

Let me be the first to say that I believe you have a beautifully simple, workable, collusion free solution!

I don't think this would work. If A and B are in collusion, or if A is just bad at cutting cake, then A could cut one large piece and one small piece. Then if B and A both cut theirs into perfect thirds then the best C could get is one third of a big piece and one third of a small piece. B would have two thirds of a large piece. In fact, B would always have a better outcome then C.

[Guest]

I say that they count to 3 and then the all just start stuffing their faces, so the one who eats the slowest and grabs the slowest, just gets the least!

[Guest]

I don't think this would work. If A and B are in collusion, or if A is just bad at cutting cake, then A could cut one large piece and one small piece. Then if B and A both cut theirs into perfect thirds then the best C could get is one third of a big piece and one third of a small piece. B would have two thirds of a large piece. In fact, B would always have a better outcome then C.

A's piece (half) plus B's (half) piece = 100% of the cake, so if they cut their (halves) into perfect 3rds, 1/3 A + 1/3 B = 1/3 of the cake, no matter how lopsided A's first cut is.

If A makes the first cut unevenly, B and C get more.

If A or B cut the thirds unevenly, C gets more.

If C chooses wisely, he cannot have less than 1/3 of the total cake. Any lopsided cuts result in a loss by the cutter, and nothing to be gained by any collusion.

I could be wrong, I have been before. If you think I am, please explain.

Please note it was not my solution, I just think it works.

I had a (unposted) solution, but mine was complex, so simple rules!

Kudos psycho!

[Guest]

What happens if B is dissatisfied from the start? E.g. A&C are colluding, so A's first slice is 1%. B has no recourse -- B passes to C who claims to be dissatisfied, and B's pegged with 1% of the cake, leaving 99% for A&C to divide. If the method is modified to offer B a "dissatisfied" option which forces A to take the first piece cut, what if A&B are colluding and A cuts a 99% slice with which B claims to be dissatisfied?

I think the collusion-worry is an extremely interesting and too-often ignored part of the problem. Nice one, bushindo.

Nop. By the original method, last person to trim/cut the slice is forced to take it (if all subsequent players passed on it). So, if B and C are unsatisfied from the start, A gets the slice.

If A cuts a 1% slice, A will be stuck with it and B and C now get to divide among them 99% of the cake. If A cuts a slice of 99%, B will trim it so C doesn't get it, regardless of whether B is friend of A or C is friend of A.

[Guest]

A's piece (half) plus B's (half) piece = 100% of the cake, so if they cut their (halves) into perfect 3rds, 1/3 A + 1/3 B = 1/3 of the cake, no matter how lopsided A's first cut is.

If A makes the first cut unevenly, B and C get more.

If A or B cut the thirds unevenly, C gets more.

If C chooses wisely, he cannot have less than 1/3 of the total cake. Any lopsided cuts result in a loss by the cutter, and nothing to be gained by any collusion.

I could be wrong, I have been before. If you think I am, please explain.

Please note it was not my solution, I just think it works.

I had a (unposted) solution, but mine was complex, so simple rules!

Kudos psycho!

If A cuts unevenly and B cuts evenly, then B gets more cake than C. C would not be happy with this outcome even if he ended up with more then a third of the cake because he had no opportunity to end up with as much cake as B did. If you let C take any two pieces instead of having to take one from each person then you wouldn't have this problem, you would have other problems.

Example:

The three of them have 100% of a cake.

A, being bad at cutting, and not in collusion with B, cuts the cake into 5%, 5%, 90% pieces.

B picks the 90% piece and cuts it into 30%, 30%, 30% pieces.

C gets 5% from A and 30% from B giving him 35%, while B has 60%.

You end up with: A is an idiot that can't tell the difference between 5% and 90% but is happy, B is happy because his piece is huge, and C is unhappy wishing he went second.

Edited May 29, 2009 by elrac

[Guest]

If A cuts unevenly and B cuts evenly, then B gets more cake than C. C would not be happy with this outcome even if he ended up with more then a third of the cake because he had no opportunity to end up with as much cake as B did. If you let C take any two pieces instead of having to take one from each person then you wouldn't have this problem, you would have other problems.

Example:

The three of them have 100% of a cake.

A, being bad at cutting, and not in collusion with B, cuts the cake into 5%, 5%, 90% pieces.

B picks the 90% piece and cuts it into 30%, 30%, 30% pieces.

C gets 5% from A and 30% from B giving him 35%, while B has 60%.

You end up with: A is an idiot that can't tell the difference between 5% and 90% but is happy, B is happy because his piece is huge, and C is unhappy wishing he went second.

A first only cuts the cake once, and is selfishly motivated to do his personal best for 50/50 split (That's 2 pieces, not 3),

because otherwise he loses and no 2 party collusion can get him more than a final 33.33%, which careful cutting will get him anyway.

B selects (the bigger if he detects a difference) ~ half of the cake

A and B each cut their half into thirds, (each piece now ~ 1/6) again doing their best, because after C picks his piece, the two ~1/6 pieces each have left are their cake.

After the first slice and pick, A & B do not choose or get remnants from each other's 'half'

again, this was psycho's solution.

Edited May 29, 2009 by bobbydl

[Guest]

again, this was psycho's solution.

A first only cuts the cake once, and is selfishly motivated to do his personal best for 50/50 split (That's 2 pieces, not 3),

because otherwise he loses and no 2 party collusion can get him more than a final 33.33%, which careful cutting will get him anyway.

B selects (the bigger if he detects a difference) ~ half of the cake

A and B each cut their half into thirds, (each piece now ~ 1/6) again doing their best, because after C picks his piece, the two ~1/6 pieces each have left are their cake.

After the first slice and pick, A & B do not choose or get remnants from each other's 'half'

Ahh, I did mess up a bit, but I still think it is a bad deal for C. I guess it goes to the idea of what would be considered fair for each person. If A messes up the cut, like by making the first cut 10% and 90%, then B and C should both feel that they get the same amount out of the bigger piece.

Example redux;

A cuts the cake into pieces that are 10% and 90%, he seems to think they are the same size although B and C both think he is an idiot.

B takes the 90% piece and cuts it into 30% 30% 30%, while A cuts his 10% correctly this time into 3.3%, 3.3%, 3.3% .

C has to pick one from each, so he ends up with 33.3% while B still gets 60%, and A starts to realize he made a mistake with his 6.6%, but it was his own fault so it doesn't matter.

Stated a different way, the problem I see with this method is that the actions of A can make it so that B will get a bigger piece than C. Although C can get more then 33% of the cake if A messes up, C will still not think he got his fair share because B got a bigger piece. C has no way of remedying this situation.

Edited May 29, 2009 by elrac

[Guest]

again, this was psycho's solution.

A first only cuts the cake once, and is selfishly motivated to do his personal best for 50/50 split (That's 2 pieces, not 3),

because otherwise he loses and no 2 party collusion can get him more than a final 33.33%, which careful cutting will get him anyway.

B selects (the bigger if he detects a difference) ~ half of the cake

A and B each cut their half into thirds, (each piece now ~ 1/6) again doing their best, because after C picks his piece, the two ~1/6 pieces each have left are their cake.

After the first slice and pick, A & B do not choose or get remnants from each other's 'half'

Thanks bobbydl!

[CaptainEd]

I'm surprised by all this.

Kidsrange et al posed the answer I'd heard of, and I was very surprised to find a more complicated and crumby approach pointed to by gadaju: http://brainden.com/forum/index.php?showto...st&p=172109

Kidsrange et al posed both the answer and the riposte to the concern about collusion. My only quibble is with the rationale. Here's my slight restatement of it, as I understand it.

Might as well be rectangular as circular, makes the geometry easier to visualize. Knife is pointed North-South. Player A is permitted to prepare to cut his/her own piece, as follows: Starting with knife at East edge of cake, A starts poising it further to the west. The further west he/she goes, the more he/she will get. Anybody (call them B) who believes A is getting too much can yell STOP.

This means that B feels the current knife location would yield a piece too good for A. B gets that piece.

(B should be happy, getting a piece that was too good for A.

C,D,et al, should be happy, as they think there are even larger pieces to come. If they didn't think so, they would have yelled STOP earlier, to prevent A from getting too big a piece.

A should be happy, because someone else got a piece smaller than A was going for.)

A continues moving the knife. Either additional players STOP and grab slices, or eventually A decides to stop and cut a slice. That slice clearly shouldn't bother any players, as the folks who already have pieces were clearly content with their size and the remaining people must think they're going to get larger pieces from the remaining cake. (A new volunteer knife-wielder is chosen; there is no advantage or disadvantage to being wielder or watcher)

Collusion:

Players could yell STOP too soon (ie. taking pieces that are too small), but that doesn't hurt A or any downstream players, it only hurts themselves.

The rationale is not fairness, but rather informed greed.

Edited June 17, 2009 by CaptainEd