Monday, August 08, 2005
Your weekend brain teaser.
Now open for business.
There's an old puzzle that asks, if two pirates have a stash of treasure they want to divvy up, how can they do it so that each pirate is satisfied with his "half"? The answer is obvious -- one pirate divides the booty into two piles, and the other gets to pick which pile he wants.
Note that this, of course, doesn't guarantee that the two piles of swag will have exactly the same value. All it guarantees is that each of the two pirates should be satisfied with his share and neither has any right to complain after the division is over. But how well does this generalize to more than two people?
Imagine you have a group of children and a chocolate cake, and they want to divide the cake "evenly" amongst themselves. How can this be done so that, after all portions are allocated, everyone is satisfied with their slice? You can assume the existence of an extremely sharp knife that can make arbitrarily precise cuts if you need to.
(And, knowing my readership, no, the children are not allowed to murder each other to simplify the puzzle.)
SOLUTION: I think it's time to put all of us out of our collective miseries, so here's the solution. Note very carefully two things about this solution: 1) it works for an arbitrary number of children, and 2) it does not (as I stressed above) guarantee that every piece of cake is identical (that is simply impossible to attain), but it does guarantee that, once the cutting and allocation is done, no child has cause for complaint. Here goes.
Child 1 cuts a slice that he would allegedly be happy with. One at a time, every other child inspects the piece and, if they have no problem, approves it. Note how, regardless of the size of that piece, if all of the other children have no quarrel with that slice, that first child will get to keep it and everyone will be satisfied with it.
On the other hand, if, while the other children are examining the slice, any of them thinks that slice is unfairly large, they can trim however narrow a slice off of it they want and return that slice to the cake BUT ... that's their slice now. That is, the child who trimmed the slice is now forced to take ownership of that slice, and the remaining children still get to inspect that smaller slice the same way they did above. At the end of the inspection period for that slice, whoever has ownership of that piece gets to keep it.
Start all over again with slightly less cake and one fewer child.
Why this works, and can't be "gamed" by any child, is left as an exercise for the reader.
Subscribe to:
Post Comments (Atom)
10 comments:
turn off the lights... the kids wouldn't know the size of each other's portions. probably a bit messy though.
That's the protocol when you split a bag of herb with a friend.
Hey CC, what was the answer to the teaser of the Buddist kid needing exactly 45 minutes?
The solution to the incense sticks puzzle can be found here, in the comments.
One kid cuts the cake, once piece for each kid. Once the cake has been sliced, then all the other children select their pieces. The last kid to pick a piece is the cake slicer.
Assuming that the cake slicer wants to have as much cake as all the other kids, he will do his very best to ensure that all slices are the same size.
Nope.
Arbitrarily precisely cut the cake into equal pieces of whatever number is required. You seem to be saying this is OK with the "extremely sharp knife that can make arbitrarily precise cuts".
Assuming that isn't allowed, do you mean the children can cut pieces exactly the same size, but don't have sufficient grasp of fractions to do this in one step with the whole cake?
Could 5 children, for instance, cut 5 equal pieces from the cake and be sure to have cake left over? If so, duplicate the process on the leftover piece until infinity, or at least until cutting cake no longer leaves cake. The cutter gets the last crumb, he'll be hungry after making billions of cuts...
"Arbitrarily precisely cut the cake into equal pieces of whatever number is required."
Um ... if you could do that, it wouldn't be much of a puzzle. By saying that you could cut arbitrarily precisely, I meant that you could cut as thin a slice as you want to.
But, just using the eyeball technique, there's no way you can guarantee that you're cutting equal-sized slices, so
that's not an option.
NOTE: Read the puzzle again. I never said the slices had to be exactly equal, only that the children had no right to complain about being treated unfairly after the cutting was done.
It's the same with the two pirates, remember? If the first pirate divides the treasure into two obviously-unequal piles, and the second pirate takes the larger pile, the first pirate has no right to complain since he did the division initially.
Okay, I'm sure the details aren't perfect here. There are ways to game this system, and particularly for a child who isn't interested in cake at all to create chaos among those who do. Also, I'm going to arbitrarily say 8 children, because talking in terms of "N" children gets awkward.
Kid #1 cuts the cake into 8 pieces. Like in the pirate case, Kid #1 will be the last to recieve a piece of cake, so his enlightened self-interest should drive him to be reasonably fair.
The plate then passes down the line. Each Kid #2-#7 can opt to trim the largest piece down to a "fair" size (in his own estimation). For reasons that will be made clear later, it is in each child's interest to act honestly.
At the end of the line, Kid #8 gets to simply choose his favorite piece.
The plate then passes back up to Kid #7, who will find himself in one of the following situations:
1) He declined to trim any piece of cake on the first pass. In this case he may simply select the best remaining piece of cake. By not trimming, he implicitly vetted the division, and has no cause for complaint no matter what Kid #8 chose.
2) He trimmed a piece of cake, but Kid #8 took that one. This could happen either because Kid #7 did not trim enough off the biggest piece (in which case it's his own fault he doesn't end up with that piece), or because he trimmed it perfectly fairly and Kid #8 selected it by chance (in which case there should be an equally big piece left on the plate for Kid #7 to choose). Either way, in this case Kid #7 may choose the best piece remaining on the plate.
3) He trimmed a piece of cake, and Kid #8 did not take it. This could happen because either Kid #7 trimmed too much off the largest piece (making it less attractive) or because he trimmed it perfectly fairly, in which case it's as good as any other. Either way, if the piece Kid #7 trimmed is still on the plate, then he is compelled to take that piece. This should be acceptable unless Kid #7 intentionally trimmed the piece very small, in which case he earned his small piece.
The plate returns back up the line, with these rules applied to each kid in turn. It was in each child's interest to be fair on the "trimming" pass, because if he trimmed a piece too large, some kid down the line will claim it, but if he trimmed it too small, he'll be stuck with it on the return trip. Kid #1 (the cutter) is encouraged to be fair because he will get the smallest piece remaining at the end of the process.
In the theoretical case, division of the trimmings could proceed in the same way until the trimmings were so small as to be inconsequential to all concerned, but as this is a birthday party and cake we're talking about, all trimmings will be passed to Dad, who will be able to dispose of them appropriately.
Post a Comment