Fair shares and pieces of pizza

I’m grateful to Dr Richard Morrison for calling my attention to a worthy addition to the mathematics of food and drink. It’s one of several nice problems in pizza slicing; this one was originally posed by Prof. Peter Winkler in 2008, and is as follows.

Alice and Bob share a pizza. The pizza is sliced by cuts from the middle to the crust. There may be any number of pieces, which may be of various sizes. To eat the pizza Alice and Bob have to stick to the following politeness protocol:

  1. They pick pieces in an alternating fashion;
  2. Alice starts by eating any piece of the pizza;
  3. Afterwards only pieces adjacent to already-eaten pieces may be picked.

This means that on each turn (except the first and the last) a player has two available pieces from which to pick.

How should Alice pick her pieces to eat the largest possible portion of the pizza?

An analysis of this original version of the problem was presented by Kolja Knauer, Piotr Micek and Torsten Ueckerdt in a paper entitled “How to eat 4/9 of a pizza”. If the number of slices is even then, unsurprisingly, Alice can always guarantee that she will get at least half the pizza. One might think that since Alice gets first choice she will always be able to eat more than Bob if the number of slices is odd — but, remarkably, this is not the case. It turns out that if there are an odd number of slices then the best that Alice can guarantee is that she will get 4/9 of the pizza! (The original example of this was given by Peter Winkler; what Knauer, Micek and Ueckerdt managed to do was to prove that this is indeed the worst case pizza for Alice.) The full paper is well worth looking at if you’re interested: although it’s presented using the full formal apparatus of mathematical notation, theorems and proofs, it doesn’t require high-powered mathematical machinery — elementary logic and a clear head should be all you need to follow it!

In a very recent update, Keyue Gao introduces a variation called the Pizza Race problem. The set-up is the same except that now time becomes important. Alice and Bob eat the pizza at the same rate, and each may take the next piece only after he or she finishes eating the current piece. Thus, the time it takes to eat one piece of pizza is proportional to its size. (The time to make a decision and pick up a new piece of pizza is assumed to be negligible: I guess we all know people who eat like that.) The sizes of all slices are chosen so that Alice and Bob never finish eating a piece at exactly the same time.

Gao was able to show that with this time element, Alice can always eat at least 2/5 of the pizza, but not to determine whether this is the highest possible lower bound. The problem remains open… and by way of encouragement, you might like to know that Gao’s work was carried out as part of an undergraduate summer project, so this is the kind of area where you don’t need to be an experienced mathematical researcher to make a contribution!

For the enthusiast, by the way, Prof. Winkler has compiled some more fascinating and counter-intuitive problems in a couple of papers available on his website: look, for example, at “Games People Don’t Play” (available from his publication list) and at “Seven Puzzles You Think You Must Not Have Heard Correctly”. No peeking at the solutions!

(DP)

Advertisements
This entry was posted in Articles. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s