0

## The Secrets of Nim (Pizza Nim)

Published on Sunday, March 04, 2012 in , , ,

One of the great things about Nim is that you can adapt it to so many objects. For example, it would be easy to take standard Nim and play it with a pizza, so you could make sure that you, or the other person, always take the last slice.

If you're going to scam somebody with a fun food like pizza, though, shouldn't you be scamming them so as to get the majority of the pizza, or assure you at least get half? Thanks to a mathematician by the name of Peter Winkler, we know the answer.

If you and another person can take them in any order, then it's pretty easy to see that the pieces will most likely be taken in order of how big they are. If they're cut into equal slices, then even this doesn't matter.

To make it more of a challenge, we need rules. Here are the rules, based on Peter Winkler's investigation.

1) There are two players, whom we'll call A and B.
2) Player A names how many slices the pizza will be cut into.
3) Player B must cut the pizza by making all cuts from the center of the pizza to its crust, but is not required to make the pieces of equal size.
4) Player A gets to choose the first slice.
5) From that point, players alternate taking turns removing slices. Player B always follows Player A, and vice versa.

Here's the interesting spin on taking pieces, however:

6) After the first slice is taken, players are only allowed to take slices on their turn that are adjacent to the slices that have already been taken.

In other words, after the first piece is taken by Player A, there are only two slices from which either player can choose.

So, if you're Player A, the number of slices really only determines how many turns will be taken. The real question is whether it's to your advantage to state an even or odd number of slices.

Most people would think that they should state an odd number of slices. That way, they'd get to choose the first and last slices, thus winding up with 1 more slice than the other player, giving them the edge.

As it turns out, this is exactly wrong. Remember, it's not the number of slices that's your goal, but the greater share of the pizza, or assuring yourself at least half of the pizza. Player A should always choose an even number of slices.

To learn why, imagine that you, as Player A, request that the pizza be cut into 6 slices, and player B cuts the pizza in this manner:

Before taking your first piece, think of alternating pieces, regardless of size, as being in two groups. In the picture below, I've alternated the slices with red and green tints, to break them into separate groups.
At this point, ask yourself, which group, if any, contains a larger share of the pizza? Just by eyeballing the picture above, it's not too hard to see that it's the green group. But is there any way to make sure that you can obtain all the slices in the green group?

To help illustrate how this is done, I'll add the exact percentages, so we have a way to refer to each slice. Note that the green group percentages are 35%, 11%, and 8%, so we're going to insure ourselves 54% of the pizza:
Probably nobody will be surprised if you were to take that big 35% slice first, so that's your first move. Remember that only slices adjacent to the ones previously removed can be chosen. By removing the 35% slice, you're leaving them a choice between the 7% slice and the 29% slice, both of which are red. In short, they can't take a green slice!

Most likely, they'll take the 29% slice, leaving your next choice between the 7% slice (red) and the 11% slice (green). Since you've already determined that the green group contains the greater share of the pizza, you'll take the green 11% slice.

Notice what happens at this point. Once again, you've limited their choice to two slices, both from the red group (10% and 7%). They choose either one of those, and either way, they open up the final green 8% slice for you to take!

No matter how it proceeds, you can always make sure that they only get choices from the red group, while you can always make sure there's 1 green slice for you to take! Even if you were to start by choosing the smallest green 8% slice, by using this approach, you can still insure yourself the larger share of the pizza!

Since you examine the pizza ahead of time to see which group contains more slices, you can always guarantee yourself at least half of the pizza, if not more.

If you simply want to understand the approach and pull this on a friend the next time you have pizza, you have everything you need to know. However, if you want to delve deeper into the heavy mathematics of it, check out How to eat 4/9 of a pizza and Solution of Peter Winkler's Pizza Problem. One of the authors on those papers has also prepared this PDF presentation of the puzzle, which you may find helpful.

If you practice this and use it, enjoy your sweet, tasty victory!