Fine Dining with a Pizza Puzzle
Peter Winkler gave a talk at MIT last fall and, as is customary, the audience was invited to join him for dinner afterwards at a local restaurant. I was eager to dine with Peter because he is a puzzle collector and I was hoping to hear a new puzzle. I got what I was hoping for — tripled. We got a pizza puzzle, a cake puzzle and a tart puzzle to complement our dinner. Today I will discuss the pizza puzzle.
Peter is now a columnist at ACM communications. His column is called “Puzzled” and it is featured as part of the section titled “Last Byte.” Writing these paragraphs has made me so hungry that I need to go grab something to bite.
Okay, I am back and here is the pizza puzzle.
Alice and Bob ordered a pizza. The pizza is cut into several radial pieces. Both Alice and Bob are greedy and well-mannered at the same time. They each want to get as much pizza as possible for themselves, but they don’t want to be obvious about it. They take pieces in turn, starting with Alice. Because they are well-mannered and not obvious, when it is their turn, they only take a piece that is adjacent to the pieces already taken. Throughout the process of consuming this pizza, the untaken pieces are contiguous.
The question is: Is it possible to cut the pizza in such a way that although Alice starts, Bob can guarantee himself more than half?
If you want to think about this puzzle on your own, now would be a good time to pause. Why? Because in the next paragraph, I will give you some hints about how to approach this question.
If the number of pieces is even, then Alice can’t lose. She can number the pieces around the circle consecutively, decide whether all the odd pieces or all the even pieces make up a bigger chunk, and then follow the parity.
But what happens if there are an odd number of pieces? Alice has an advantage, for she will get more pieces. But is that enough to guarantee that she will get at least half? Suppose she starts by taking a minuscule piece. Then Bob can number all of the leftover pieces in order and decide if he prefers the even-numbered group or the odd-numbered group. He is in control now, so he can guarantee himself the bigger part of the leftover pieces.
However, that might not be good enough for Bob to win. For example, if there is a very big piece, one that is bigger than half of the pizza, then in the first move Alice wins.
On the other hand, would Alice necessarily win by starting with the biggest piece?
Suppose the biggest piece is significantly less than half. Would Bob have a chance? To his advantage, he does have a lot of control. He can choose the parity of the pieces he wants at the beginning, and he can also switch this parity later, depending on what Alice does. Does he control the situation enough that it would be possible to cut the pizza in his favor?
I have to add that if you can find a solution with N pieces, then you can easily build a solution with N+2 pieces. Suppose you start with a pizza cut into N pieces, such that Bob will win. If you add two adjacent pieces of zero value to this pizza, you will get a pizza cut into N+2 pieces, such that Bob can still win. Indeed, Bob will follow the strategy he used with the N-pieces pizza, except that each time Alice takes one of the new pieces, Bob takes the other.
Can you find a way to cut a pizza so that Bob can guarantee himself more than half?
Share:
Austin:
Nice puzzle!
I would suggest the term “pinwheel” for a set consisting of every other slice (from what is left). For example, if eight slices are left, then slices 1,3,5,7 form a pinwheel, as do slices 2,4,6,8. As you observed, whichever player gets to choose from among an even number of slices can guarantee him- or herself either pinwheel.
Unfortunately for Bob, I can show that in a pizza with 2n+1 slices, there is always a slice Alice can remove such that neither pinwheel in the remaining 2n slices consists of more than half the (original) pizza. So, if Bob has a strategy, it must be more complicated than choosing a pinwheel.
19 September 2009, 5:14 pmJDS SEO Manchester:
Wow what a great pizzle.. Is is possible for Bob to have more, I have been jotting down notes to an hour and can’t find a ‘polite’ way…
8 December 2009, 9:14 amPratik Poddar:
For the even case, yes its simple. Alice would “force” Bob to take either the even set or the odd set whichever is less and so have more than half pizza.
For the odd case, is there a solution? Proof in either direction? Thanx
Pratik (https://pratikpoddarcse.blogspot.com)
13 January 2010, 2:42 am