CMSC 203, Section 0201
Discrete Structures
Spring 2009
Homework 1, Questions 4, 5 & 6
Due: Tuesday February 3, 2009
Of Pizza, Pirates and Preferences. You’ve been captured by pirates and, while stumbling
along the beach digging for buried treasure, the pirates chance upon a whole pizza with all the
toppings. The pirates are really sick of their diet of salt pork and stale bread and are eager to
divvy up the pizza for lunch. However, pirates are petty, greedy, suspicious, insanely jealous,
prone to violence and generally badly behaved (that’s how they wound up as pirates). Thus, they
immediately begin squabbling over how to share the pizza. If swords are drawn, you might get
hurt. How can you help divide the pizza fairly?
One complication in this problem is that the pirates do not have the same preferences for pizza
toppings. One pirate might like pepperoni while another one anchovies. Being mutually suspicious,
they don’t want to reveal their own preferences and would not believe each other anyway.
In the case of two pirates, a simple cut-and-choose procedure provides the solution. One pirate
cuts the pizza into two pieces that he thinks are equal according to his own preferences. The other
pirate then chooses one of the pieces. The first pirate gets a piece that he thinks is half the pizza.
The second pirate gets to choose first, so he can pick the piece that he thinks is bigger. So, both
pirates are happy. Note that the procedure does not require either pirate to reveal their preferences.
Too bad you’ve been captured by 3 pirates: Alan, Bob and Charles. (These are the pirates’
real names. They have much more fearsome nicknames among pirates.) Reaching into your dim
memories of a Discrete Math class, you suggest that the pirates follow this procedure:
FairShare Procedure
1. Alan divides the pizza into three pieces that he thinks are equal (according to his own pref-
erences).
2. Bob takes the largest piece (by his own preferences) of the three and trims the piece to make
it equal to the second largest piece. The