Discussion Forum

Don't Fight over the Cake (Weekly Brain Potion Discussion)

Picture of ZIML Admin
Don't Fight over the Cake (Weekly Brain Potion Discussion)
by ZIML Admin - Friday, October 27, 2017, 11:40 AM

This week's problem:

Michael and his twin sister Michelle attend their friend's birthday party.

Being polite, Michael and Michelle let all the other guests get cake before taking their pieces. Unfortunately by the time they go to get cake, there is only one piece left!

The last piece of cake has some places with more frosting and some places with more sprinkles. Michael and Michelle want a fair way to divide the cake into two pieces for them to eat. They also have different preferences in what they want on their cake. Therefore cutting the piece evenly in half may not work! Each twin should think their piece of cake is at least as good as the piece the other gets.

Can you help Michael and Michelle decide how to divide the piece of cake?

Please share any thoughts or questions you have below. We'll monitor the responses and give our thoughts as well!

Picture of Dubya Tomorra
Re: Don't Fight over the Cake (Weekly Brain Potion Discussion)
by Dubya Tomorra - Friday, October 27, 2017, 6:25 PM

The problem said "Each twin should think their piece of cake is at least as good as the piece the other gets." so the twins don't have to cut the piece of cake evenly. They just need to state their preferences (icing or sprinkles) and divide accordingly. This doesn't sound like a math problem though...so I am not sure.

Picture of Ray Zhao
Re: Don't Fight over the Cake (Weekly Brain Potion Discussion)
by Ray Zhao - Friday, October 27, 2017, 7:44 PM

They both should get half of the sprinkle part, the frosting, and the part with nothing.

Re: Don't Fight over the Cake (Weekly Brain Potion Discussion)
by Alex Yi - Saturday, October 28, 2017, 4:56 PM

Isn't this the Cutting Cakes problem?

The problem, here, is that while Michael might see frosting and sprinkles as equivalent, Michelle might not see them as such (for example, sprinkles are twice as tasty as frosting), or vice versa, or any of infinite other possibilities. So, of course, it's not as simple as it first looks, to divide evenly.

The classic solution, I think, is to let one person divide the cake, and let the other person choose. If you're the cutter, then your optimal strategy is to cut it into what you see as equivalent halves, and if you're the chooser, you just pick whichever one seems best to you (or a random one if both seem equal). This is fair, since if the cutter cuts the cake into unequal halves, he runs the risk of having the chooser take what he sees as the "bigger" half.

The problem here, is that the solution isn't symmetric: i.e. the cutter is guaranteed at most half of the cake, while the chooser is guaranteed at least half of the cake, so the squabble resumes over who gets to be the chooser.

My solution, thus, goes like this: First, we decide on an axis - that is, a line that all cuts must be made parallel to. Then, both people get knives, and they simultaneously cut the cake in a straight line according to what they think is a half-way point, parallel to the axis. (The Intermediate Value Theorem proves that such a line always exists, no matter the person's preferences.) Then, we have two possibilities: either the cuts happen to be the same; in which case either side can be given to either party indistinguishably, or they happen to be different. Assuming a vertical axis, in this case, we give the leftmost piece to the left person, the rightmost piece to the right person, and we repeat the algorithm with the center piece.

There are three benefits to this system, over the above one: first, this method is symmetric, unlike the above method, second, if played fairly, this method guarantees at least half of the cake to each person, and third, this method is also impossible to cheat, since using your cut to divide into unequal halves runs the risk of you getting the smaller half, as above.

There are, however, two problems: first, the method is not guaranteed to terminate, so we could keep dividing the last breadcrumb into infinitely smaller pieces, and second, it's rather difficult to implement simultaneous cutting in real life. The first problem could be resolved with the fact that in real life, after a few iterations, we reach the "scraps and crumbs" of cake, and by this time, it's more efficient to just clean up the crumbs and eat what you have. The second, however, is a bit trickier: one solution would be to take a birds-eye view image of the cake, print it twice, and have each person draw a line corresponding to their cut, and then cut along that line.

(The above assumes, in regards to cheating, that neither person knows the others' cake preference; if one knew the others, it would be much easier to cheat. How exactly is left as an exercise to the reader.)

Re: Don't Fight over the Cake (Weekly Brain Potion Discussion)
by Darius Fan - Sunday, October 29, 2017, 1:04 PM

So if Michael likes sprinkles better and Michelle likes frosting better, Michael should get all the sprinkles and Michelle will get all of the frosting. Then they will all like what they got and would consider each piece 100% to their satisfactions. If the both like the same thing, then they would split what they both like in half so that they would each have 50% satisfaction. So in this example, if the left side had more sprinkles and the right side had more frosting, Michael would get the left side if he liked sprinkles and vise versa. Then each sibling would like their slice like 80% percent each? That would add up to 160%? But then again, you can't count happiness while having cake :) -Darius

Re: Don't Fight over the Cake (Weekly Brain Potion Discussion)
by Alex Yi - Sunday, October 29, 2017, 6:58 PM
The problem here, though, is that you're mixing scales: the first 80% comes from one person's perspective, while the second 80% comes from the other. I don't think that's allowed. Nice cake, though!
Picture of Allen weng
Re: Don't Fight over the Cake (Weekly Brain Potion Discussion)
by Allen weng - Sunday, October 29, 2017, 2:38 PM

They should both state their preferences and then average out the cake.

The two scenarios:

Michael likes both, but Michelle likes frosting.

Then Michelle gets something around a 4:1 proportion of frosting to sprinkles, while Michael gets vice versa.

Since Michael is neutral, he does not care what he gets, but wants a little of each. This allows the cake to be split while ensuring they each get the same amount of cake.

This can be slightly changed to create scenarios where a. Michael likes frosting and Michelle likes both, b. Michael likes sprinkles and Michelle still likes both, or c. Michelle likes sprinkles and Michael likes both.

All of these are just where on person has a preference and the other does not.


The other scenario would be they each like completely different things, in which case the obvious solutions would be to split the cake among a line separating the cake into sprinkles and frosting,and make sure the two areas are the same. If the areas are different. cut out the extra part so both are the same, then cut that extra piece in half and split it.

Picture of John Lensmire
Re: Don't Fight over the Cake (Weekly Brain Potion Discussion)
by John Lensmire - Friday, November 3, 2017, 1:00 PM

Thanks everyone for participating!

Special kudos to Alex Yi for his discussion, and Alex is correct that this is a take on a classic problem in Game Theory about dividing something fairly when people have differing preferences. Game Theory is a way to use math to help understand people's decision making and is famous for its many applications in economics.

The frosting and sprinkles were just examples here, you can think of even more scenarios, such as a piece of cake that is a mix of chocolate and vanilla or even a piece of cake that is taller in some places than in others. The problem (and solution) can also apply to other scenarios, such as a pizza that has different toppings in different places or even dividing chores for the week.

In understanding the solution it can also be helpful to think of the problem with both Michael and Michelle acting greedy. In other words, both would like to have as much cake as possible! Note that Alex's solution still works in this scenario:  If Michael is the one cutting the cake, it is in his best interest to cut it "fairly", because if he cuts it unfairly he is risking Michelle picking the "better" piece.

Those interested can try to extend the solution to three or more people. It gets a little more complicated, but the idea is the same!