Sharing a pepperoni pizza with your worst enemy

You are about to eat a pepperoni pizza, which is sliced into eight pieces. Each pepperoni will unambiguously belong to some slice (no pepperoni is “between” slices).

The caveat is that you have to share the pizza with your worst enemy, and you want to secure more pieces of pepperoni than he does. Slices are chosen as follows: First you choose any slice. Then your enemy chooses a slice adjacent to the slice that you just chose. Next, you choose a slice adjacent to one of the two chosen slices, and so on.

How do you make sure you get at least as much pepperoni as your opponent? In this case, a solution is as follows: Number the slices 1,2,1,2,1,2,1,2, such that any two consecutive slices have different labels. Add the number of pepperonis on all slices with the label 1, and add the number of pepperonis on all slices with the label 2. If e.g. the number of pepperonis on the slices numbered 1 is largest, you choose some slice with the number 1. Your enemy can then only choose a slice with the number 2, to which you respond by choosing the next adjacent slice with the number 1, and so forth.

This works, whenever there is an even number of slices.

My question is, is there a winning strategy, when the number of slices is odd?

Answer

Believe it or not, this problem has been studied before (in the superficially different formulation of a pizza sliced into radial slices of unequal size). It turns out that the first player can only guarantee getting 4/9 of the pizza: there are slicings of the pizza under which the second player can get 5/9 of the pizza. See, for example, this arxiv preprint. If you have access to MathSciNet, this review of the same paper might also be a decent index into the history of the problem.

Attribution
Source : Link , Question Author : Mankind , Answer Author : Gregory J. Puleo

Leave a Comment