Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
11  
I'm not quite convinced that your strategy gets you the most pieces of pepperoni. I just see that it gets you more than your enemy. After you chose the label with the maximum sum, either $1$ or $2$, your strategy says to continue choosing slices with the same label. How do you know that it's never advantageous to switch labels while picking? – Mike Pierce Jan 27 at 15:57
8  
@HowDoIMath, okay. I just thought of a specific example where your strategy doesn't get the maximum, so I'll post it for reference: Think of the game where there are four slices of pizza and in circular order each slice has $\{2,4,2,1\}$ pepperonis. Assuming you want to pick up your largest slice first, your strategy says you pick $4$, he picks $2$, you pick $1$, he picks $2$, whereas you clearly do better if you pick $2$ your second time. Choosing the $1$ slice first doesn't do any better. – Mike Pierce Jan 27 at 16:06
4  
To make the game and problem more concrete, assume there are an odd number of pepperoni's so that there must be a winner to the game. (If not, your solution to the "even slices" case only guarantees at least a tie.) Also assume no slice has a negative number of pepperoni's -- if there can be negatives, then the first player no longer always has a win (consider the pie with $\{1,1,-101,1,1\}$ pepperoni's on five slices). And, as is usual in 2-player combinatoric games, say we only care about who wins, not by how much. – Mark Fischler Jan 27 at 16:34
33  
This is why mathematicians don't get invited to parties, just so you know. – pjs36 Jan 27 at 18:36
4  
@MikePierce: I think {2,3,2,0} is a somewhat more interesting example — the optimal strategy is to start with the slice with 3 pepperonis, even though HowDoIMath's strategy suggests choosing the 2 and the other 2 (and not taking the 3 at all). – Scott Jan 28 at 1:42
up vote 50 down vote accepted

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.

share|cite|improve this answer
17  
I am now hesitant to split a pizza with you. – Mark S. Jan 28 at 4:13
25  
@MarkS. but I'll even let you take the first slice! – Gregory J. Puleo Jan 28 at 4:56

This problem reminds me of the first problem, "Coins in a Row", in Peter Winkler's Mathematical Puzzles: A Connoisseur's Collection.

There are quite a number of discussions of this problem online, for example here's a blog post that looks to maximize a linear version of this problem.

Curiously, with the linear version of the problem (where players can either pick the first or last "slice" in the line), an even number of "slices" guarantees that the first player can have more "pepperoni", but an odd number of "slices" often gives the second player an advantage.

share|cite|improve this answer

I propose the solution is alpha-beta search. Your adjacent rule means we have n * 2(n - 2) possible searches which is well within range.

share|cite|improve this answer
    
I think there are only n^2 - n + 2 nodes to search. – Florian F Jan 29 at 9:42
    
That would be the correct count if his adjacent rule did not exist (that allows only 2 choices for any move after the first). – Joshua Jan 29 at 16:12
    
Did you mean n times a power of 2? That means you are considering the same position multiple times. What I count is the number of possible states with the adjacency rule, not the number of paths. – Florian F Jan 30 at 0:15
    
Oh how silly of me. – Joshua Jan 30 at 2:10

With an odd number of slices, whomever goes first reduces the following player's problem to the even-numbered solution, that is to say, they can alternately colour the pizza slices black and white, sum the values, and chose the set with the most value.

Therefore the problem is reduced to this: which slice can you take that gives you enough value to overcome the difference between the two remaining sets? If there exists such a slice, you want to play first and take that slice and your victory is guaranteed. If not, then no matter what the first player does, they will lose to a sufficiently savvy opponent.

share|cite|improve this answer
    
Either I'm not convinced that this is correct, or I don't understand what you mean. I agree that if you can find a slice, such that its # of pepperonis make up for the difference between the two groups, and such that this slice is positioned between two slices that you want your opponent to have, then you win. But I don't think that if such a slice does not exist, then you will lose, as there may be a strategy other than the "odd-even" one that gives you more pepperonis than your opponent. – Mankind Feb 1 at 13:25
1  
Yeah, on reflection, this is not the only strategy nor a complete/optimal one. I guess I was misled by the question suggesting that the parity solution was complete/optimal, which I'm not sure it is and therefore a solution build on top of that is equally unsound. – Danikov Feb 1 at 14:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.