Issuu

Game Theory Basics Solutions to Exercises © Bernhard von Stengel 2022 Solution to Exercise 1.1 (a) Let ≤ be defined by (1.7). To show that ≤ is transitive, consider 𝑥, 𝑦, 𝑧 with 𝑥 ≤ 𝑦 and 𝑦 ≤ 𝑧. If 𝑥 = 𝑦 then 𝑥 ≤ 𝑧, and if 𝑦 = 𝑧 then also 𝑥 ≤ 𝑧. So the only case left is 𝑥 < 𝑦 and 𝑦 < 𝑧, which implies 𝑥 < 𝑧 because < is transitive, and hence 𝑥 ≤ 𝑧. Clearly, ≤ is reflexive because 𝑥 = 𝑥 and therefore 𝑥 ≤ 𝑥. To show that ≤ is antisymmetric, consider 𝑥 and 𝑦 with 𝑥 ≤ 𝑦 and 𝑦 ≤ 𝑥. If we had 𝑥 ≠ 𝑦 then 𝑥 < 𝑦 and 𝑦 < 𝑥, and by transitivity 𝑥 < 𝑥 which contradicts (1.38). Hence 𝑥 = 𝑦, as required. This shows that ≤ is a partial order. Finally, we show (1.6), so we have to show that 𝑥 < 𝑦 implies 𝑥 ≤ 𝑦 and 𝑥 ≠ 𝑦 and vice versa. Let 𝑥 < 𝑦, which implies 𝑥 ≤ 𝑦 by (1.7). If we had 𝑥 = 𝑦 then 𝑥 < 𝑥, contradicting (1.38), so we also have 𝑥 ≠ 𝑦. Conversely, 𝑥 ≤ 𝑦 and 𝑥 ≠ 𝑦 imply by (1.7) 𝑥 < 𝑦 or 𝑥 = 𝑦 where the second case is excluded, hence 𝑥 < 𝑦, as required. (b) Consider a partial order ≤ and assume (1.6) as a definition of <. To show that < is transitive, suppose 𝑥 < 𝑦, that is, 𝑥 ≤ 𝑦 and 𝑥 ≠ 𝑦, and 𝑦 < 𝑧, that is, 𝑦 ≤ 𝑧 and 𝑦 ≠ 𝑧. Because ≤ is transitive, 𝑥 ≤ 𝑧. If we had 𝑥 = 𝑧 then 𝑥 ≤ 𝑦 and 𝑦 ≤ 𝑥 and hence 𝑥 = 𝑦 by antisymmetry of ≤, which contradicts 𝑥 ≠ 𝑦, so we have 𝑥 ≤ 𝑧 and 𝑥 ≠ 𝑧, that is, 𝑥 < 𝑧 by (1.6), as required. Also, < is irreflexive, because 𝑥 < 𝑥 would by definition mean 𝑥 ≤ 𝑥 and 𝑥 ≠ 𝑥, but the latter is not true. Finally, we show (1.7), so we have to show that 𝑥 ≤ 𝑦 implies 𝑥 < 𝑦 or 𝑥 = 𝑦 and vice versa, given that < is defined by (1.6). Let 𝑥 ≤ 𝑦. Then if 𝑥 = 𝑦, we are done, otherwise 𝑥 ≠ 𝑦 and then by definition 𝑥 < 𝑦. Hence, 𝑥 ≤ 𝑦 implies 𝑥 < 𝑦 or 𝑥 = 𝑦. Conversely, suppose 𝑥 < 𝑦 or 𝑥 = 𝑦. If 𝑥 < 𝑦 then 𝑥 ≤ 𝑦 by (1.6), and if 𝑥 = 𝑦 then 𝑥 ≤ 𝑦 because ≤ is reflexive. This completes the proof. Solution to Exercise 1.2 (a) In analysing the games of three Nim heaps where one heap has size one, we first look at some examples, and then use mathematical induction to prove what we conjecture to be the losing positions. A losing position is one where every move is to a winning position, because then the opponent will win. The point of this exercise is to formulate a precise statement to be proved, and then to prove it. First, if there are only two heaps recall that they are losing if and only if the heaps are of equal size. If they are of unequal size, then the winning move is to reduce the larger heap so that both heaps have equal size.

Consider three heaps of sizes 1, 𝑚, 𝑛, where 1 ≤ 𝑚 ≤ 𝑛. We observe the following: 1, 1, 𝑚 is winning, by moving to 1, 1, 0. Similarly, 1, 𝑚, 𝑚 is winning, by moving to 0, 𝑚, 𝑚. Next, 1, 2, 3 is losing (observed earlier in the lecture), and hence 1, 2, 𝑛 for 𝑛 ≥ 4 is winning. 1, 3, 𝑛 is winning for any 𝑛 ≥ 3 by moving to 1, 3, 2. For 1, 4, 5, reducing any heap produces a winning position, so this is losing. The general pattern for the losing positions thus seems to be: 1, 𝑚, 𝑚 + 1, for even numbers 𝑚. This includes also the case 𝑚 = 0, which we can take as the base case for an induction. We now proceed to prove this formally. First we show that if the positions of the form 1, 𝑚, 𝑛 with 𝑚 ≤ 𝑛 are losing when 𝑚 is even and 𝑛 = 𝑚 + 1, then these are the only losing positions because any other position 1, 𝑚, 𝑛 with 𝑚 ≤ 𝑛 is winning. Namely, if 𝑚 = 𝑛 then a winning move from 1, 𝑚, 𝑚 is to 0, 𝑚, 𝑚, so we can assume 𝑚 < 𝑛. If 𝑚 is even then 𝑛 > 𝑚 + 1 (otherwise we would be in the position 1, 𝑚, 𝑚 + 1) and so the winning move is to 1, 𝑚, 𝑚 + 1. If 𝑚 is odd then the winning move is to 1, 𝑚, 𝑚 − 1, the same as position 1, 𝑚 − 1, 𝑚 (this would also be a winning move from 1, 𝑚, 𝑚 so there the winning move is not unique). Second, we show that any move from 1, 𝑚, 𝑚 + 1 with even 𝑚 is to a winning position, using as inductive hypothesis that 1, 𝑚 0 , 𝑚 0 + 1 for even 𝑚 0 and 𝑚 0 < 𝑚 is a losing position. The move to 0, 𝑚, 𝑚 + 1 produces a winning position with counter-move to 0, 𝑚, 𝑚. A move to 1, 𝑚 0 , 𝑚 + 1 for 𝑚 0 < 𝑚 is to a winning position with the counter-move to 1, 𝑚 0 , 𝑚 0 + 1 if 𝑚 0 is even and to 1, 𝑚 0 , 𝑚 0 − 1 if 𝑚 0 is odd. A move to 1, 𝑚, 𝑚 is to a winning position with counter-move to 0, 𝑚, 𝑚. A move to 1, 𝑚, 𝑚 0 with 𝑚 0 < 𝑚 is also to a winning position with the counter-move to 1, 𝑚 0 − 1, 𝑚 0 if 𝑚 0 is odd, and to 1, 𝑚 0 + 1, 𝑚 0 if 𝑚 0 is even (in which case 𝑚 0 + 1 < 𝑚 because 𝑚 is even). This concludes the induction proof. This result is in agreement with the theorem on Nim heap sizes represented as sums of powers of 2: ∗1+∗𝑚 +∗𝑛 is losing if and only if, except for 20 , the powers of 2 making up 𝑚 and 𝑛 come in pairs. So these must be the same powers of 2, except for 1 = 20 , which occurs in only 𝑚 or 𝑛, where we have assumed that 𝑛 is the larger number, so 1 appears in the representation of 𝑛: We have 𝑚 = 2𝑎 + 2𝑏 + 2𝑐 + · · · for 𝑎 > 𝑏 > 𝑐 > · · · ≥ 1, so 𝑚 is even, and, with the same 𝑎, 𝑏, 𝑐, . . ., 𝑛 = 2𝑎 + 2𝑏 + 2𝑐 + · · · + 1 = 𝑚 + 1. Then ∗1 + ∗𝑚 + ∗𝑛 ≡ ∗0. The following is an example using the bit representation where 𝑚 = 12 (which determines the bit pattern 1100, which of course depends on 𝑚): 1 12 13 Nim-sum 0

= = = =

0001 1100 1101 0000

(b) We use (a). Clearly, 1, 2, 3 is losing as shown in (1.2), and because the Nim-sum of the binary representations 01, 10, 11 is 00. Examples show that any other position is winning. The three numbers are 𝑛, 𝑛 + 1, 𝑛 + 2. If 𝑛 is even then reducing the heap of size 𝑛 + 2 to 1 creates the position 𝑛, 𝑛 + 1, 1 which is losing as shown in (a). If 𝑛 is odd, then 𝑛 + 1 is even and 𝑛 + 2 = (𝑛 + 1) + 1 so by the same argument, a winning move is to reduce the Nim heap of size 𝑛 to 1 (which only works if 𝑛 > 1).

Without (a), the following is a more complicated argument based entirely on the binary representation. Suppose the position 𝑛, 𝑛 + 1, 𝑛 + 2 was losing. First, if the first and last number is even then the three consecutive numbers have only one odd number among them, with a 1 in the final position of the “sum without carry” of the Nim sizes. Hence the Nim-sum is nonzero and the position is winning. So the three numbers must start and end with an odd number, with a single even number in the middle. If the three numbers have the same largest power of 2 in their binary representation, the leftmost binary column in the Nim-sum is odd, again a winning position. So the middle even number must be a power of 2, which is at least 4 because the case 1, 2, 3 is excluded. So the three numbers have binary representations of the form 01 𝑘 11 (with 𝑘 ≥ 0), 10 𝑘 00, and 10 𝑘 01. So the leftmost and rightmost column have an even number of 1’s (necessary to have a losing position), but the second-to-last column has only one 1 in it and hence the Nim-sum is again nonzero. (c) This is a winning position because the Nim-sum of the heaps is binary 1110 and thus nonzero, as shown in the following table. The table also shows the three winning moves obtained by changing the bits of the binary representation corresponding to the Nim-sum, which are one of the heap changes 8 → 6, 11 → 5, or 13 → 3: heapsize

move 1

move 2

8 = 1000

→ 0110

= 6

1000

= 8

1000

= 8

11 = 1011

1011

= 11

→ 0101

= 5

1011

= 11

13 = 1101

1101

= 13

1101

= 13

→ 0011

= 3

Nim-sum 1110

0000

move 3

0000

Note that the number of removed tokens is different for each of the three heaps, because the three changed bits from the Nim-sum 1110 affect different patterns for the first three bits 100 (for heap size 8), 101 (for heap size 11), and 110 (for heap size 13). Solution to Exercise 1.3 (a) In misère Nim, a single heap with 𝑛 tokens is losing if 𝑛 = 1, otherwise winning: If 𝑛 > 1 then the player wins by reducing the heap to size 1. If 𝑛 = 0 then the player cannot move and has won; although this is the case of “no heap” rather than “one heap”, this will be useful in (c). Two heaps are a winning position if one of the heaps has size 1, where the winning move is to remove the entire other heap. Otherwise, both heaps have at least two tokens in them. Then this is a losing position if the two heaps are equal, because any move from there leads to a winning position as follows: If one heap is removed entirely, then the other player responds by reducing the remaining heap to size 1; if one heap is reduced to size 1, then the other player removes the entire other heap; finally, if one heap is reduced to size 2 or larger, then the other player equalizes the heaps again. Consequently, two unequal heaps are therefore a winning position. (b) In misère Nim, 1, 2, 3 is a losing position by the following counter-moves to the first move, in analogy to (1.2):

1, 2, 3

2, 3

1, 1, 3

1, 3

1, 2, 2

1, 2, 1

1, 2

2, 2

1, 1, 1

2, 2

1, 1, 1

(c) Losing positions in misère Nim are given by any odd number of heaps with a single token each, because then all move sequences finish with the current player taking the last token. Conversely, any even number of heaps with a single token each is a winning position. More generally, any even number of single-token heaps can be added (as a game sum) to a misère Nim position without affecting whether it is winning or losing, where the winning player removes a single-token heap if the other player has just done so, or otherwise makes a winning move in another Nim heap. Consider now a general position and remove all pairs of single-token heaps. If at most two heaps remain, this is covered in (a). Otherwise there are 𝑘 ≥ 3 heaps of sizes 𝑎 1 ≤ 𝑎 2 ≤ · · · ≤ 𝑎 𝑘 with 𝑎 1 ≥ 1 and 𝑎 2 ≥ 2. We claim that this is a losing position if and only if it is a losing position in normal play, that is, if the binary Nim-sum of 𝑎 1 , 𝑎2 , . . . , 𝑎 𝑘 is zero (which we call, as before, a zero position). Suppose 𝑎 1 , 𝑎2 , . . . , 𝑎 𝑘 is a zero position, and consider any move, which creates a non-zero position. If the new position has only two heaps, which can only happen if 𝑘 = 3 and an entire heap has been removed, then the remaining two heaps are unequal, which by (a) is a winning position. If at least three heaps remain, then we have to consider the possibility (if 𝑘 = 3 and 𝑎1 = 1) that these are of the form 1, 1, 𝑎3 or 1, 𝑎2 , 1 where 𝑎 2 , 𝑎3 ≥ 2; in both cases, the winning counter-move is to 1, 1, 1. In all other cases, the winning counter-move is back to a zero position, as in Nim with normal play; this includes the case that this zero position has only two heaps, because then these two heaps are equal and at least of size two, which is also a losing position in misère Nim. In short, misère Nim is played optimally very similarly to Nim, except that an odd rather than even number of single-token heaps define a losing position, and that care has to be taken when only two heaps remain. Solution to Exercise 1.4 (a) In 3 × 3 Cram, there are, up to symmetry, only two moves for player I, namely placing the domino such that it occupies a corner square or such that it occupies the center square. In either case, player II can respond by placing her domino alongside the first domino, such that a 2 × 2 square in one corner is occupied, leaving the L-shaped remaining 5 squares: II

→

→ 4

Then no matter what player I does, II will still be able to place the last domino, and player I loses. Hence, 3 × 3 Cram is a win for player II. (b) When both 𝑚 and 𝑛 are even, player II will win in 𝑚 × 𝑛 Cram by playing “copycat”, using the central symmetry of the board. That is, whenever player I places his domino, player II responds by placing her domino on the square obtained by point-reflection on the center of the board (shown as a dot in the following pictures). The following is an example move sequence on a 4 × 6 board: I

→ I

→ II

→

→ II

→ I

→

Then the domino pattern of the board will have that central symmetry whenever player I makes his move, so that the response move of player II will always be possible. That is to say, the two adjacent squares in question are always empty because their symmetric counterparts have been empty when player I made his move. Be careful: Any “copycat” strategy requires that the underlying symmetry of the situation is preserved. This fails when using the symmetry where the board is reflected along a line: here player I could place a domino on the line itself and II would not have a counter-move. So “by copycat” is not a satisfactory answer. (c) In 𝑚 × 𝑛 Cram when 𝑚 is odd and 𝑛 is even (or vice versa), player I will win by placing his domino on the center pair of squares (in the middle row or column), and then playing copycat as described before for player II in (b). The following shows how this could start on a 4 × 5 board: I

→

Solution to Exercise 1.5 (a) Player I always wins in these situations. We describe directly the winning move in the games with two rows of dots: For 2 × 𝑚 Chomp, the winning move is to remove the bottom right dot (2, 𝑚), leaving a pattern like the following when 𝑚 = 4:

Afterwards, player I can always re-create this pattern by removing the dot that is diagonally adjacent to the dot that player II removed. That is, any move of player II of the form (1, 𝑖) for 𝑖 > 1 can be countered by (2, 𝑖 − 1), and any move (2, 𝑖) by (1, 𝑖 + 1). So player I has always a move left and wins. For square games of size 𝑚 × 𝑚 with 𝑚 ≥ 2, the winning move is (2, 2). Then player I can respond to a move of type (𝑖, 1) by removing the dot (1, 𝑖) and vice versa, until player II is forced to take (1, 1) and loses. (b) Remove the “poisoned cookie”, that is, the dot on (1, 1). Then the last player loses by not being able to move any more, exactly when before she would have had to take the poisoned cookie. (c) If removing the bottom right dot (𝑚, 𝑛) is a winning move, then we are done. If not, there is a counter-move (𝑖, 𝑗) by player II that would create a losing situation for player I. But then player I could make (𝑖, 𝑗) to start with, creating the same losing situation for player II. So this game is a win for player I, even though we don’t know the winning move. This beautiful argument works only when considering the removal of a single dot as a first move, which is “absorbed” into the rectangle of removed dots with the next move; it would not work for any other first move. Note that in the case 𝑚 = 𝑛, (a) provides an explicit winning move. Solution to Exercise 1.6 (a) The completed table for columns 5 and 6 is 0

∗0

∗1

∗2

∗3

∗4

∗5

∗6

∗1

∗2

∗0

∗4

∗5

∗3

∗7

∗2

∗0

∗1

∗5

∗3

∗4

∗8

∗3

∗4

∗5

∗6

∗2

∗0

∗1

(b) The queen is on a square with Nim value 2, so one winning move is to reduce the Nim heap to size 2 to make this a losing position. However, there are also two squares with Nim value 4 that the queen can reach, on row 3 column 1 and on row 0 column 4. These are the only such squares. Moving the queen to either of these also gives a losing position because it is equivalent to ∗4 + ∗4. Any other move would produce a sum of two different Nim heaps, which is not a losing position, so there are no other winning moves.

Solution to Exercise 1.7 (a) Putting the domino anywhere on the board produces two independent boards of size 1 × 𝑘 and 1 × (𝑛 − 𝑘 − 2). The two board lengths add up to 𝑛 − 2 because two squares are taken away by the domino. The resulting position is a sum of two games because the player can only move in one of them, which is equivalent to the sum of Nim heaps ∗𝐷 𝑘 + ∗𝐷𝑛−𝑘−2 . By symmetry, we only have to consider 𝑘 ≤ 𝑛2 − 1. As an example, if 𝑛 = 10, then the largest 𝑘 to be considered (where the domino is placed in the middle of the strip) is 𝑘 = 4 = 10 2 − 1,

and if 𝑛 is odd, as when 𝑛 = 9, then the largest 𝑘 to be considered is 𝑘 = 3 ≤ 92 − 1, because for 𝑘 = 4 the domino is already past the middle:

Hence, 𝐷𝑛 = mex({𝐷 𝑘 ⊕ 𝐷𝑛−𝑘−2 | 0 ≤ 𝑘 ≤

𝑛 − 1}). 2

(b) We use the result in (a). Instead of mex({. . .}) we use the simpler notation mex(. . .) and obtain 𝐷0

𝐷1 = 0,

𝐷2

mex(𝐷0 ⊕ 𝐷0 ) = mex(0) = 1,

𝐷3

mex(𝐷0 ⊕ 𝐷1 ) = mex(0) = 1,

𝐷4

mex(𝐷0 ⊕ 𝐷2 , 𝐷1 ⊕ 𝐷1 ) = mex(1, 0) = 2,

𝐷5

mex(𝐷0 ⊕ 𝐷3 , 𝐷1 ⊕ 𝐷2 ) = mex(1, 1) = 0,

𝐷6

mex(𝐷0 ⊕ 𝐷4 , 𝐷1 ⊕ 𝐷3 , 𝐷2 ⊕ 𝐷2 ) = mex(2, 1, 0) = 3,

𝐷7

mex(𝐷0 ⊕ 𝐷5 , 𝐷1 ⊕ 𝐷4 , 𝐷2 ⊕ 𝐷3 ) = mex(0, 2, 0) = 1,

𝐷8

mex(𝐷0 ⊕ 𝐷6 , 𝐷1 ⊕ 𝐷5 , 𝐷2 ⊕ 𝐷4 , 𝐷3 ⊕ 𝐷3 ) = mex(3, 0, 3, 0) = 1,

𝐷9

mex(𝐷0 ⊕ 𝐷7 , 𝐷1 ⊕ 𝐷6 , 𝐷2 ⊕ 𝐷5 , 𝐷3 ⊕ 𝐷4 ) = mex(1, 3, 1, 3) = 0,

𝐷10

mex(𝐷0 ⊕ 𝐷8 , 𝐷1 ⊕ 𝐷7 , 𝐷2 ⊕ 𝐷6 , 𝐷3 ⊕ 𝐷5 , 𝐷4 ⊕ 𝐷4 )

mex(1, 1, 2, 1, 0) = 3.

For your possible interest, the sequence 𝐷0 , 𝐷1 , . . . is 0, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0, 1, 1, 3, 0, . . . and eventually repeats with period 34, the highest occurring value being 9 (which requires that 8 occurs – explain! But no 6 occurs – how can that be?). Recognised from those 𝑛 where 𝐷𝑛 = 0, Cram on a 1 × 𝑛 board is a losing game for 𝑛 = 0, 1, 5, 9, 15, and others. Solution to Exercise 1.8 (a) Here, black will win, by simply closing the gap to the white counter whenever white makes a move. So black has always a move left and wins.

(b) The close relationship, hopefully revealed by (a), is to Poker Nim, where a move that widens the gap between the two counters amounts to adding tokens to the heap, whereas narrowing the gap amounts to reducing the heap size. That is, the gap between the two counters is the size of the Nim heap that corresponds to that row. The equivalent Nim heaps are shown on the left: *2 *3 *1 *3 *0 *2 *6 *4

8 7 6 5 4 3 2 1 a b

c d e

g h

As an experienced Nim player, you may spot that the top three rows 8, 7, 6, equivalent to ∗2, ∗3, ∗1, sum to a losing position, and so do the bottom three rows 3, 2, 1 that are equivalent to ∗2, ∗6, ∗4, and of course row 4 which is equivalent to ∗0. So one winning move is to turn row 7 or row 5, either of which is equivalent to ∗3, to ∗0, by moving e5 to b5, or h7 to e7. We now look systematically at all possible winning moves. First of all, the entire game, call it 𝐺, is a sum of eight independent Poker-Nim heaps. That is, 𝐺 is the game-sum 𝐺 = ∗2 + ∗3 + ∗1 + ∗3 + ∗0 + ∗2 + ∗6 + ∗4 where we saw that 𝐺 ≡ ∗3 and therefore 𝐺 + ∗3 ≡ 0. A winning move is therefore to add the Nim-sum ∗3 to 𝐺, which we do by adding ∗3 to any one of the eight Poker-Nim heaps above. We then have to check if the resulting new heap size is a feasible move: row 8 :

∗2 + ∗3 ≡ ∗1

row 7 :

∗3 + ∗3 ≡ ∗0

row 6 :

∗1 + ∗3 ≡ ∗2

row 5 :

∗3 + ∗3 ≡ ∗0

row 4 :

∗0 + ∗3 ≡ ∗3

row 3 :

∗2 + ∗3 ≡ ∗1

row 2 :

∗6 + ∗3 ≡ ∗5

row 1 :

∗4 + ∗3 ≡ ∗7

These equivalent Nim heap are computed by splitting the heaps into distinct powers of two. For example, in row 2 we have, in more detail, ∗6+∗3 ≡ ∗4+∗2+∗2+∗1 ≡ ∗4+∗1 ≡ ∗5. The above moves are then indeed winning: For example, reducing in row 8 the gap of size 2 to size 1 (in terms of Nim heaps: ∗2, to which we added ∗3, becomes ∗1) reaches the overall position ∗1 + ∗3 + ∗1 + ∗3 + ∗0 + ∗2 + ∗6 + ∗4

which is equivalent to ∗0 and a losing position. Similarly, the above moves in rows 7, 5, 3, and 2 reduce the gap between the counters to obtain a smaller Nim-heap. In the other rows, the gap needs to be increased: •

The move in row 6 from ∗1 to ∗2 is a Poker-Nim move because it increases the gap from 1 to 2, where the white counter is moved from b6 to a6.

•

The move in row 4 from ∗0 to ∗3 increases the gap from 0 to 3, where the white counter is moved from c4 to f4. This move would not be possible for Black. Nevertheless, the game can be treated as an impartial game because the winning moves that reduce a gap between the counters (that is, reduce the respective Nim heap) are available to either player; the Poker-Nim moves are not needed in order to win (they never are, which is the whole point of the mex rule).

•

The required move in row 1 from ∗4 to ∗7 would need to increase the gap from 4 to 7, but this not possible for either player because neither counter can be moved three squares outwards. Hence, there is no winning move in this bottom row. With White to start this is the only row where White does not have a winning move. This game is known as Northcott’s game. There are Java applets on the internet where the game could be played interactively, such as http://www.cut-the-knot.org/ recurrence/Northcott.shtml , but these no longer work on modern browsers.

Solution to Exercise 1.9 (a) This game fulfills the ending condition because no node can be visited again, because there are no “cycles” in the digraph. (b) Because the counters are moved independently, this is a sum of games, each corresponding to a counter. The nodes represent positions of a single game with one counter only. The options of a node are simply the nodes that the counter can move to. Every node is equivalent to a Nim heap. Nodes L and N have no successor node, so these are nodes from which a counter cannot be moved any more. Consequently, they are equivalent to the empty Nim heap ∗0. The nodes that have only L or N as successor are H, P, and M. They get Nim value 1 as they are equivalent to ∗1. Next, those nodes get Nim values that only have successors that already have Nim values, computed as the mex of those values. For example, D has only H as successor, which has Nim value 1, so D gets mex(1) = 0 as its Nim value. Node O gets mex(0, 1) = 2 as it Nim value, then K gets 3 which is mex(0, 1, 2). This continues in this fashion. The Nim values of all nodes are given as below. In order to determine if the sum of games determined by the counters is winning or losing, we have to take the Nim sum of the respective Nim values. We can ignore the two counters on H because they cancel each other. The resulting Nim sum for the counters on A, F, G, K is 2 ⊕ 3 ⊕ 4 ⊕ 3 = 2 ⊕ 4 = 6. This is nonzero, so this is a winning position and the first player to move wins. There is one winning move, from G to J, because the counter on G has Nim value 4, the highest power of two in the Nim sum. The only other potential alternative would be to obtain a second 4 in the Nim sum to

1 B

1 G

0 P

3 E

1 O

1 I

2 N

0 M

cancel the existing 4 of the counter on G by moving from F to G, but this would not give a Nim sum of 0, so moving from G to J is the only winning move. (c) When the arrow from J to K is reversed so that it points from K to J instead, the Nim value of J, which is 2, does not change, because 2 is still the mex of {0, 1}, which is the same as the mex of the larger set {0, 1, 3} when K is also a successor. Similarly, the Nim value of K, which is mex{0, 1, 2} = 3, does not change, because the additional successor J has value 2, which is already in the set {0, 1, 2}. Because all Nim values remain the same, the computation in (b) applies as well and the winning move is as before, so nothing changes. Solution to Exercise 1.10 In order to represent Chomp in the normal play convention where the last player to move wins, we remove the top left dot, the “poisoned cookie”, indicated by a small circle in the picture below. Moreover, we replace the dots by squares. By the chomp rule, a move removes a square and with it all squares to the right and below it. The picture below describes all possible positions of the game. The starting position is A.