MATHEMATICAL.

OLYMPIAD.CH
MATHEMATIK-OLYMPIADE
OLYMPIADES DE MATHÉMATIQUES
OLIMPIADI DELLA MATEMATICA

Combinatorial Games
Tanish Patil
Updated: February 21, 2023
Version: 1.0.1

Contents
1 Introduction 2

2 States of Matter and States that Matter 3

2.1 Laying down some foundations . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Chomping our way to a contradiction. . . . . . . . . . . . . . . . . . . . . 9

3 Symmetry: a man, a plan, a canal, Panama! 11

3.1 Whatever you can do, I can do better . . . . . . . . . . . . . . . . . . . . . 11
3.2 Induction for the winduction . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Avoiding common pitfalls 14

A Matchsticks, Bowling Pins and Chocolate Bars 16

A.1 Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
A.2 Chomp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
A.3 Kayles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
A.4 Cram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
A.5 Notakto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1
1 Introduction
Since the dawn of time, Olympiad contestants have been presented with questions in which
two competitors play a game with bizarrely specific rules, where they must determine
which of the two has a winning strategy. The adventures of these two eternal rivals, often
named Alice and Bob, but who have also been known to go by monikers as varied as
Abdulaziz1 and Batman2 are a classic staple of combinatorics. This script, which draws
on the excellent work of Pranav Sriram in Chapter 5 of his combinatorics book, aims
to provide an introduction to how to deal with these problems and illustrate examples
of useful tricks one can use to simplify things, often by exploiting the symmetry of the
game.

Definition 1.1 (Combinatorial Game). A combinatorial game is a game played

between two players who alternately make moves on some well defined game space,
starting from an initial configuration. The game must satisfy the following criteria:
• Play is dictated by strict rules to which both players adhere. These rules
describe what moves each player is allowed to make in any given situation, as
well as the winning conditions that determine when a certain player wins or
when the game is drawn. If any of these happen, the game ends.
• Both players have perfect information. This means that they know the com-
plete set of rules as well as every aspect of the current state of the game.
• There is no randomness in the game. The outcome of every move and all its
modifications to the state of the game are deterministic and known to both
players in advance.

The game of chess, tic-tac-toe and go are all examples of combinatorial games. On the
other hand, games like poker, memory, Tichu or Rock-Paper-Scissors are not, as each of
them either contains aspects that are not known to both players at all times or aspects
of randomness. Note also, that the rules do not necessarily have to be the same for both
players. Many of the combinatorial games we will see in Olympiad problems have an
additional property:

Definition 1.2 (Finite Game). A combinatorial game is finite, if it is not possible

for it to go on for an infinite number of moves.

It is not always easy to see that a certain game is finite and may well have to be proven
as part of the problem. If not mentioned otherwise, if a game goes on forever, we say that
it is drawn. The game of chess for example is only a finite game due to a special rule,
called "the 50 move rule". For other games, like tic-tac-toe, it is very easy to argue why
it is finite as the number of total moves is clearly bounded.
[Zermelo] For every finite game there are two exclusive possibilities: Either one of the two
1
Several Arabic-language contests have used Abdul to date.
2
Hasn’t actually happened yet, but one can hope.

2
players can force a win, or both players can force a draw.
As a direct corollary we get that in a game without draws, one of the players has a
winning strategy. This is somewhat intuitive but not easy to prove, considering that the
number of possible states and moves could still be infinite and the length of the game
must not necessarily be bounded. For the purpose of this script however, all games will
not only be finite but also bounded in length with a finite number of possible states and
a finite number of possible moves from any state. In this case it is not too hard to see
why the result must be true: By starting from the "end" states, the states in which
someone has won the game or the game is drawn, we work backwards and figure out who
is winning in any given state inductively. The idea of starting at the end of the game
and moving backwards in time is one of the key lines of attack when solving problems
involving combinatorial games.

2 States of Matter and States that Matter

2.1 Laying down some foundations
Let us start by making precise definitions of some of the crucial concepts about combina-
torial games.

Definition 2.1 (Game State). A state of a game is the collection of all relevant
information about the game at a certain point in time.

For example, a state in chess consists of knowing not only where all the pieces are on the
board, but also things like whose turn it is to move, if the players still have the right to
castle, whether the last move allowed for the special move "en passant" and a few more
technicalities like these. Essentially, the state of a game consists of all the information
needed to continue playing.

Definition 2.2 (End State). An end-state is a state immediately following the

final move of the game, in which one of the two players has achieved their winning
condition.

An end-state in chess would be a state with a checkmate or stalemate position, or the

state after a draw for any other reason. From here on out, we will adhere to the convention
that our two players are called A and B, where player A makes the first move.

Definition 2.3 (Winning State). A state is said to be X-winning if player X can

force a win from that state onward.

We will often paraphrase this definition by saying that a certain player "has a winning
strategy" or "is winning" in a given state. By Zermelo’s Theorem, every finite combina-
torial game without draws is winning for one of the two players. Similarly, states can also

3
be said to be tied if they are not winning for either player.

Definition 2.4 (Winning Property). A winning property for player X is a property

of the game state that implies that the state is X-winning.

Note that a fundamental piece of information in a games state is whose turn it is to move
next. In a game where both players have the same win condition and both players can
make the same kinds of moves, symmetry tells us that changing the person whose turn it
is to move in an otherwise unchanged state will change who the state is winning for.

Definition 2.5 (Symmetric Game). A game is said to be symmetric a if the only

difference between the two players is who goes first. This means that the rules, the
winning conditions and the initial state of the game are all symmetric with respect
the two players.
a
This is just the name we give here, but in the existing mathematical literature we usually
refer to such games as impartial.

In a symmetric game, we sometimes prefer to simplify matters by talking about whether

a state is winning in terms of the player whose turn it is to move next or the player that
has just moved.

Definition 2.6 (1- and 2-winning). For a state in a symmetric game, we say it is
1-winning if the player about to move has a winning strategy, and 2-winning if the
other player has a winning strategy.

Now, theoretically we could solve any finite game problem by starting at the end-states,
labelling them as either A-winning, B- winning or tied and then considering the states
immediately preceding them inductively. We could continue to work backwards in this
fashion until we have labelled every single state. A state can be deduced to be X-winning
in two different ways:
• If it is X’s turn to move and they can reach at least one state that is already known
to be X-winning.
• If it is not X’s turn to move and all the states they can reach by X’s opponent are
X-winning.
Similarly, a state can be deduced to be tied if it is X’s move, there are no states reachable
that are X-winning, but at least one that is tied. However, in practice, it is never feasible
to solve the problem in this manner because there are often too many states to evaluate.
This is where the utility of a winning property comes into play - if we can prove that a
specific property of the game state allows player X to force a win, and then prove that
the game will always reach a state with this property, then we will have proven that
X always wins. To better illustrate these concepts, let’s put them to use on an actual
problem.

4
 Example 1. Arnaud and Bibin are playing the following game: starting at the number
1 < n ≤ 1000, they alternate turns to perform operations. Arnaud (who starts) may either
divide the number by 2 if it is even or add 4 (whether it be even or odd), and Bibin may
either multiply the number by 2 if it is odd or take away 2 (whether it be even or odd).
Arnaud wins if the number is 1 or 0 and Bibin wins if it exceeds 1000 or if nobody has
won after 100 turns for both sides. Who has a winning strategy?

Solution. Firstly, we note that the game is finite by definition, as if it goes on too long
then Bibin will just win. Also, the game is not symmetric, so we will be talking in terms
of A-winning and B-winning.
We start by identifying the end-states. If the number is equal to 1 or 0 then this will be an
end-state in which Arnaud wins; if it is greater than 1000 then this will be an end-state in
which Bibin wins. How much information is in a state, anyway? For a start, the number
is important, as well as whose turn it is to move next. However, we should also not forget
to keep track of how many turns have elapsed, since this is also important information
for this game, due to Bibin’s second winning condition.
Now, we can work backwards from these end-states to identify some states that are either
A- or B-winning. For a start, we quickly see that if the number is 2 and less than 200
turns have elapsed then the state is always A-winning. This is because if it is Arnaud’s
turn, he will just divide by 2 and on the other hand if it is Bibin’s turn, he is forced
to take away 2. Similarly, if the starting number is odd and greater than 500, and it is
Bibin’s turn, he is winning. In the former case, the notion of Bibin being forced to make
a possibly detrimental move is quite interesting, so let’s investigate it further.
If at the start of Bibin’s turn the number is even, then he has no choice but to take away
2. The number is still even, so Arnaud has the choice between dividing by 2 or adding
4. If dividing by 2 gave an odd number then Bibin could just multiply by 2 and Arnaud
would have just lost a turn. If it gives an even number, however, then Bibin is again
forced to take away 2 and Arnaud maintains what we could call "control" of the game.
Suppose that dividing by 2 gives an odd number. In this case, Arnaud can just add 4;
Bibin is forced to take away 2 and now dividing by 2 will give an even number instead.
So we see that, if at the start of Arnaud’s turn he has an even number 2x, he can force a
reduction in two ways:
• If x is even then he simply divides by 2; Bibin must then take away 2 and it will be
Arnaud’s turn again and he will have x − 2, which is even, to operate on.
• If x is odd then he adds 4; Bibin must then take away 2. Now he divides by 2,
giving Bibin x + 1 which is even and Bibin must take away 2, giving Arnaud x − 1,
which is even, to operate on.
Arnaud therefore uses at most 4 turns to at least halve the number. This means Arnaud
ever has an even number at the start of his turn and it is less than 998, then he nearly
always has a winning strategy, since he can get to 0 or 1 in at most 40 moves (since 1000
is less than 210 ). This gives us a winning property for Arnaud: have an even number at

5
the start of his turn, as long as it is not 998, and have enough turns remaining to get
down to 0.
This means that Bibin should avoid giving Arnaud an even number at all costs. However,
we quickly notice that if Arnaud has an odd number at some point, Bibin can easily
ensure he is forced to stay on odd numbers. Arnaud must add 4 on his turn, and Bibin
can simply take away 2 on his own turn; as a result, Arnaud will just have the next biggest
odd number. Arnaud has no viable method to reduce the number and so Bibin will either
win because the number exceeds 1000 or win because 200 turns elapse. So it turns out the
winning property for Bibin is just give Arnaud an odd number at the start of his turn.
So now the game is as good as solved: if n is even and not equal to 998, then Arnaud wins;
if n is odd then Bibin wins. The only remaining case is n = 998 but we notice quickly
that Arnaud will divide by 2 (since adding 4 loses instantly) and Bibin can just multiply
by 2 to consume two turns for free; he can just repeat this indefinitely to win.

Here, you see the usefulness of winning properties: whilst Bibin’s strategy is very easy
to explicitly describe in terms of states, it is much more difficult to describe exactly
how Arnaud would win starting at something like "624, Bibin’s turn, 143 turns elapsed".
However, thanks to winning properties, we can greatly simplify situations by boiling them
down to specific properties of the state; in this case, the parity of the number is the most
important thing to look at.
Let’s go into another example, this time symmetric.
Example 2. In this problem x, y, z are positive integers; w is a nonnegative integer.
Anaëlle and Barbara have two Cremeschnittes3 , with one dessert weighing x grams and
the other dessert weighing y grams. They then proceed to eat the Cremeschnittes in the
following manner: first, Anaëlle eats z grams from a dessert of his choice and a quantity
w less than or equal to z2 grams from the other dessert. Then Barbara does likewise, eating
firstly from a dessert (again, she can choose which one) and then a quantity less than or
equal to half that from the other dessert.
• If the person who takes the last bite is the winner, determine the winner in function
of x, y.
• If the person who takes the last bite is the loser, determine the winner in function
of x, y.
In this game, a state is simply x, y and whose turn it is to move. Since the game is
symmetric, we prefer to use the notion of 1- and 2-winning this time. For both cases,
the end states are just when (x, y) = (0, 0); the difference is that in the first case the
person who has just played will be the winner whereas in the second case they would have
lost.
3
A Slovenian cream cake, considered a local speciality in the region around Lake Bled.

6
Solution. Let’s start by analysing the first case. Working backwards from the end-state,
we see that the state immediately preceding it has to be of the form (a, b) where WLOG
2b ≤ a. A state like this is clearly 1-winning since the person whose turn it is can
immediately finish both cakes and win. Now the question is: what kind of state could
possibly be 2-winning? In what kind of situation are you forced to make a move which,
no matter what, hands the other person a winning position?
For a start, we know that (1, 0) is 1-winning. This means that (1, 1) should be 2-winning,
since the only possible move in this state is to finish one of the two cakes, giving your
opponent (1, 0) and immediate victory. (2, 0) and (2, 1) are also 1-winning as described
above, and so (2, 2) is 2-winning since any move you make gives your opponent a 1-
winning state. Since being able to reach a 2-winning state means you are 1-winning, this
further implies that any state of the form (a + 1, b + 1) or (a + 2, b + 2) where 2b ≤ a is
1-winning. So, for example, (3, 2) is 1-winning and so (3, 3) must be 2-winning, since you
can only reach (3, 2); (3, 1); (3, 0); (2, 1) and (2, 0), all of which are 1-winning. Now, we
could continue to bash small cases like this indefinitely, but now we have a basic grasp of
what is going on, we should try and find a winning property.
One pattern that seems to have emerged is that having (x, x) at the end of your turn
appears to be a winning property, since (1, 1), (2, 2) and (3, 3) are all 2-winning, and the
end-state (0, 0) can also be said to be 2-winning in the sense that the person who just
played has won. Let’s see if we can prove this. Suppose your opponent has (x, x) at the
start of their turn. For a start, they can’t possibly reduce it to some state of the form
(y, y), as there is no way for them to eat an equal amount from both cakes. Furthermore,
whatever move they make you can simply make a "complementary" move that brings it
back to this winning property: if they eat z from one dessert and w from the other then
you can simply eat w from the former and z from the latter to again have some (y, y) at
the end of your turn. Since they can never win when starting their turn on a state of this
kind, and the game is finite, you will eventually have (0, 0) at the end of your turn and
you will have won. So (x, x) is always 2-winning.
However, now the problem is easily finished. Remember that being able to reach a 2-
winning state means you are 1-winning. From any state (x, y) where x ̸= y, you can
simply eat from the larger cake to reduce it to the same size as the other one, and you
will have reached a 2-winning state. So this means that all states of the form (x, y) where
x ̸= y must be 1-winning, and so Anaëlle is winning if and only if the two cakes are not
of equal size in the initial state. If they are not, then she can reach the win con; if they
are, then Barbara can do so instead.
The second case is left to the reader to try, with the following hint: prove that (1, 1) and
(2, 2) are 1-winning but (3, 3) is 2-winning; use the latter to find a winning property and
finish. The winning strategy is remarkably similar to that from the first case, given that
the objective has now been completely inverted.

This example showcases two important facets of symmetric games: firstly, that it is
much easier to find a 1-winning state from a 2-winning state than vice-versa (a 1-winning

7
state is simply characterised as one from which you can reach some 2-winning state but
a 2-winning state is one from which you can reach only 1-winning states. Secondly, the
symmetry is often very useful for finding winning properties and winning strategies. Using
symmetry in this fashion will be the main focus of the next section, but before that, let
us look at one last example.
Example 3 (IMO Shortlist 2005, C5). Five identical empty buckets of 2-litre capacity
stand at the vertices of a regular pentagon. Cinderella and her wicked Stepmother go
through a sequence of rounds: At the beginning of every round the Stepmother takes one
litre of water from the nearby river and distributes it arbitrarily over the five buckets.
Then Cinderella chooses a pair of neighbouring buckets, empties them into the river, and
puts them back. Then the next round begins. The Stepmother’s goal is to make one of
these buckets overflow. Cinderella’s goal is to prevent this. Can the wicked Stepmother
enforce a bucket overflow?
You know the drill by now. A state is characterised by five real numbers (the quantities
of water in each bucket) as well as whose turn it is to move. The game is not symmetrical,
so we return to the notions of A- and B-winning; here let us take the Stepmother as A
since she moves first. An end-state in which the Stepmother wins is simply one in which
one of the numbers is greater than 2. There is no real end-state for Cinderella; in this
example she simply wins if the Stepmother doesn’t.

Solution. Working backwards, if one of the numbers is greater than 1 at the start of the
Stepmother’s turn, then she is winning. Moving back one further step, Cinderella must
have two non-consecutive numbers that are both greater than 1 at the start of her turn,
as otherwise she would just get rid of all the numbers greater than 1 during her turn. If
we say the numbers are B1 , B2 , . . . B5 then two non-consecutive numbers are always of
the form Bi and Bi+2 (taking indices modulo 5). So having such a pair of numbers both
be greater than 1 at the start of the Stepmother’s turn is both a necessary and sufficient
condition for the Stepmother to win. However, if you play around with the problem a
bit, you will soon realise that Cinderella seems to be the one who wins, so we want a
winning property for her instead; one viable winning property would be if she can keep
the quantity Bi + Bi+2 less than or equal to 2 for all i at the start of her turn.
However, the issue with a winning property like this is that we cannot prove that it
can be "maintained": imagine all the numbers were 1. No matter which two Cinderella
resets to 0, the Stepmother can make some Bi = Bi+2 = 1.5 at the end of her turn,
which means Cinderella would no longer have her winning property. What we want is a
stronger winning property, and in particular a winning property which we can show can
be maintained in the sense that if it is true at the start of a given turn, Cinderella can
play in some way such that no matter how the Stepmother plays, she still has the winning
property two turns later.
Of course, there is a reason why this problem is an IMO Shortlist C5, and that is because
the winning property is not obvious at first glance. However, it is not overtly convoluted
either and after a little practice you will be more than capable of coming up with it. The

8
winning property we will use will simply be if at the end of Cinderella’s turn, Bi +Bi+2 ≤ 1
for all i. Clearly, this is a sufficient but not necessary winning property, but we did remark
earlier that we would perhaps need something stronger so that it could be maintained.
Suppose at the end of Cinderella’s turn, the winning property is satisfied. We know she has
just emptied two of the buckets, so WLOG B4 = B5 = 0. Furthermore, this means B1 +
B3 ≤ 1 and B2 ≤ 1. After the Stepmother’s turn, we therefore have B1 +B3 +B4 +B5 ≤ 2.
Hence we either have that B5 + B3 ≤ 1 or B4 + B1 ≤ 1. Without loss of generality4 let us
say B5 + B3 ≤ 1. Then, Cinderella empties B1 and B2 . Now observe that the state is still
a winning property for her, since B4 ≤ 1 and B5 + B3 ≤ 1. Now we are done, because the
initial state satisfies this winning property and we have shown the winning property can
be maintained.

The big lesson to take away from this example is that you will often have several viable
winning properties that you can use, some of which are stronger than others in the sense
that they are sufficient but not necessary. However, if you want to prove that the winning
property can be preserved from turn to turn, sometimes you need to make a stronger
supposition. Here, the fact that the stronger winning property was true before implies
Cinderella can keep it true after; the weaker winning property mentioned before does not
have this property where it can imply itself in this inductive manner. Finding the right
winning property is the name of the game for this type of problem, and only practice
will develop your intuition, which will improve your chances of finding the right winning
property.
Now we look at one last example which illustrates a particularly powerful idea: how to
combine what we know about states along with proofs by absurdity.

2.2 Chomping our way to a contradiction.

Example 4. Julia has once against terrorised the SMO-camp with a full menu of vegan
food, but Annalena is determined to cook Pouletflügelu5 for the young contestants. She
challenges Julia to the following contest: they take a standard, 5 × 4 Swiss chocolate bar,
and take turns eating a square of chocolate as well as all the squares not yet consumed to
the right and below it. The loser is the one who eats the top-left square of chocolate; the
winner gets to decide the menu. Prove that if Annalena plays perfectly, the children will
be feasting on chicken wings that night.6
This problem is different to those seen before in that we are given specific values rather
than m × n. This is just a red herring, however, as if you test small cases you will begin
to notice that Annalena always seems to win, except for the extremal case where the
chocolate bar is a single square. Trying to prove a winning strategy exists for our case is
4
It is not obvious why we can drop a WLOG here, but think about symmetry around B2 if you are
not convinced.
5
If you think this is a spelling mistake, you are not cultured enough.
6
Of course, the vegans are welcome to enjoy fried broccoli.

9
 Figure 1: An example of a horror story in which Julia wins.

far less doable, however. Induction seems tempting here, but there is an even better tool
at our disposal: a proof by contradiction.

Solution. What if we were to suppose by absurdity that Julia had the winning strategy?
Funnily enough, this simple step allows us to nuke the problem with what we already
know about 1-winning and 2-winning states.
Suppose that the initial state is 2-winning. Recall what we already know: 1-winning is
much easier to prove than 2-winning, simply because:
• For a state to be 1-winning, you simply need to be able to play a move that leads
to a 2-winning state.
• For a state to be 2-winning, you need that every single move leads to a 1-winning
state.
So for the initial state, we need that every single state reachable after 1 move be 1-winning.
However, if this were to be true, there is a very simple contradiction, since Annalena has
one great zwischenzug of a move she can play, which is just to eat the bottom-right square.
Now, by our supposition, the state is now 1-winning, meaning Julia can make a move to
a 2-winning state. However, whatever move it is, Annalena could have made it herself
because the set of accessible states has not changed at all- eating the bottom-right square
does not allow you to get to any states you could not previously already attain. This
means there is a 2-winning state you can access from the initial state, contradiction.

This notion of having a "useless" move available to you is extremely powerful, and allows
you to immediately conclude that some states are 1-winning.

Definition 2.7 (Do-Nothing Move). In a symmetric game, a move from state α to

state β is called a do-nothing move if all possible moves from state β lead to states
that would have been directly accessible from α already, switching whose turn it is.

An example of a do-nothing move is a move that literally does nothing, e.g. passing or
a move that makes a change to the game state that would have happened on the other
players following move regardless.
If in a symmetric game there is a do-nothing move from a state α, then α is not 2-
winning.

10
Proof. Assume the state α is 2-winning. It follows that all states accessible from α are
1-winning, in. particular the state β reached after the do-nothing move. By definition, all
moves from β are accessible from α already and are therefore 1-winning. It follows that
β is 2-winning, a contradiction.

As an immediate corollary, if the game does not allow draws then the α is in fact 1-
winning. The two fundamental properties of 1-winning and 2-winning states discussed
above can be used in many different ways, most often for a proof by contradiction.

3 Symmetry: a man, a plan, a canal, Panama!

In Example 2 from the previous section, we saw that a symmetric strategy could be
applied in the game where you play a move that complements or mirrors that of your
opponent somehow in order to preserve a winning property. This idea comes up very
often in symmetric games, so let us see a few more classic examples of it.

3.1 Whatever you can do, I can do better

Example 5. Tanish and Raphi play the following game: There are n counters on a table.
They take turns picking up anywhere from 1 to k ≥ 2 counters, with Tanish starting first.
The person who picks up the last counter loses. Determine, in function of n, who has a
winning strategy.

Solution. This is an extremely famous riddle, and you have probably heard it in some
form before. The solution, of course, is to have the number of counters be 1 mod k + 1
at the end of your turn. This way, whatever move your opponent makes, you make the
complementary move so that between you, k + 1 counters were removed off the table.
Eventually, there will be 1 counter left on the table that your opponent is forced to pick
up. It follows that Tanish always wins unless n is 1 mod k + 1, in which case Raphi wins
instead.

Sometimes, however, the winning property can be a lot more subtle than this. In the
following example, there isn’t really even a notion of a winning property but rather just
brutally using symmetry to find a winning strategy.
Example 6. Marco and Valentin play the following game on a n × n (n ≥ 3) chessboard:
they take turn playing down 3 × 1 rectangles on the board such that the rectangles cover
exactly three squares of the chessboard that were not previously covered by some move.
The first player with no legal move loses. If Marco moves first, determine who has a
winning strategy.
It seems a bit difficult to enunciate a winning property here. Clearly, you want to be
able to make a move, but the question is what kind of winning property could describe
this. Ideas that spring to mind include labelling the squares with coordinates and trying
to create some kind of variable that encapsulates the fact that you have three squares

11
next to each other that are all empty so that you can play a move. For example, if one
person can ensure that there is an empty square with three empty neighbours at the start
of their turn, then they will always have a viable move. However, what if you were to
always make a move that literally mirrors that of your opponent?

Solution. Consider the case where n is even first. Suppose that every time Marco makes
a move, Valentin decides to make the same move but where the rectangle is rotated 180
degrees about the centre of the board. The very fact that Marco is legally able to make a
move implies that Valentin will always be able to make one, because due to the symmetry
in how they are placing down their rectangles if Marco makes his move then Valentin will
always have his rotated move available to him. This means, as the game is finite, Valentin
must be winning.
Now consider the case where n is odd. Now the centre of the board is a square. Suppose
Marco plays his first rectangle so that it is centred on the central square as well. Now, for
every move Valentin makes, he can make the rotated move and by the same reasoning, it
is now Marco that is winning.

A semanticist could point out here that the move does not literally mirror that of the
opponent and indeed trying to apply a strategy where you play a move that is the reflection
of your opponent’s move over some line will not work because there are some moves
where the mirrored options intersects with the original move and so will not always be
playable.
Another utility for symmetry can be when it allows you to keep the initial state of the
problem unchanged, which allows you to inductively prove that someone who is winning
in a small case is winning in a larger case.

3.2 Induction for the winduction

Example 7. Jakob and Luka are standing at two separate whiteboards on which the
numbers 1, 2, . . . , n ≥ 3 are written in ascending order. They then take it turns, Jakob
first, to swap two of the numbers on their board. After k turns (total, not each) they
compare the first number in the sequence, then the second, and so forth up to the nth
number. For every instance your number is greater than your opponent’s in some position,
you get a point; whoever has more points wins. Find, in function of n and k who has a
winning strategy or if the game is a draw.
One thing we notice is that having the last move is quite helpful. Let us therefore consider
the cases k even (Luka moving last) and k odd (Jakob moving last) separately.

Solution. The first thing we notice when considering symmetric strategies is that Luka
can always make the exact same move Jakob did if he wanted. This strategy always
ensures a tie in both cases, as if Luka moves last they will have the same sequences and
if Jakob does the sequences will just differ by a single swap, but this just give a single
point to each of them, so it is still a draw. So Jakob does not have a winning strategy, as

12
Luka can always force a draw. The question is now whether Luka can play for the win,
or whether Jakob can also force a draw.
What happens if Jakob now copies Luka? The issue here is that he has to make an initial
move, but as we saw before, just making a single move means both parties are tied. After
this point, if he copies Luka’s move (in terms of the positions of the numbers swapped,
not the numbers themselves) then the sequences will be identical after his move apart
from the single initial swap. This means, if Jakob has the last move, he can force a draw.
This just leaves us with the case where Luka has the last move.
Unfortunately for Jakob, this is the one case where Luka can play for the win. Luka
simply copies his move for the first k − 2 turns. After Jakob’s final move, Luka can
always find a move that gives him two points and Jakob just one. The reader is invited to
convince themselves of this fact more rigorously if they wish. The key here is that Luka
has essentially reduced the game to the version where they have a single move each, and
since he wins in this case he can always win as long as he moves last. The value of n has
no effect on who the winner is.

These three examples together give just a glimpse as to how strong symmetry can be in a
games problem. Of course, other techniques from combinatorics are also applicable in this
kind of problem - for example, constructing a smart invariant that reflects who is winning
(a winning property is technically an invariant!) or an intelligent coloration that gives
you useful information you can then use to hone your approach; a clever induction or a
smart parity argument. The only real theory that is specific to combinatorial games is
the study of states and winning strategies seen in the previous section. However, you can
find some very famous examples of combinatorial games that have been heavily studied
in the appendix.
The last example uses induction in order to simplify the problem. Induction also has one
other main utility: proving that some set of states are either 1-winning or 2-winning. The
most common way of doing this is to prove that your set is "bipartite":

Definition 3.1 (Recurring Set of States). A subset S of the states of a symmetric

game is called recurrent if for every α ∈ S there is a move leading to a state β, such
that β is not an end-state and every move from β leads back to a state in S.

Let S be a recurrent set of states in a finite symmetric game. If some element of S is

1-winning then they are all 1-winning.
The proof of this is simple: if you are in a state α of S and it is your turn to move, then
a winning strategy is to always move to the associated state β. Your opponent will then
have to move back to an element of S. Since the game is finite, you will eventually end up
at the element which is known to be 1-winning and from here there is a winning sequence
of moves.

13
4 Avoiding common pitfalls
There are several logical fallacies or common errors you can make whilst solving a problem
of this kind. Here is a list (certainly not exhaustive) of the most common errors you should
avoid.
• Forget that the player whose turn it is to play is a very important part
of the game state in an asymmetric game. In chess, for example, it is very
possible to have a position that is winning for both Black and White based on whose
turn it is to move, or to have a position that is winning for White no matter whether
it is White’s turn or Black’s turn.
• Forget to prove a game is finite. If it is not trivial (and even if it is, why not?)
take the time to prove that the game must end, or perhaps even realise that it can
go on forever and there is also the possibility of a tie.
• Assume that a state is 2-winning if you can go to a 1-winning state. This
is not true! A state is 2-winning if you can only go to 1-winning state. You have to
be sure there are no 2-winning states you can attain.
• Assume that if the only way to go between two states is in an even
number of moves, then both moves are winning for the same player; or
another logical fallacy of this kind. This kind of logical fallacy is very easy to
make but it is usually much more difficult to characterise 1- and 2-winning moves
than you think. For example, suppose we have a game where you have a positive
integer and you can take away either of the two smallest divisors of that number
as your move; the player who leaves 0 at the end of his move wins. Clearly, 4 is
2-winning and 3 and 2 are 1-winning. Nevertheless, the only way to go from 4 to 2
is with two moves; this does not imply that 4 should also be 1-winning.
• Assume that a state is 1-winning if all the states you can attain from it
are 2-winning. Again, you just need to be able to attain a single 2-winning state;
not all of the states you can reach have to be 2-winning.
• Assume taking a move back from a 1-winning state gives only/at least
one 2-winning state. A 1-winning state can be preceded by only 1-winning states;
all this means is that with good gameplay you would never end up at this state.
However, you are allowed to say that 2-winning states are only preceded by 1-
winning states by definition.
• Assume that just because a game is not finite, there must be some tied
state. You can easily have a game which can theoretically go on forever but where
one player is winning. For example, imagine the (very bizarre) game where on your
turn you can either pass, or win. Of course the game can go on forever but it is also
clearly 1-winning for every state.
• Assume that if there is a move that does nothing, the state is always tied.
Having a move that does nothing just means that the state can’t be 2-winning, but

14
 it can still be 1-winning.
• Prove that a state is tied by showing one player can force a tie. This
just proves that the game is not winning for the other player, but it could still be
winning for the player who has the ability to force a draw. For example, in example
6, in the case where Jakob moves last it is not enough to prove that Luka can force
a draw to conclude that the game is drawn, even if it seems obvious that moving
last is advantageous. You must also prove Jakob can force a tie.
• Say that if you have a condition true for the end-state such that you can
always move from a state with your condition to a state that does not
have the condition, then this condition gives a winning property. Who says
the states without your condition can’t be winning as well? Or that your opponent
has to play a move that gives you back the condition?
• Assume a certain kind of move is detrimental and will not be played in
a perfect strategy. In the very first example, even if Arnaud wants to reduce the
number, it is sometimes in his favour to increase it temporarily. It would be wrong
to assume that the possibility of adding 4 is useless for him because it takes you
further away from 0 and 1. Sometimes you must go back to go forward...

15
A Matchsticks, Bowling Pins and Chocolate Bars
A.1 Nim
Nim is a game in which you have several groups of matchsticks on a table; different groups
can be of different sizes. On a player’s turn they may remove any number of matchsticks
a single pile. There are two main variants: either the person taking the last matchstick
wins, or the person taking the last matchstick loses. Examples 3 and 5 are both specific
cases of Nim.
To figure out who is winning in Nim, we use a very specific operation on the sizes of
the piles, called the bitwise xor operation, also referred to as the Nim-sum. To perform
this operation, one takes the sizes of each group of matchsticks and adds them in binary
whilst not carrying any digits forward. In other words, you consider all the different binary
strings representing the different groups. Then, to get the units digit of your sum, you
take the parity of the number of times 1 is a units digit for the strings you are summing
together. You repeat this for the twos digit, the fours digit and so on until you get to the
highest power. For example, if you were to sum 3, 4, and 5, you would be summing 011,
100 and 101. 1 is in the units digit twice, so the sum has a units digit of 0. 1 is in the
twos digit once, so the sum has a twos digit of 1. Finally, 1 is in the fours digit twice, so
the sum has a fours digit of 0. The Nim-sum is therefore 010, or 2.
If the winner is the person taking the last matchstick, then the winning strategy is to
keep the Nim-sum at 0 at the end of your turn. If the Nim-sum is not already 0 there is
always a move that reduces it to 0; if it is already 0 then there is no move that will keep
it at 0; and in the end-state the Nim-sum is indeed 0. If the loser is the person taking
the last matchstick, then the winning strategy is the same except when your next move
would be to only leave heaps of size 1. Whereas before you would leave an even number
of heaps of size 1 at the end of your turn (meaning that since all subsequent moves are
just "remove a heap", you get the last move) you simply leave an odd number of heaps
of size 1 at the end of your turn (meaning you now get the second-to-last move for the
same reason).

A.2 Chomp
Chomp, or Example 4 generalised, is a game in which you initially have an m×n chocolate
bar on a table. On a player’s turn they must choose a square of remaining chocolate and
consume it along with any square below or to the right of it still remaining. The loser is
the one who eats the top-left square of chocolate.
Chomp is always won by the first player unless (m, n) = 1. The argument behind this
is particularly elegant in that we do not know what the winning strategy is, but simply
because that it must exist. Suppose that the second player had a winning strategy (so
that the initial state is 2-winning; and whatever move you make must lead to a 1-winning
state). In this case, the first player can eat the single bottom-right square of chocolate on
their turn. This means that the second player can now make a move that will supposedly

16
be part of a winning strategy, and leave the game in a 2-winning state. However, the first
player could just have made this move themself to reach a 2-winning state, meaning the
initial state is also 1-winning. This is a contradiction, and so the initial state cannot be
2-winning.
Chomp can be generalised to any number of dimensions; by the same argument, as long
as there is more than a single unit of chocolate, the first player is winning.

A.3 Kayles
In the game of Kayles, you have a row of n bowling pins side by side. On a players turn,
they may either remove one pins or two pins that were initially adjacent. Again, there
are two main variants: the player who knocks down the last pin loses and the player who
knocks down the last pin wins. In the variant where the last pin wins, a simple symmetry
strategy ensures that the first player will always win: simply remove one or two pins from
the middle so that there are two groups of equal size, and then replicate your opponent’s
moves. The last-pin-loser variant was solved by Sibert and Conway, but is outside the
span of this lesson.

A.4 Cram
Cram is played on an m×n chessboard with an even number of squares; players take turns
placing dominoes on the board that cover two squares and do not overlap with existing
dominoes and the player that cannot move first loses. Cram is always won by the first
person by a symmetric strategy like that seen in Example 6.

A.5 Notakto
Notakto is a variant of tic-tac-toe that works as follows: two players play tic-tac-toe on
one or several boards at once; but instead of placing Os and Xs, both players place Xs.
Once a board has three in a row on it, it is said to be dead and no more moves can be
played there. The player who kills the last board loses.
Notakto on one board is easily won by the first player; on two boards, the second player
wins. Using induction, you can show that the first player wins for an odd number of
boards and the second player for an even number of boards.

17