Dividing a portion three ways, fairly

Factual Questions
21

HC, I think you got it! I’d just change the reasoning for C: He won’t be content just because the others cut halves as best they could; they might still do a bad job and cut a big and a small piece. But whatever they do, C has the opportunity to cut a perfect third of the big piece plus a perfect third of the small piece, which will get him a perfect third of the whole pie!

That’s envy-free in my book. What I love about this solution is that it doesn’t require any trimmings to be mushed or discarded.

22

Envy-free and totally foolproof:

Take food to nearest Mom. Have HER make the cuts, and make it clear to all three kids that any bickering over who got the largest piece will result in MOM taking back the whole mess and eating it herself.

Veni, Vidi, Visa … I came, I saw, I bought.

23

Here is another fun fact. The people that came up with the solution knew even before trying that there had to be a solution to this problem. That’s because there’s another theorem (proven beforehand) that stated that there had to be a configuration that would give everyone at least as much as they would feel is fair. That’s not very clear, let me give an example:

If you have four people dividing a cake, there is a way to cut it so that every person gets at least 25%. Think about it, that sounds rather strange. What’s taken into account is ‘perceived value’. Everyone has a different way of evaluating the value of cake slices. Some people will prefer a piece that has more cream on the top, some want more cherries, others want more of those colourful things they sprinkle on cakes, etc.

What that means is that once they found the correct method of cutting the cake, not only were they sure everyone felt they would receive a fair share, but some people would feel they had received a ‘better’ slice than the others according to their value system.

Isn’t it great? They also said that the theorem could be applied to most disagreements they could come up with in real life, not just cakes. The notable exceptions included when one of the participants tried to eliminate the others rather than cut the cake, à la Serbian-kill-the-Albanians.

Only humans commit inhuman acts.

24

HC - Good job! Here’s a solution that would work with less cutting:

A cuts a piece of pie equal to 1/3
B has 2 options:

  1. Take the piece “A” cut, or
  2. Refuse the piece “A” cut.

If “B” chooses option 1, then “C” cuts the remainder in half. “A” gets first choice of remaining two pieces.

If “B” chooses option 2, “A” must take the initial piece. “B” then cuts the remainder in half and “C” gets choice.

“A” knows the first cut must be very close to 1/3. Too large and “B” claims it, leaving less for “A” and “C”; too small and “B” refuses it, forcing “A” to accept the smallest piece.

Nah, I think I like yours better.

The overwhelming majority of people have more than the average (mean) number of legs. – E. Grebenik

25

Dr J: Not envy-free. Suppose A cuts too large a piece, B takes it and C is envious. HC’s is better.

26

Hey, let’s push the envelope and see if we can generalize the solution!

I just noticed that HC solved the 3-way cut by first performing the 2-way cut and then having the third person cut all pieces into 3 sub-pieces (let me call these slices), of which the original owners can keep 2 each.

Now my generalization is as follows: To achieve an envy-free n-way cut, first perform an (n-1)-way cut among the first n-1 persons. Now the n-th person cuts all existing pieces into n slices, of which the original owners keep n-1. The rest goes to the n-th person!

Example n=3: see above.

Example n=4: A, B, and C make the proven three-way cut. Each now has two pieces. D cuts all pieces in four slices, so there’s eight slices for each of the three, of which each can keep six. Two each go to D, who also has six pieces altogether. (I guess A, B, and C must keep exactly three slices of each piece, not all of one piece and just two slices of another.)

Example n=5: A, B, C, and D make the four-way cut, and each has six pieces. E cuts those into five slices each, or 30 slices per capita, or 120 slices altogether…

I see this leads to a large number of small pieces, viz. n! pieces or (n-1)! pieces per capita. Looks like mush after all…

Now how do we prove this scheme is envy-free? Would you agree with me that if n-1 persons have found an envy-free cut, and each of these makes an envy-free (though uneven) cut with the n-th guy, the whole cut is envy-free?

**Induction is fun!! **

(“Induction, destruction – who wants to die in a WAR?!” – who sang that before Bruce Springsteen?)

27

Headless Cow says:

As I said before, it’s a lot easier to find the faults in a method that to devise a correct solution. The answer above is again not “envy-free”.

Person B could end up with a larger portion than person A (in person A’s opinion), because person A might think that C made two of the three pieces bigger when dividing B’s half.

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.

28

TheIncredibleHolg says:

Since HeadlessCow’s solution is not “envy-free”, generalizing it will not give you a correct answer for n portions.

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.

29

Here’s a response I came up with that pissed off a math professor when he posed the same question. (3 equal portions in 2 cuts)

Cut pie in half. Move 60 degrees to either side then cut straight through the center. It will leave two pieces totalling 120 degrees of the total a piece and two pieces totaling 60 degrees a piece (or 120 together). Altogether that totals 360 degrees and nothing for chance. The professor said it was wrong by changing what he had written on the board. He said that two pieces at 60 degrees was not the equivalent of 120 degrees.

SC

“People’s Poet don’t die, we’ll kill ourselves if you do, but first we’ll take off all our clothes.” The Young Ones

30

Dang! All that work for nothing! Just as I thought I could almost feel the Nobel Prize in my hand…

I suppose you also answered my final question: A series of envy-free cuts between two persons each does not lead to an overall envy-free solution because one person can be unhappy with a division between two others that s/he wasn’t even involved in.

(“Induction, destruction…” – even more a propos than I thought! Again: who sang that first?)

31

Forgive me if I get this wrong, folks; I’ve read every post on this thread and think I’ve incorporated them, but . . .

Anyway, I think what’s being missed here is that it’s not merely the slicing, but the selection which must be out of each individual’s control to motivate them to make fair slices. Consider the primal case: A & B. A makes the cut, B selects. But think of this not as B selecting his/her piece, but as B selecting A’s piece.

The way I see it, A & B do the slicing into sixths; C selects the slices for A & B, and must take what is left.

32

Apparently this mathematic problem was solved in 1960. I did a quick search but was not immediately able to find the solution anywhere. Here’s a strange related link, though: http://www.math.hmc.edu/~su/fairdivision/calc/

33

Yes. A short discussion of the problem can be seen at
[urlhttp://saturn.vcu.edu/~gasmerom/MAT131/fairdivision.html

At that page I found the name for the 3-way envy-free division method I quote above: The Selfridge-Conway method.

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.

34

OK, you know what I meant:

http://saturn.vcu.edu/~gasmerom/MAT131/fairdivision.html

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.