Tuesday, January 19, 2010

Pizza fairness

Tonight's pizza slicing theorem, from the New Scientist:
LUNCH with a colleague from work should be a time to unwind - the most taxing task being to decide what to eat, drink and choose for dessert. For Rick Mabry and Paul Deiermann it has never been that simple. They can't think about sharing a pizza, for example, without falling headlong into the mathematics of how to slice it up. "We went to lunch together at least once a week," says Mabry, recalling the early 1990s when they were both at Louisiana State University, Shreveport. "One of us would bring a notebook, and we'd draw pictures while our food was getting cold."

The problem that bothered them was this. Suppose the harried waiter cuts the pizza off-centre, but with all the edge-to-edge cuts crossing at a single point, and with the same angle between adjacent cuts. The off-centre cuts mean the slices will not all be the same size, so if two people take turns to take neighbouring slices, will they get equal shares by the time they have gone right round the pizza - and if not, who will get more?

(click to enlarge)

Of course you could estimate the area of each slice, tot them all up and work out each person's total from that. But these guys are mathematicians, and so that wouldn't quite do. They wanted to be able to distil the problem down to a few general, provable rules that avoid exact calculations, and that work every time for any circular pizza.

As with many mathematical conundrums, the answer has arrived in stages - each looking at different possible cases of the problem. The easiest example to consider is when at least one cut passes plumb through the centre of the pizza. A quick sketch shows that the pieces then pair up on either side of the cut through the centre, and so can be divided evenly between the two diners, no matter how many cuts there are.

So far so good, but what if none of the cuts passes through the centre? For a pizza cut once, the answer is obvious by inspection: whoever eats the centre eats more. The case of a pizza cut twice, yielding four slices, shows the same result: the person who eats the slice that contains the centre gets the bigger portion. That turns out to be an anomaly to the three general rules that deal with greater numbers of cuts, which would emerge over subsequent years to form the complete pizza theorem.

The first proposes that if you cut a pizza through the chosen point with an even number of cuts more than 2, the pizza will be divided evenly between two diners who each take alternate slices. This side of the problem was first explored in 1967 by one L. J. Upton in Mathematics Magazine (vol 40, p 163). Upton didn't bother with two cuts: he asked readers to prove that in the case of four cuts (making eight slices) the diners can share the pizza equally. Next came the general solution for an even number of cuts greater than 4, which first turned up as an answer to Upton's challenge in 1968, with elementary algebraic calculations of the exact area of the different slices revealing that, again, the pizza is always divided equally between the two diners (Mathematics Magazine, vol 41, p 46).

With an odd number of cuts, things start to get more complicated. Here the pizza theorem says that if you cut the pizza with 3, 7, 11, 15... cuts, and no cut goes through the centre, then the person who gets the slice that includes the centre of the pizza eats more in total. If you use 5, 9, 13, 17... cuts, the person who gets the centre ends up with less (see diagram).

Rigorously proving this to be true, however, has been a tough nut to crack. So difficult, in fact, that Mabry and Deiermann have only just finalised a proof that covers all possible cases. ...

Read the rest here. The science of pizza slicing advances. :)

No comments: