SOLUTION MANUAL
Game Theory Basics 1st Edition
By Bernhard von Stengel. Chapters 1 - 12
1
,TABLE OF CONTENTS NJ NJ NJ
1 - Nim and Combinatorial Games
NJ NJ NJ NJ NJ
2 - Congestion Games
NJ NJ NJ
3 - Games in Strategic Form
NJ NJ NJ NJ NJ
4 - Game Trees with Perfect Information
NJ NJ NJ NJ NJ NJ
5 - Expected Utility
NJ NJ NJ
6 - Mixed Equilibrium
NJ NJ NJ
7 - Brouwer’s Fixed-Point Theorem
NJ NJ NJ NJ
8 - Zero-Sum Games
NJ NJ NJ
9 - Geometry of Equilibria in Bimatrix Games
NJ NJ NJ NJ NJ NJ NJ
10 - Game Trees with Imperfect Information
NJ NJ NJ NJ NJ NJ
11 - Bargaining
NJ NJ
12 - Correlated Equilibrium
NJ NJ NJ
2
,Game Theory Basics NJ NJ
Solutions to Exercises N J N J
© Bernhard von Stengel 2022
N J NJ NJ NJ
Solution to Exercise 1.1 NJ NJ NJ
(a) Let ≤ be defined by (1.7). To show that ≤ is transitive, consider x, y, z with x ≤ y and y ≤ z. If x
NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ
= y then x ≤ z, and if y = z then also x ≤ z. So the only case left is x < y and y < z, which impl
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
ies x < z because < is transitive, and hence x ≤ z.
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
Clearly, ≤ is reflexive because x = x and therefore x ≤ x.
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
To show that ≤is antisymmetric, consider x and y with x y and
NJ NJ
≤ y x. If we
≤ had x ≠ y the
NJNJNJNJNJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJNJ NJ NJ NJNJNJNJNJ NJ NJ NJ NJ NJ NJ NJ
n x < y and y < x, and by transitivity x < x which contradicts (1.38). Hence x = y, as required.
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
This shows that ≤ is a partial order.
NJ NJ NJ NJ NJ NJ NJ NJ
Finally, we show (1.6), so we have to show that x < y implies x y and x ≠≤ y and vice versa. Le
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ
t x < y, which implies x y by (1.7). If we had x ≤= y then x < x, contradicting (1.38), so we also h
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
ave x ≠ y. Conversely, x y and x ≠ y imply by (1.7)x < y or x = y≤where the second case is excl
NJ NJ NJ NJ NJ NJNJN J NJ NJ NJ NJ NJ NJ NJ J NJ
N NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
uded, hence x < y, as required. NJ NJ NJ NJ NJ NJ
(b) Consider a partial order and≤assume (1.6) as a definition of <. To show that < is transitive, s
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
uppose x < y, that is, x y and x ≠ y, and≤y < z, that is, y z and y ≠ z. Because is≤transitive, x
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJ NJ NJ NJNJNJN
z. If we had
J
≤ x = z then x y≤and y x and hence x = y by ≤
NJ NJ NJ antisymmetry ≤ of , which contra
NJ NJ NJ NJ NJ NJNJNJNJNJ NJ NJ NJNJNJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJ NJ NJ
dicts x ≠ y, so we have x z and x ≠ z, that is,x < z by (1.6), as required.
≤ ≤
NJ NJ NJ NJ NJ NJ NJ NJNJNJN J NJ NJ NJ NJ NJ NJ J NJ
N NJ NJ NJ NJ NJ
Also, < is irreflexive, because x < x would by definition mean x x and x ≤
NJ NJ NJ ≠ x, but the latter is NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
not true. NJ
Finally, we show (1.7), so we have to show that x ≤ y implies x < y or x = y and vice versa, gi
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
ven that < is defined by (1.6). Let x ≤ y. Then if x = y, we are done, otherwise x ≠ y and then
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
by definition x < y. Hence, x ≤ y implies x < y or x = y. Conversely, suppose x < y or x = y.
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J N J NJ NJ NJ NJ N J
If x < y then x ≤ y by (1.6), and if x = y then x ≤ y because ≤ is reflexive. This completes t
NJ N J N J NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
he proof. NJ
Solution to Exercise 1.2 NJ NJ NJ
(a) In analysing the games of three Nim heaps where one heap has size one, we first lookat some
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ
examples, and then use mathematical induction to prove what we conjecture to be the losing posi
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
tions. A losing position is one where every move is to a winning position, because then the o
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
pponent will win. The point of this exercise is to formulate a precise statement to be proved, a
NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
nd then to prove it.NJ NJ NJ NJ
First, if there are only two heaps recall that they are losing if and only if the heaps are of eq
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
ual size. If they are of unequal size, then the winning move is to reduce thelarger heap so tha
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ NJ
t both heaps have equal size.
NJ NJ NJ NJ NJ
3
, Consider three heaps of sizes 1, m, n, where 1 m ≤ n. We ≤ observe the following: 1, 1, m is
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJNJ NJNJNJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ
winning, by moving to 1, 1, 0. Similarly, 1, m, m is winning, by moving to 0, m, m. Next, 1,
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
2, 3 is losing (observed earlier in the lecture), and hence 1, 2, n for n 4 is winning. 1, 3, n is
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
winning for any n 3 by moving to 1, 3, 2. For 1, 4, 5, reducing any heap produces a winning
≥ ≥
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
position, so this is losing. NJ NJ NJ NJ
The general pattern for the losing positions thus seems to be: 1, m, m 1, for even
NJ
+ numbers
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
m. This includes also the case m = 0, which we can take as the base case foran induction. We
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ NJ
now proceed to prove this formally.
NJ NJ NJ NJ NJ
First we show that if the positions of the form 1, m, n with m
NJ NJ n are≤losing when m is even
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJNJNJ NJ NJ NJ NJ NJ NJ
and n = m 1, then these+are the only losing positions because any other position 1, m, n with
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J
m
NJ n is winning. Namely,
N J N J
≤ if m = n then a winning move from1, m, m is to 0, m, m, so we
N J NJ N J NJ NJ N J NJ N J NJ NJ NJ NJ J
N NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
can assume m < n. If m is even then n > m 1 (otherwise we would be in the position 1, m, m
+
NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ N J N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
1) and so the winning move is to 1, m, m 1. If m is odd then the winning move is to 1,
+ +
N J N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
m, m 1, the same as position 1, m 1, m (this would also be a winning move from 1, m, m so ther
– −
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
e the winning move is not unique).
NJ NJ NJ NJ NJ NJ
Second, we show that any move from 1, m, m + 1 with even m is to a winning position,using as i
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ
nductive hypothesis that 1, mJ, mJ + 1 for even mJ and mJ < m is a losing position. The move t
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
o 0, m, m + 1 produces a winning position with counter-
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
move to 0, m, m. A move to 1, mJ, m + 1 for mJ < m is to a winning position with the counter-
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
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
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
winning position with counter- NJ NJ NJ
move to 0, m, m. A move to 1, m, mJ with mJ < m is also to a winning position with the counter-
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ
move to 1, mJ − 1, mJ if mJ is odd, and to 1, mJ 1, mJ if mJ is even (in which case mJ 1 < m b
NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ
ecause m is even). This concludes the induction proof.
NJ NJ NJ NJ NJ NJ NJ NJ
+ +
This result is in agreement with the theorem on Nim heap sizes represented as sums of powers of
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
2: 1 m ∗ +∗ n is losing 0
NJ N
+∗ if and only if, except for 2 , the powers of 2 making upm and n come i
J N J N J N J N J
N J
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ NJ NJ
n pairs. So these must be the same powers of 2, except for 1 = 20, which occurs in only m or n, w
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
here we have assumed that n is the larger number, so 1 appearsin the representation of n: We
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ NJ NJ N J
have m = 2a 2b 2c NJNJNJNJNJNJ NJNJNJNJNJNJ
+ + + ··· ··· ≥
NJ NJ N J NJ
N J NJ NJ NJ NJ NJ
for a > b > c > 1,s
+ + + · · · + +
NJ N J NJ N J N J N J NJNJNJNJNJNJNJN J J
N
o m is even, and, with the same a, b, c, . . ., n = 2
NJ NJ NJ
a 2b 2 c NJ 1 = m 1. Then NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ
N J N J N J N J N J N J
NJ NJ NJ NJ
NJ NJ NJNJNJN J N J
1 N
m
∗ +∗ +∗ ≡∗
J
n
NJNJNJNJNJN J
NJ
0. The following is an example using the
NJNJNJNJN J
NJ
bit representation where NJNJNJNJNJN J
NJ
N J NJ NJ NJ NJ NJ NJ NJ NJ NJ
m = 12 (which determines the bit pattern 1100, which of course depends on m):
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
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-
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
sum of the binary representations 01, 10, 11 is 00. Examples show that any other position i
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
swinning. The three numbers are n, n 1,+n
J
N 2.+If n is even then reducing the heap of size n
NJ NJ NJ NJ NJ NJ N J NJ N J N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
2 to 1 creates the position n, n 1, 1 which is losing as shown in (a). If n is odd, then n 1 i
+ +
NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ
s even and n 2 = n 1 1 so by the same argument, a winning move is to reduce the Nim
+ +
NJ NJ NJ NJNJNJ NJ N J NJNJNJ NJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N
heap of size n to 1 (which only works if n > 1).
( + )+
J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
N J N J NJ
4
Game Theory Basics 1st Edition
By Bernhard von Stengel. Chapters 1 - 12
1
,TABLE OF CONTENTS NJ NJ NJ
1 - Nim and Combinatorial Games
NJ NJ NJ NJ NJ
2 - Congestion Games
NJ NJ NJ
3 - Games in Strategic Form
NJ NJ NJ NJ NJ
4 - Game Trees with Perfect Information
NJ NJ NJ NJ NJ NJ
5 - Expected Utility
NJ NJ NJ
6 - Mixed Equilibrium
NJ NJ NJ
7 - Brouwer’s Fixed-Point Theorem
NJ NJ NJ NJ
8 - Zero-Sum Games
NJ NJ NJ
9 - Geometry of Equilibria in Bimatrix Games
NJ NJ NJ NJ NJ NJ NJ
10 - Game Trees with Imperfect Information
NJ NJ NJ NJ NJ NJ
11 - Bargaining
NJ NJ
12 - Correlated Equilibrium
NJ NJ NJ
2
,Game Theory Basics NJ NJ
Solutions to Exercises N J N J
© Bernhard von Stengel 2022
N J NJ NJ NJ
Solution to Exercise 1.1 NJ NJ NJ
(a) Let ≤ be defined by (1.7). To show that ≤ is transitive, consider x, y, z with x ≤ y and y ≤ z. If x
NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ
= y then x ≤ z, and if y = z then also x ≤ z. So the only case left is x < y and y < z, which impl
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
ies x < z because < is transitive, and hence x ≤ z.
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
Clearly, ≤ is reflexive because x = x and therefore x ≤ x.
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
To show that ≤is antisymmetric, consider x and y with x y and
NJ NJ
≤ y x. If we
≤ had x ≠ y the
NJNJNJNJNJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJNJ NJ NJ NJNJNJNJNJ NJ NJ NJ NJ NJ NJ NJ
n x < y and y < x, and by transitivity x < x which contradicts (1.38). Hence x = y, as required.
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
This shows that ≤ is a partial order.
NJ NJ NJ NJ NJ NJ NJ NJ
Finally, we show (1.6), so we have to show that x < y implies x y and x ≠≤ y and vice versa. Le
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ
t x < y, which implies x y by (1.7). If we had x ≤= y then x < x, contradicting (1.38), so we also h
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
ave x ≠ y. Conversely, x y and x ≠ y imply by (1.7)x < y or x = y≤where the second case is excl
NJ NJ NJ NJ NJ NJNJN J NJ NJ NJ NJ NJ NJ NJ J NJ
N NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
uded, hence x < y, as required. NJ NJ NJ NJ NJ NJ
(b) Consider a partial order and≤assume (1.6) as a definition of <. To show that < is transitive, s
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
uppose x < y, that is, x y and x ≠ y, and≤y < z, that is, y z and y ≠ z. Because is≤transitive, x
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJ NJ NJ NJNJNJN
z. If we had
J
≤ x = z then x y≤and y x and hence x = y by ≤
NJ NJ NJ antisymmetry ≤ of , which contra
NJ NJ NJ NJ NJ NJNJNJNJNJ NJ NJ NJNJNJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJ NJ NJ
dicts x ≠ y, so we have x z and x ≠ z, that is,x < z by (1.6), as required.
≤ ≤
NJ NJ NJ NJ NJ NJ NJ NJNJNJN J NJ NJ NJ NJ NJ NJ J NJ
N NJ NJ NJ NJ NJ
Also, < is irreflexive, because x < x would by definition mean x x and x ≤
NJ NJ NJ ≠ x, but the latter is NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
not true. NJ
Finally, we show (1.7), so we have to show that x ≤ y implies x < y or x = y and vice versa, gi
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
ven that < is defined by (1.6). Let x ≤ y. Then if x = y, we are done, otherwise x ≠ y and then
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
by definition x < y. Hence, x ≤ y implies x < y or x = y. Conversely, suppose x < y or x = y.
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J N J NJ NJ NJ NJ N J
If x < y then x ≤ y by (1.6), and if x = y then x ≤ y because ≤ is reflexive. This completes t
NJ N J N J NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
he proof. NJ
Solution to Exercise 1.2 NJ NJ NJ
(a) In analysing the games of three Nim heaps where one heap has size one, we first lookat some
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ
examples, and then use mathematical induction to prove what we conjecture to be the losing posi
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
tions. A losing position is one where every move is to a winning position, because then the o
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
pponent will win. The point of this exercise is to formulate a precise statement to be proved, a
NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
nd then to prove it.NJ NJ NJ NJ
First, if there are only two heaps recall that they are losing if and only if the heaps are of eq
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
ual size. If they are of unequal size, then the winning move is to reduce thelarger heap so tha
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ NJ
t both heaps have equal size.
NJ NJ NJ NJ NJ
3
, Consider three heaps of sizes 1, m, n, where 1 m ≤ n. We ≤ observe the following: 1, 1, m is
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJNJ NJNJNJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ
winning, by moving to 1, 1, 0. Similarly, 1, m, m is winning, by moving to 0, m, m. Next, 1,
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
2, 3 is losing (observed earlier in the lecture), and hence 1, 2, n for n 4 is winning. 1, 3, n is
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
winning for any n 3 by moving to 1, 3, 2. For 1, 4, 5, reducing any heap produces a winning
≥ ≥
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
position, so this is losing. NJ NJ NJ NJ
The general pattern for the losing positions thus seems to be: 1, m, m 1, for even
NJ
+ numbers
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
m. This includes also the case m = 0, which we can take as the base case foran induction. We
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ NJ
now proceed to prove this formally.
NJ NJ NJ NJ NJ
First we show that if the positions of the form 1, m, n with m
NJ NJ n are≤losing when m is even
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJNJNJNJNJNJ NJ NJ NJ NJ NJ NJ
and n = m 1, then these+are the only losing positions because any other position 1, m, n with
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J
m
NJ n is winning. Namely,
N J N J
≤ if m = n then a winning move from1, m, m is to 0, m, m, so we
N J NJ N J NJ NJ N J NJ N J NJ NJ NJ NJ J
N NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
can assume m < n. If m is even then n > m 1 (otherwise we would be in the position 1, m, m
+
NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ N J N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
1) and so the winning move is to 1, m, m 1. If m is odd then the winning move is to 1,
+ +
N J N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
m, m 1, the same as position 1, m 1, m (this would also be a winning move from 1, m, m so ther
– −
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
e the winning move is not unique).
NJ NJ NJ NJ NJ NJ
Second, we show that any move from 1, m, m + 1 with even m is to a winning position,using as i
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ
nductive hypothesis that 1, mJ, mJ + 1 for even mJ and mJ < m is a losing position. The move t
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
o 0, m, m + 1 produces a winning position with counter-
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
move to 0, m, m. A move to 1, mJ, m + 1 for mJ < m is to a winning position with the counter-
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
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
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
winning position with counter- NJ NJ NJ
move to 0, m, m. A move to 1, m, mJ with mJ < m is also to a winning position with the counter-
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ
move to 1, mJ − 1, mJ if mJ is odd, and to 1, mJ 1, mJ if mJ is even (in which case mJ 1 < m b
NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ
ecause m is even). This concludes the induction proof.
NJ NJ NJ NJ NJ NJ NJ NJ
+ +
This result is in agreement with the theorem on Nim heap sizes represented as sums of powers of
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
2: 1 m ∗ +∗ n is losing 0
NJ N
+∗ if and only if, except for 2 , the powers of 2 making upm and n come i
J N J N J N J N J
N J
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ NJ NJ
n pairs. So these must be the same powers of 2, except for 1 = 20, which occurs in only m or n, w
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
here we have assumed that n is the larger number, so 1 appearsin the representation of n: We
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ J
N NJ NJ NJ NJ N J
have m = 2a 2b 2c NJNJNJNJNJNJ NJNJNJNJNJNJ
+ + + ··· ··· ≥
NJ NJ N J NJ
N J NJ NJ NJ NJ NJ
for a > b > c > 1,s
+ + + · · · + +
NJ N J NJ N J N J N J NJNJNJNJNJNJNJN J J
N
o m is even, and, with the same a, b, c, . . ., n = 2
NJ NJ NJ
a 2b 2 c NJ 1 = m 1. Then NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ
N J N J N J N J N J N J
NJ NJ NJ NJ
NJ NJ NJNJNJN J N J
1 N
m
∗ +∗ +∗ ≡∗
J
n
NJNJNJNJNJN J
NJ
0. The following is an example using the
NJNJNJNJN J
NJ
bit representation where NJNJNJNJNJN J
NJ
N J NJ NJ NJ NJ NJ NJ NJ NJ NJ
m = 12 (which determines the bit pattern 1100, which of course depends on m):
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
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-
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
sum of the binary representations 01, 10, 11 is 00. Examples show that any other position i
NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
swinning. The three numbers are n, n 1,+n
J
N 2.+If n is even then reducing the heap of size n
NJ NJ NJ NJ NJ NJ N J NJ N J N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
2 to 1 creates the position n, n 1, 1 which is losing as shown in (a). If n is odd, then n 1 i
+ +
NJ NJ NJ NJ NJ NJ NJ N J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N J NJ
s even and n 2 = n 1 1 so by the same argument, a winning move is to reduce the Nim
+ +
NJ NJ NJ NJNJNJ NJ N J NJNJNJ NJNJNJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ N
heap of size n to 1 (which only works if n > 1).
( + )+
J NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ NJ
N J N J NJ
4
