Play First and Lose: Zugzwang in Chess, Math and Pizzas

In most two-player games, it is generally better to win the toss and go first. And if you are sharing a pizza with someone and want to have a larger portion, it’s usually better to grab the first slice and pick a really large one. But there are situations in which it might be better to go second. In chess, these situations have a dramatic-sounding name: zugzwang! Our puzzles today explore this up-is-down phenomenon in four different contexts.

Let’s start with chess, which is possible to win whether you go first or second. In the most recent World Chess Championship, the Norwegian reigning champion Magnus Carlsen demolished the Russian grandmaster Ian Nepomniachtchi by a score of 7.5 to 3.5. Out of the 11 games played, Carlsen won four, twice as white and twice as black. The other seven games were drawn.

But though it is possible to win as black in chess, it is well known that getting to move first with the white pieces is advantageous — it’s a little like serving first in tennis. Statistically, based on a large number of games, the odds are about 54%-46% in favor of the player going first in chess. In most chess positions, you can improve your position by making a move. But there are times when the player who has to move can only worsen their position and will eventually lose. This is an example of zugzwang — a German word whose literal meaning is “move compulsion.” Here’s a simple example:

The position above is symmetrical and looks equal. But upon closer inspection, you can see that whoever goes next has to move their king away from the pawn that it is protecting. This allows the other side to capture the pawn and ultimately queen their own pawn and win the game.

Most zugzwang positions aren’t reciprocal like this one. Usually only one side is caught in this kind of bind.

Since the term “zugzwang” comes from chess, let’s start with a chess puzzle. Below is a position from a World Championship candidates match half a century ago that was won by another legendary champion, the American Bobby Fischer.

Puzzle 1: Chess

Question: In the position shown, it is black’s turn to move. Unfortunately, black is in zugzwang and will ultimately lose. Can you explain how?

It’s all very well to have a zugzwang situation when most of the pieces are off the board, but what about the initial position? Perhaps white is already in zugzwang at the beginning of the game with perfect play by black, or perhaps there’s a white move that invariably puts black in zugzwang. Or it may be that perfect play always results in a draw. Chess is too combinatorically complex a game to figure this out, even with the help of the most advanced supercomputers. However, there are some simple games in which one side starts off in zugzwang.

Puzzle 2: Nim

Consider the ancient game Nim. The general form consists of two players removing bunches of stones from any of several piles until all the stones are removed. In its many variations, Nim has generated several mathematical results in combinatorial game theory, including the Sprague-Grundy theorem.

In the simpler form of Nim called the subtraction game, there’s just one number to subtract from, instead of multiple piles of stones. There are two players, A and B. A gets to go first, but B gets to choose the number to start subtracting from. Let’s say B starts with 101. The players then take turns subtracting 1, 2 or 3 from the number that remains after the last player’s turn. The game ends when the value reaches zero. The player who is compelled to make the last subtraction loses.

It is easy to see in the above situation that A is already in zugzwang and destined to lose if B follows the best strategy. If A subtracts x, all B needs to do is to subtract the amount 4 − x. This takes the starting number (which is 1 plus a multiple of 4) down a zugzwang ladder from 101, 97, 93… to 9, 5, 1, forcing A to make the last subtraction. If we changed the rules so that the person who makes the last subtraction wins, B can choose an initial value of 100 and follow the same simple strategy.

For our second puzzle, I’ve added a rule to make it harder for B to find the right strategy. In this version of the subtraction game, the players must take away at least 1 as before, but the maximum amount you can subtract at any stage is 1 more than the tens digit of the current number. Thus, if the current number is between 90 and 99, you can subtract any number up to and including 10; if it’s 80 to 89, you can subtract 1 to 9, and so on. Finally, when the remaining number is between 1 and 9, you can only subtract 1 each turn. A goes first as before, and B gets to choose a starting number between 90 and 99. The player stuck with making the last subtraction loses.

Question: What starting number should B choose? Can you list the entire zugzwang ladder?

Puzzle 3: Sim

For our third puzzle, we turn from Nim to Sim, a game based on the rich area of combinatorics called Ramsey theory. Sim is a game between two players — let’s call them Red and Blue. The game is played on the figure shown, which consists of six points, each of which is joined to every other by black lines (called edges in graph theory). Each player in turn picks a single edge and colors it red or blue per their name. If a player’s move causes any three of the points to be joined by edges of the same color, the player loses. With six points, the number of lines is “6 choose 2” = $latex \frac{6 !}{2 ! 4 !}$, or 15, so the game lasts at most 15 moves. You can play an online version of Sim here.

From Ramsey theory we know that if you color edges between six points using two colors, there will always be a certain number of triangles bounded by edges of the same color. So the game of Sim will always have a winner. In fact, it has been proved that a winning strategy is always available to the second player, no matter what the first player does. In other words, the first player is in zugzwang at the very start of the game.

Question: Can you describe the shortest possible game of Sim that results in a position of reciprocal zugzwang (whichever player moves next loses)? List the moves made in the game in sequence.

Even though there is always a winning strategy for the second player, it is apparently too complicated to find or remember without the assistance of computers. So, for ambitious recreational mathematicians, the quest to find a practical winning strategy for the second player is still open.

Puzzle 4: Pizza

Finally, here is my favorite example of zugzwang, and our toughest puzzle today. The goal is to use zugzwang to get a larger share of a pizza.

Letting your friend pick the first slice, can you get a larger portion of the pizza? Believe it or not, the answer is yes, provided you cut the pizza in a specific way!

Your friend gets to go first, and you get to cut the pizza. You cut the pizza into wedge-shaped radial slices as usual. You can make any number of slices and they don’t all need to be the same size. Your friend goes first and picks any slice she wants. After that you each take a slice in turn, but you and your friend must choose one of the two slices that border the open part of the pizza. Both of you do your best to get as much of the pizza as possible.

Questions:

a. How do you cut the pizza such that after all the slices are taken, you have more of the pizza than your friend? Give the smallest possible number of slices in which this can happen, and the relative size of each slice.

b. What’s the largest fraction of the pizza that you can obtain?

c. Can you specify all the possible numbers of slices that will not work to achieve this result?

Let me give you some hints to help you get started. Consider the end of the game when there are just three slices left. Imagine that their relative sizes are 1, 3 and 1. The person going first is in zugzwang and has to pick one of the two slices of size 1. This exposes the slice of size 3, which you grab. Your friend gets the last slice, thus ending up with $latex \frac{2}{5}$ of this portion while you get $latex \frac{3}{5}$. You can make a long zugzwang ladder by merely extending this pattern. For five slices with the pattern 1, 3, 1, 3 and 1, your friend ends up in zugzwang twice, and you get a pizza portion of size 6, while she gets a portion of just size 3 despite going first.

So if the slices were all lined up in a row, it would be easy enough. But the catch, of course, is that the pizza is initially round and whole and your friend can select the first slice to maximize her take, right out of the middle of your zugzwang ladder. So how do you get it to work? That’s your task today.

Happy puzzling, and if things get tough, you can always order pizza for inspiration. Just remember to go first … until you manage to solve this puzzle.

Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a Quanta Magazine T-shirt or one of the two Quanta books, Alice and Bob Meet the Wall of Fire or The Prime Number Conspiracy (winner’s choice). And if you’d like to suggest a favorite puzzle for a future Insights column, submit it as a comment below, clearly marked “NEW PUZZLE SUGGESTION.” (It will not appear online, so solutions to the puzzle above should be submitted separately.)