Most games that pit two players or teams against each other require one of them to make the first play. This results in a built-in asymmetry, and the question arises: Should you go first or second?
Most people instinctively want to go first, and this intuition is usually borne out. In common two-player games, such as chess or tennis, it is a real, if modest, advantage to win the toss and go first. But sometimes its to your advantage to let your opponent make the first play.
In our February Insights puzzle, we presented four disparate situations in which, counterintuitively, the obligation to move is a serious and often decisive disadvantage. In chess, this is known as zugzwang a German word meaning move compulsion. Lets see how the strange magic of zugzwang is realized in each of our four scenarios.
The position on the chessboard below was reached in the second game of the World Championship Candidates match in 1971 between the American grandmaster Bobby Fischer playing white, and the Soviet grandmaster Mark Taimanov playing black. It is blacks turn to move, but unfortunately black is in zugzwang, and will lose. Our task was to explain how.
If we compare the minor pieces, white has a bishop and black has a knight. Neither of these pieces is enough to force victory. But white also has a pawn that can advance to the top of the board and become a queen. If that happens, white easily wins. So blacks task is clear: Taimanov has to capture the white pawn, even if it means sacrificing his knight to do so. That will lead to a draw, which is the best black can do here.
At first, it might seem like blacks knight is in a good position to capture whites pawn. The knight is protected by blacks king and controls the h7 square, which the white pawn must pass through before it can be promoted.
Alas, now the move compulsion of zugzwang rears its ugly head. For while Taimanov would have been content to keep his knight on g5, he is in the unfortunate position of having to move either his king or the knight. If he moves his king, it can no longer protect the knight, and the knight perishes, leaving the pawn free to advance. If, on the other hand, he moves the knight to the only safe square, f3, and white then pushes his pawn to h6, its true black can move the knight back to g5 on the subsequent move. This prevents Fischer from immediately advancing his pawn to h7. But now white can pull out the secret weapon of zugzwang in chess: He can make a waiting move, sliding his king over to g6. Again, black must move, and now Taimanov has truly run out of viable options.
If black moves his king, his knight falls. If he moves his knight to f3, whites pawn advances to h7 and its game over. (If he moves his knight anywhere else, whites bishop or king will capture it and its also game over.) This is the power of zugzwang in a nutshell.
Needless to say, Fischer won the game. He then trapped Taimanov in an even more complicated zugzwang in game 4 and ultimately swept the matches 6-0. Fischer went on to crush two other leading grandmasters before beating the Soviet grandmaster Boris Spassky in 1972 to become world champion, in what was dubbed the match of the century.
Several readers described solutions to this problem.
In this variation of the ancient game Nim, two players, A and B, play a subtraction game in which B gets to pick a starting number, from which each player in turn subtracts a small number until they hit zero. During each turn, a player must subtract at least 1, up to a maximum of 1 more than the tens digit of the current number. Thus, if the current number is between 90 and 99, they can subtract any number up to and including 10; if its 80 to 89, they can subtract 1 to 9, and so on. Finally, when the remaining number is between 1 and 9, they can only subtract 1 each turn. A goes first, and B gets to choose a starting number between 90 and 99. The player stuck making the last subtraction loses.
Question: What starting number should B choose? Can you list the entire zugzwang ladder?
This puzzle was solved by readers Seth Cohen and sunil nandella. I can do no better than to quote Seth Cohens excellent explanation:
For Puzzle 2, start at the bottom. If A is on 1, A loses. Likewise, since in the single digits they can only subtract 1, A loses on 3, 5, 7, and 9 (adding 2 each time). But A doesnt lose on 11, because at 11, A can subtract 2 and give the losing 9 to B. A does lose on 12, however. A loses on 15 and 18 as well (adding 3 each time). Now, as we jump into the 20s, we cant add 3 anymore, because at 21, A can subtract 3 and give the losing 18 to B. We must add 4: 22, 26. As we jump into the 30s, we have to add 5: 31, 36. To the 40s, add 6: 42, 48. And on and on: every time we move into a higher decade, we have to add 1 more to continue to the zugzwang ladder. The whole zugzwang ladder, from top to bottom: 93, 82, 72, 63, 55, 48, 42, 36, 31, 26, 22, 18, 15, 12, 9, 7, 5, 3, 1.
Sim is a game between two players lets call them Red and Blue. The game is played on the figure shown, which consists of six points, each of which is shown joined to every other by black lines (called edges ingraph theory). Each player in turn colors a single edge red or blue per their name. If a players move causes any three of the points to be joined by edges of the same color, the player loses.
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.
Here is a Sim position in which the reciprocal zugzwang position is reached in nine moves.
A move order that could generate this position is AB, BE, AC, CE, AD, DE, AF, FE, AE. That leaves six remaining uncolored edges: BC, BD, BF, CD, CF and DF. Coloring any of them either red or blue forces a triangle to have all edges of the same color, as shown in the following table.
Therefore, whichever player has to move next (in this case, the blue player) will be in zugzwang, and will lose. To understand how we reached this position, consider the quadrilateral formed by the four points ABCE. It has two contiguous red edges, AB and AC, and two contiguous blue edges, BE and CE. So whatever color the edge BC (the diagonal of the quadrilateral) is colored, it will complete a triangle of the same color. You can think of such a set of four points with a missing edge as a single zugzwang unit. There are six such units in this position, each dooming one of the six uncolored edges.
Blue reached this situation early in the game because of imperfect play. As I mentioned in the puzzle column, a winning strategy is always available to the second player in Sim, no matter what the first player does. The strategy is to avoid creating zugzwang quadrilaterals except two that leave a common edge uncolored. There are exactly 6 choose 2 (or 15) edges in the diagram, so the 15th (last) move will always fall to the first player. Ramsey theory tells us that with six points there will be a minimum of two triangles with edges of all the same color. With perfect play, the second player should be able to put off the creation of unicolored triangles until the last move. This will trap the first player into forming two unicolored triangles with the last edge.
Reader sunil nandella described and drew the position of such a perfectly played game in which the reciprocal zugzwang situation takes place on move 15, causing the first player to lose by unavoidably producing the two requisite unicolored triangles. The two zugzwang quadrilaterals in nandellas solution are BCEF and ABDE, which both have BE as the last uncolored edge.
Two players, A and B, share a pizza. A gets to choose the first slice, and B gets to cut the pizza. B must cut the pizza into wedge-shaped radial slices, making any number of slices which dont all need to be the same size. A can pick any first slice. After that B and A each take a slice in turn, always choosing one of the two slices that border the open part of the pizza. Both A and B do their best to get as much of the pizza as possible.
Questions:
Before I describe the solutions, lets go over some heuristic ideas that can lead us to the answers. As Jack Latta pointed out, B can never get a larger portion of the pizza if there are an even number of slices. To understand why, lets assume the pizza has eight slices, numbered 1 through 8. Now the pizza can be conceptually divided into two portions: the odd-numbered slices O (slices 1, 3, 5, 7) and the even-numbered slices E (slices 2, 4, 6, 8). Player A can ensure that he gets either E or O, whichever one is larger. If O is the larger portion, A can start with slice 1, leaving B to pick slice 2 or 8; A can then continue to pick the odd-numbered slice that is exposed (either 3 or 7 next turn) no matter which slice B picks. This always leaves B with even-numbered options. Conversely, if E is larger, A can win by getting all of the even-numbered slices. If both portions are exactly the same, A can pick odd or even, still denying B a larger part of the pizza. So the pizza we seek must have an odd number of slices.
Again, the concept of zugzwang ladders (which Ill refer to as z-ladders) comes into play. As I described in the puzzle, if you have a linear row of an odd number of slices with alternating sizes 1 and 3, the player going first must open the ladder, ceding all the larger pieces to the second player, who will therefore win.
The difficulty is that, with a round pizza, A can pick a large piece first. What happens to the z-ladder then? Lets consider what happens when a pizza consists of a single seven-slice z-ladder 1, 3, 1, 3, 1, 3, 1 as shown in the figure below, which has slice numbers in gray and sizes in brown.
Its useful to distinguish between slice 4, which we will call the middle slice, and slices 2 and 6, which are side slices. If A takes the large middle slice 4, then we are left with two joined z-ladders of slice sizes 1, 3, 1 (slice numbers 1-3 and 5-7). B is obliged to open one of them (she gets to decide which) by taking slice 3 or 5, ceding another large piece to A. After the opened ladder is exhausted, it is As turn and he is obliged to open the last ladder, ceding the last large piece to B. So in this scenario, A gets two large slices, and B gets one. If, on the other hand, A goes for one of the large side slices (slice 2 or 6), then we are left with a five-slice z-ladder and a single small piece, which B can take, forcing A to open the five-slice ladder and give two large slices to B. In the case of a five-slice z-ladder pizza, both large slices are side slices, and A and B each get one large piece.
We dont have a solution yet, but we have gleaned several insights that will lead us there. These are:
Insight 1: The pizza must have an odd number of pieces.
Insight 2: One z-ladder wont work. Based on insight 1, and the fact that z-ladders have an odd number of slices, we would need at least three z-ladders strung together.
Insight 3: You can look at the big slices only. B must get more of them.
Insight 4: While A has the advantage of taking the first large slice in a z-ladder, he needs to take the middle large slice, or his advantage is lost. If there is no middle large slice (as in a five- or nine-slice z-ladder with two and four large slices, respectively), the large slices are shared.
Insight 5: When there are two z-ladders left, the one who goes next has the advantage of deciding which ladder to open, forcing the other player to open the last one. In a pizza with an odd number of pieces, the player who has this key choice will always be B. This insight is golden!
Reader witzar came up with a brilliant 21-slice solution consisting of three z-ladders of lengths 5, 7 and 9 slices that illustrate these insights nicely. The pizza has nine large slices, and the ladders have two, three and four large slices, respectively. In the figure below, the three z-ladders are shown bounded by different colors.
In what follows, note that because A takes the first slice and the players alternate thereafter, A always goes on odd-numbered turns and B on even-numbered ones.
If A takes his first large slice from the five-slice z-ladder, the two players split the two large slices and then B can open the seven-slice ladder on turn 6, giving A three large slices, while B gets the four large slices of the final nine-slice ladder, which A is forced to open on turn 13. B wins with five large slices against As four.
If As first slice is the large middle slice of the seven-slice ladder, A gets two of that ladders three large slices. B then opens the five-slice ladder on turn 8, ceding its two large slices to A while again grabbing all of the nine-slice ladders large slices as before, A is forced to open this ladder on turn 13. B wins again with five large slices to As four.
If As first slice is one of the large central slices of the nine-slice ladder, A and B will share the four large slices of this ladder equally, each getting two. This happens because on turn 5, A is obliged to open the 5-slice piece thats left of this ladder to B. Then, as before, B opens the smaller five-slice ladder after the first ladder is done, this time on turn 10. She then gets all of the large slices in the last seven-slice ladder, which A is forced to open on turn 15. Once again, B gets five large slices to As four.
Note that if A goes for a small slice on his first turn, he merely gives B large slices of the first z-ladder right away, without changing the strategic advantage that B has when there are two z-ladders left. As results end up being as bad as, or worse than, the above cases. The same thing happens if A doesnt continue all the way to the end of a ladder but jumps to an unopened one. In short, A is in zugzwang from the beginning and has no way to win.
Its clear that 5/9 is the largest fraction of such a pizza that B can obtain if only the large slices matter. This assumes that the small slices are really tiny, the large slices are very much more than three times the small ones, and A plays optimally. Thus five-ninths is the answer to our second question.
It turns out that the smallest number of slices allowing B to win is 15, which is the answer to our first question. This pizza consists of three zugzwang ladders of five slices each, with two types of large slices: large (l) and extra-large (L). A general template for slice sizes in this pizza is: s, l, s, l, s, s, L, s, L, s, s, l, s, L, s, where s stands for the small slices (shown in the figure with the three five-slice z-ladders marked). Possible sizes of the 15 slices for an actual such pizza could be: 1, 3, 1, 3, 1, 1, 6, 1, 6, 1, 1, 3, 1, 6, 1. You can play with such a pizza and verify that B gets the larger portion no matter which slice A picks first by ensuring that she will obtain the large or extra-large slices of the weightier of the other two z-ladders at the end.
With such a pizza, B will get either two extra-large L slices and one l slice or one L and three l slices, depending on what A does on turn 3. The optimal ratio between l and L takes place when both of Bs possible takings above are equal, i.e., 2L + l = L + 3l, or L = 2l. The maximum portion size for B is (2L + l)/(3L + 3l), which is 5/9, as before. It turns out that no arrangement of slices will allow B to get more than five-ninths of the pizza, assuming best play by A.
You can pad the above 15-slice pizza with an even number of additional small slices between any of the z-ladders, so the above solution can be generalized to pizzas with any odd number of slices above 15. So, the answer to our third question is that B cannot win if the pizza has an even number of slices, or an odd number of slices less than 15.
This problem was popularized by the Dartmouth mathematician and gourmet puzzle master Peter Winkler. A formal treatment of this and other pizza-sharing problems is available here.
Congratulations to witzar on the brilliant solution to this difficult pizza zugzwang problem, and for earning this months Insights prize. Thank you to all who contributed.
See you soon for new insights.
Correction: April 9, 2022This puzzle solution previously referred to a 15-slice pizza as having 21 slices. The error has been corrected.
Read the original post:
The Secrets of Zugzwang in Chess, Math and Pizzas - Quanta Magazine