Finally, we show 1.6, so we have to show thatG5H impliesGH andGH and

Solutions to Exercises Solution to Exercise 1.1 (a) Letbe dened by (1.7). To show thatis transitive, considerG– H– IwithGH and HI. IfG=H thenGI, and ifH=I then alsoGI. So the only case left isG5H andH5I, which impliesG5Ibecause5is transitive, and henceGI.Clearly,is reexive becauseG=Gand thereforeGG.To show thatis antisymmetric, considerGandHwithGH andHG. If we had G

Consider three heaps of sizes1– <– =, where1<= . We observe the following: 1–1–

– <

¸ 1for even< 0and<

5< is a losing position. The move to0– <– <¸ 1produces a winning position with counter-move to0– <– <. A move to1– <

– <¸ 1for<

5< is to a winning position with the counter-move to1– <

– <

¸ 1if< 0is even and to1– <

– <

1if< 0is odd. A move to1– <–

with<

5< is also to a winning position with the counter-move to1– <

1– < 0if<

is odd, and to1– <

¸ 1– < 0if< 0is even (in which case<

¸15

powers of 2:1¸<¸= is losing if and only if, except for2

, the powers of 2 making up

, which occurs in only

in the representation of=: We have<=2

¸ 2 1 ¸ 2 2 ¸ for071727 1, so

¸ 2 1 ¸ 2 2

¸ ¸

1=<¸ 1. Then 1¸ <¸ = 0. The following is an example using the bit representation where

<=12(which determines the bit pattern1100, which of course depends on<):

1=0001

12=1100

13=1101

Nim-sum0=0000 (b) We use (a). Clearly,1–2–3is losing as shown in (1.2), and because the Nim-sum of the binary representations01,10,11is00. Examples show that any other position is winning. The three numbers are=– =¸ 1– =¸2. If=is even then reducing the heap of size=¸2to1creates the position=– =¸ 1–1which is losing as shown in (a). If=is odd, then=¸1is even and=¸2=¹=¸ 1º ¸1so by the same argument, a winning move is to reduce the Nim heap of size=to1(which only works if=71).

2 2 / 4

Without (a), the following is a more complicated argument based entirely on the binary representation. Suppose the position=– =¸ 1– =¸2was losing. First, if the rst and last number is even then the three consecutive numbers have only one odd number among them, with a 1 in the nal 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 case1–2–3is excluded. So the three numbers have binary representations of the form01

:

11(with:0),10

:

00, and10

:

• 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 binary1110and 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 changes8!6,11!5, or13!3:

heapsize move 1 move 2 move 3

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 0000 0000 Note that the number ofremovedtokens is dierent for each of the three heaps, because the three changed bits from the Nim-sum 1110 aect dierent patterns for the rst three bits 100 (for heap size 8), 101 (for heap size 11), and 110 (for heap size 13).Solution to Exercise (a) In misère Nim, a single heap with=tokens is losing if==1, otherwise winning: If =71then the player wins by reducing the heap to size 1. If==0then 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; nally, 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–3is a losing position by the following counter-moves to the rst

move, in analogy to (1.2):

3 3 / 4

1–2–32–31–1–31–31–2–21–2–11–22–21–1–112–21–1–11

(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 nish 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 aecting 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:3heaps of

sizes0102 0:with011and022. We claim that this is a losing position

if and only if it is a losing position innormal play, that is, if the binary Nim-sum of 01– 02– • • • – 0: is zero (which we call, as before, a zero position). Suppose01– 02– • • • – 0: 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:=3and 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:=3and01=1) that these are of the form1–1– 03or1– 02–1where 02– 03 2; in both cases, the winning counter-move is to1–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 dene a losing position, and that care has to be taken when only two heaps remain.Solution to Exercise (a) In33Cram, 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 rst domino, such that a22square in one corner is occupied, leaving the L-shaped

remaining 5 squares:

II !

II !

• / 4