Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Fete of Combinatorics and Computer ScienceSolution of Peter Winkler’s Pizza Problem*†

Fete of Combinatorics and Computer Science: Solution of Peter Winkler’s Pizza Problem*† [Bob cuts a pizza into slices of not necessarily equal size and shares it with Alice by alternately taking turns. One slice is taken in each turn. The first turn is Alice’s. She may choose any of the slices. In all other turns only those slices can be chosen that have a neighbor slice already eaten. We prove a conjecture of Peter Winkler by showing that Alice has a strategy for obtaining 4/9 of the pizza. This is best possible, that is, there is a cutting and a strategy for Bob to get 5/9 of the pizza. We also give a characterization of Alice’s best possible gain depending on the number of slices. For a given cutting of the pizza, we describe a linear time algorithm that computes Alice’s strategy gaining at least 4/9 of the pizza and another algorithm that computes the optimal strategy for both players in any possible position of the game in quadratic time. We distinguish two types of turns, shifts and jumps. We prove that Alice can gain 4/9, 7/16 and 1/3 of the pizza if she is allowed to make at most two jumps, at most one jump and no jump, respectively, and the three constants are the best possible.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Fete of Combinatorics and Computer ScienceSolution of Peter Winkler’s Pizza Problem*†

Part of the Bolyai Society Mathematical Studies Book Series (volume 20)
Editors: Katona, Gyula O. H.; Schrijver, Alexander; Szőnyi, Tamás; Sági, Gábor
Cibulka, Josef; Stolař, Rudolf; Kynčl, Jan; Mészáros, Viola; Valtr, Pavel; Mészáros, Viola
Fete of Combinatorics and Computer Science — Jan 31, 2011
Download PDF
30 pages

Loading next page...
 
/lp/springer-journals/fete-of-combinatorics-and-computer-science-solution-of-peter-winkler-s-7FJTJqowwP
Publisher
Springer Berlin Heidelberg
Copyright
© János Bolyai Mathematical Society and Springer-Verlag 2010
ISBN
978-3-642-13579-8
Pages
63 –93
DOI
10.1007/978-3-642-13580-4_4
Publisher site
See Chapter on Publisher Site

Abstract

[Bob cuts a pizza into slices of not necessarily equal size and shares it with Alice by alternately taking turns. One slice is taken in each turn. The first turn is Alice’s. She may choose any of the slices. In all other turns only those slices can be chosen that have a neighbor slice already eaten. We prove a conjecture of Peter Winkler by showing that Alice has a strategy for obtaining 4/9 of the pizza. This is best possible, that is, there is a cutting and a strategy for Bob to get 5/9 of the pizza. We also give a characterization of Alice’s best possible gain depending on the number of slices. For a given cutting of the pizza, we describe a linear time algorithm that computes Alice’s strategy gaining at least 4/9 of the pizza and another algorithm that computes the optimal strategy for both players in any possible position of the game in quadratic time. We distinguish two types of turns, shifts and jumps. We prove that Alice can gain 4/9, 7/16 and 1/3 of the pizza if she is allowed to make at most two jumps, at most one jump and no jump, respectively, and the three constants are the best possible.]

Published: Jan 31, 2011

Keywords: Optimal Strategy; Minimum Size; Characteristic Cycle; Circular Sequence; Optimal Turn

There are no references for this article.