Game Theory Basics
Solutions to Exercises
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
transitive, suppose x < y, that is, x≤ y and x ≠ y, and y < z, that is, y≤ z and y ≠ z.
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.
1
, 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).
2
, 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):
3
, 1, 2, 3
2, 3 1, 1, 3 1, 3 1, 2, 2 1, 2, 1 1, 2
2, 2 1, 1, 1 1 2, 2 1, 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 k ≥ 3 heaps of
sizes a1 ≤ a2 ≤ · · · ≤ ak with a1 ≥ 1 and a2 ≥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
a1, a2, . . . , ak is zero (which we call, as before, a zero position). Suppose a1, a2, , ak
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 k = 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 k = 3 and a1 = 1) that these are of the form 1, 1, a3 or 1, a2, 1 where
a2, a3 ≥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 II
→ →
4
Solutions to Exercises
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
transitive, suppose x < y, that is, x≤ y and x ≠ y, and y < z, that is, y≤ z and y ≠ z.
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.
1
, 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).
2
, 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):
3
, 1, 2, 3
2, 3 1, 1, 3 1, 3 1, 2, 2 1, 2, 1 1, 2
2, 2 1, 1, 1 1 2, 2 1, 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 k ≥ 3 heaps of
sizes a1 ≤ a2 ≤ · · · ≤ ak with a1 ≥ 1 and a2 ≥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
a1, a2, . . . , ak is zero (which we call, as before, a zero position). Suppose a1, a2, , ak
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 k = 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 k = 3 and a1 = 1) that these are of the form 1, 1, a3 or 1, a2, 1 where
a2, a3 ≥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 II
→ →
4
