1
,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 x, y, z with x ≤ y and
y ≤ z. If x = y then x ≤ z, and if y = z then also x ≤ z. So the only case left is x < y
and y < z, which implies x < z because < is transitive, and hence x ≤ z.
Clearly, ≤ is reflexive because x = x and therefore x ≤ x.
To show that≤ is antisymmetric, consider x and y with x≤ y and y ≤ x. If we had
x ≠ y then x < y and y < x, and by transitivity x < x which contradicts (1.38). Hence
x = y, as required. This shows that ≤ is a partial order.
Finally, we show (1.6), so we have to show that x < y implies ≤x y and x ≠ y and
vice versa. Let x < y, which implies x≤ y by (1.7). If we had x = y then x < x,
contradicting (1.38), so we also have x ≠ y. Conversely,≤x y and x ≠ y imply by (1.7)
x < y or x = y where the second case is excluded, hence x < y, as required.
(b) Consider a partial order≤ and assume (1.6) as a definition of <. To show that < is
x y and x ≠ y, and y < z, that is, y≤ z and y ≠ z.
transitive, suppose x < y, that is, ≤
Because ≤ is transitive, x≤ z. If we had x = z then x≤ y and y≤ x and hence x = y
by antisymmetry of≤ , which contradicts x ≠ y, so we have x≤ z and x ≠ z, that is,
x < z by (1.6), as required.
Also, < is irreflexive, because x < x would by definition mean x≤ x and x ≠ x, but
the latter is not true.
Finally, we show (1.7), so we have to show that x ≤ y implies x < y or x = y and
vice versa, given that < is defined by (1.6). Let x ≤ y. Then if x = y, we are done,
otherwise x ≠ y and then by definition x < y. Hence, x ≤ y implies x < y or x = y.
Conversely, suppose x < y or x = y. If x < y then x ≤ y by (1.6), and if x = y then
x ≤ y 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.
2
, Consider three heaps of sizes 1, m, n, where 1 ≤ m ≤ n. We observe the following:
1, 1, m is winning, by moving to 1, 1, 0. Similarly, 1, m, m is winning, by moving to
0, m, m. Next, 1, 2, 3 is losing (observed earlier in the lecture), and hence 1, 2, n for
n ≥4 is winning. 1, 3, n is winning for any n ≥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, m, m+ 1, for even
numbers m. This includes also the case m = 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, m, n with m ≤ n are losing when
m is even and n = m +1, then these are the only losing positions because any other
position 1, m, n with m ≤ n is winning. Namely, if m = n then a winning move from
1, m, m is to 0, m, m, so we can assume m < n. If m is even then n > m + 1 (otherwise
we would be in the position 1, m, m + 1) and so the winning move is to 1, m, m+ 1. If
m is odd then the winning move is to 1, m, m– 1, the same as position 1, m– 1, m (this
would also be a winning move from 1, m, m so there the winning move is not unique).
Second, we show that any move from 1, m, m + 1 with even m is to a winning position,
using as inductive hypothesis that 1, mJ, mJ + 1 for even mJ and mJ < m is a losing
position. The move to 0, m, m + 1 produces a winning position with counter-move
to 0, m, m. A move to 1, mJ, m + 1 for mJ < m is to a winning position with the
counter-move to 1, mJ, mJ + 1 if mJ is even and to 1, mJ, mJ – 1 if mJ is odd. A move
to 1, m, m is to a winning position with counter-move to 0, m, m. A move to 1, m, mJ
with mJ < m is also to a winning position with the counter-move to 1, mJ – 1, mJ if mJ
is odd, and to 1, m+ +
J 1, mJ if mJ is even (in which case mJ 1 < m because m 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:31 +m3n is+ 3losing if and only if, except for 2 , the powers of 2 making up
0
m and n come in pairs. So these must be the same powers of 2, except for 1 = 20, which
occurs in only m or n, where we have assumed that n is the larger number, so 1 appears
in the representation of n: We have m = 2a + 2b + 2c + · · · for a > b > c > · · · ≥ 1,
so m is even, and, with the same a, b, c, . . ., n = 2a + 2b + 2c + · · · + 1 = m + 1. Then
31 + 3m + 3n ≡ 30. The following is an example using the bit representation where
m = 12 (which determines the bit pattern 1100, which of course depends on m):
1 = 0001
12 = 1100
13 = 1101
Nim-sum 0 = 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 n, n+1, n +2. If n is even then reducing the heap of
size n +2 to 1 creates the position n, n +1, 1 which is losing as shown in (a). If n is
odd, then n+1 is even and n+ 2 = (n +1 ) 1+so by the same argument, a winning
move is to reduce the Nim heap of size n to 1 (which only works if n > 1).
3
, Without (a), the following is a more complicated argument based entirely on the
binary representation. Suppose the position n, n +1, n +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 01k 11 (with k ≥0), 10k 00, and 10k 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 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 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 n tokens is losing if n = 1, otherwise winning: If
n > 1 then the player wins by reducing the heap to size 1. If n = 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):
4
,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 x, y, z with x ≤ y and
y ≤ z. If x = y then x ≤ z, and if y = z then also x ≤ z. So the only case left is x < y
and y < z, which implies x < z because < is transitive, and hence x ≤ z.
Clearly, ≤ is reflexive because x = x and therefore x ≤ x.
To show that≤ is antisymmetric, consider x and y with x≤ y and y ≤ x. If we had
x ≠ y then x < y and y < x, and by transitivity x < x which contradicts (1.38). Hence
x = y, as required. This shows that ≤ is a partial order.
Finally, we show (1.6), so we have to show that x < y implies ≤x y and x ≠ y and
vice versa. Let x < y, which implies x≤ y by (1.7). If we had x = y then x < x,
contradicting (1.38), so we also have x ≠ y. Conversely,≤x y and x ≠ y imply by (1.7)
x < y or x = y where the second case is excluded, hence x < y, as required.
(b) Consider a partial order≤ and assume (1.6) as a definition of <. To show that < is
x y and x ≠ y, and y < z, that is, y≤ z and y ≠ z.
transitive, suppose x < y, that is, ≤
Because ≤ is transitive, x≤ z. If we had x = z then x≤ y and y≤ x and hence x = y
by antisymmetry of≤ , which contradicts x ≠ y, so we have x≤ z and x ≠ z, that is,
x < z by (1.6), as required.
Also, < is irreflexive, because x < x would by definition mean x≤ x and x ≠ x, but
the latter is not true.
Finally, we show (1.7), so we have to show that x ≤ y implies x < y or x = y and
vice versa, given that < is defined by (1.6). Let x ≤ y. Then if x = y, we are done,
otherwise x ≠ y and then by definition x < y. Hence, x ≤ y implies x < y or x = y.
Conversely, suppose x < y or x = y. If x < y then x ≤ y by (1.6), and if x = y then
x ≤ y 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.
2
, Consider three heaps of sizes 1, m, n, where 1 ≤ m ≤ n. We observe the following:
1, 1, m is winning, by moving to 1, 1, 0. Similarly, 1, m, m is winning, by moving to
0, m, m. Next, 1, 2, 3 is losing (observed earlier in the lecture), and hence 1, 2, n for
n ≥4 is winning. 1, 3, n is winning for any n ≥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, m, m+ 1, for even
numbers m. This includes also the case m = 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, m, n with m ≤ n are losing when
m is even and n = m +1, then these are the only losing positions because any other
position 1, m, n with m ≤ n is winning. Namely, if m = n then a winning move from
1, m, m is to 0, m, m, so we can assume m < n. If m is even then n > m + 1 (otherwise
we would be in the position 1, m, m + 1) and so the winning move is to 1, m, m+ 1. If
m is odd then the winning move is to 1, m, m– 1, the same as position 1, m– 1, m (this
would also be a winning move from 1, m, m so there the winning move is not unique).
Second, we show that any move from 1, m, m + 1 with even m is to a winning position,
using as inductive hypothesis that 1, mJ, mJ + 1 for even mJ and mJ < m is a losing
position. The move to 0, m, m + 1 produces a winning position with counter-move
to 0, m, m. A move to 1, mJ, m + 1 for mJ < m is to a winning position with the
counter-move to 1, mJ, mJ + 1 if mJ is even and to 1, mJ, mJ – 1 if mJ is odd. A move
to 1, m, m is to a winning position with counter-move to 0, m, m. A move to 1, m, mJ
with mJ < m is also to a winning position with the counter-move to 1, mJ – 1, mJ if mJ
is odd, and to 1, m+ +
J 1, mJ if mJ is even (in which case mJ 1 < m because m 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:31 +m3n is+ 3losing if and only if, except for 2 , the powers of 2 making up
0
m and n come in pairs. So these must be the same powers of 2, except for 1 = 20, which
occurs in only m or n, where we have assumed that n is the larger number, so 1 appears
in the representation of n: We have m = 2a + 2b + 2c + · · · for a > b > c > · · · ≥ 1,
so m is even, and, with the same a, b, c, . . ., n = 2a + 2b + 2c + · · · + 1 = m + 1. Then
31 + 3m + 3n ≡ 30. The following is an example using the bit representation where
m = 12 (which determines the bit pattern 1100, which of course depends on m):
1 = 0001
12 = 1100
13 = 1101
Nim-sum 0 = 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 n, n+1, n +2. If n is even then reducing the heap of
size n +2 to 1 creates the position n, n +1, 1 which is losing as shown in (a). If n is
odd, then n+1 is even and n+ 2 = (n +1 ) 1+so by the same argument, a winning
move is to reduce the Nim heap of size n to 1 (which only works if n > 1).
3
, Without (a), the following is a more complicated argument based entirely on the
binary representation. Suppose the position n, n +1, n +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 01k 11 (with k ≥0), 10k 00, and 10k 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 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 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 n tokens is losing if n = 1, otherwise winning: If
n > 1 then the player wins by reducing the heap to size 1. If n = 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):
4
