The Pizza Race Problem
January 9, 2013
One way to get children interested in mathematics is to offer them a treat, such as a pie or cake, and have them divide it into fair portions by themselves. If there are just two children, the task can be reduced from a mathematical to a political task. One child cuts, and the other child chooses which half he or she prefers. When there are three children involved, an impromptu lesson in trigonometry emerges in which 120 angular degrees and the definition of the center are the objects of concern.
What happens when an object has already been cut into irregular portions, and the diners need to successively take portions? How much of a quantity advantage could one diner have over the others in this sort of game? Also, what happens when a portion of the object has been previously removed; for example, one slice taken from a pizza.
Sharing an irregularly cut pizza is the question posed in the Pizza Race Problem, an analysis of which was posted by Keyue Gao on arXiv. Gao participated in the New York University Summer Undergraduate Research Experience(SURE) Program.
Gao's problem is a variation of a problem first posed by mathematician, Peter M. Winkler, at a 2008 conference in Budapest in honor of Laszlo Lovasz's sixtieth birthday. In the original problem posed by Winkler, Bob and Alice share a pizza, possibly at a cryptography conference. The pizza is irregularly sliced by any number of cuts from the center to the edge. Bob and Alice, being proper mathematicians, have decided to eat this pizza according to the following algorithm:
(1) They choose pieces in an alternating fashion;
On each turn, except the first and the last, the diner has a choice of two available pieces. Alice, in selecting first, would take the largest slice, and she would seem to always have an advantage. This is true for an even number of pieces. In that case, Alice, if she chooses wisely, will always get more than half the pizza.
What's interesting is that Alice can actually come away with less than half in the odd piece case. Although Alice gets both the first and last piece in an odd piece pizza, Winkler conjectured she might at a minimum get only 4/9 of the pizza. This conjecture was proven by Kolja Knauer, Piotr Micek and Torsten Ueckerdt.
Geometrically, the problem reduces to the selection from a ring of random numbers adding to 360 degrees. Of course, it doesn't really matter what the numbers add up to, since the sum can be scaled to 2π, or whatever you want. This makes a computer simulation very easy, since in each case you can just spit out a bunch of random numbers and not worry about their sum.
As is my custom, I've written a simple computer simulation for this pizza problem (source code, here). It generates random pizzas, allows Bob and Alice to make random selections, and it keeps track of the largest portion for Alice. As it turns out, Alice will, on average, do very well in sharing an odd piece pizza, even when she chooses her pieces at random.
Part of this might be because Alice always selects the largest piece as her first piece; and, for some random pies, this piece can be quite a bit larger than others. The following histogram shows the results of 10,000 trials for an eleven piece pizza in which Alice chooses the largest piece first, and then randomly thereafter.
(2) Alice starts the meal by selecting any piece of the pizza;
(3) After Alice's first selection, and all subsequent selections, it's only proper to choose one of the pieces adjacent to the empty space.
As can be seen in the histogram, random selection does not always give Alice at least four-ninths (0.444...) of the pizza, but it comes quite close. Just a few percent of the random trials fall below four-ninths (347 out of 10,000, or 3.47%, in one particular simulation run).
Gao adds another constraint to the problem by requiring Bob or Alice to finish eating their current piece before taking another. In this case, Alice starts first, as before, but the taking of subsequent pieces depends on the size of the pieces currently being eaten. Bob and Alice eat at the same rate. One other constraint is that the sizes of the pieces are such that Alice and Bob will never grab for the same piece at the same time.
This type of sharing would be good for Alice if she's on a diet, since Gao demonstrates that she is only guaranteed two-fifths of the pie. This is just a small variation of the result of the original problem (0.400 vs 0.444...).
|The fraction of pizza that Alice can consume from an eleven piece pizza if she selects the first slice and follows a mathematician's dining etiquette.|
(Graph rendered using Gnumeric.)
- Keyue Gao, "Pizza Race Problem," arXiv Preprint Server, December 10, 2012
- Kolja Knauer, Piotr Micek and Torsten Ueckerdt, "How to eat 4/9 of a pizza," arXiv Preprint Server, January 24, 2011.
Permanent Link to this article
Linked Keywords: Children; mathematics; pie; cake; politics; political; trigonometry; angular degree; center; pizza; family; knife; fork; Wikimedia Commons; arXiv; New York University; mathematician; Peter M. Winkler; Laszlo Lovasz; birthday; Bob and Alice; cryptography; algorithm; geometry; geometrical; circular buffer; ring; random number; computer simulation; source code; pizza.c; randomness; random; histogram; etiquette; Gnumeric; constraint; Keyue Gao; Pizza Race Problem.
Latest Books by Dev Gualtieri
Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!
Blog Article Directory on a Single Page
- Soybean Graphene - March 23, 2017
- Income Inequality and Geometrical Frustration - March 20, 2017
- Wireless Power - March 16, 2017
- Trilobite Sex - March 13, 2017
- Freezing, Outside-In - March 9, 2017
- Ammonia Synthesis - March 6, 2017
- High Altitude Radiation - March 2, 2017
- C.N. Yang - February 27, 2017
- VOC Detection with Nanocrystals - February 23, 2017
- Molecular Fountains - February 20, 2017
- Jet Lag - February 16, 2017
- Highly Flexible Conductors - February 13, 2017
- Graphene Friction - February 9, 2017
- Dynamic Range - February 6, 2017
- Robert Boyle's To-Do List for Science - February 2, 2017
- Nanowire Ink - January 30, 2017
- Random Triangles - January 26, 2017
- Torricelli's law - January 23, 2017
- Magnetic Memory - January 19, 2017
- Graphene Putty - January 16, 2017
- Seahorse Genome - January 12, 2017
- Infinite c - January 9, 2017
- 150 Years of Transatlantic Telegraphy - January 5, 2017
- Cold Work on the Nanoscale - January 2, 2017
- Holidays 2016 - December 22, 2016
- Ballistics - December 19, 2016
- Salted Frogs - December 15, 2016
- Negative Thermal Expansion - December 12, 2016
- Verbal Cues and Stereotypes - December 8, 2016
- Capacitance Sensing - December 5, 2016
- Gallium Nitride Tribology - December 1, 2016
- Lunar Origin - November 27, 2016
- Pumpkin Propagation - November 24, 2016
- Math Anxiety - November 21, 2016
- Borophene - November 17, 2016
- Forced Innovation - November 14, 2016
- Combating Glare - November 10, 2016
- Solar Tilt and Planet Nine - November 7, 2016
- The Proton Size Problem - November 3, 2016
- Coffee Acoustics and Espresso Foam - October 31, 2016
- SnIP - An Inorganic Double Helix - October 27, 2016
- Seymour Papert (1928-2016) - October 24, 2016
- Mapping the Milky Way - October 20, 2016
- Electromagnetic Shielding - October 17, 2016
- The Lunacy of the Cows - October 13, 2016
- Random Coprimes and Pi - October 10, 2016
- James Cronin (1931-2016) - October 6, 2016
- The Ubiquitous Helix - October 3, 2016
- The Five-Second Rule - September 29, 2016
- Resistor Networks - September 26, 2016
- Brown Dwarfs - September 22, 2016
- Intrusion Rheology - September 19, 2016
- Falsifiability - September 15, 2016
- Fifth Force - September 12, 2016
- Renal Crystal Growth - September 8, 2016
- The Normality of Pi - September 5, 2016
- Metering Electrical Power - September 1, 2016
Deep Archive 2006-2008