WINTER CAMP 2020: GAME THEORY

JACOB TSIMERMAN

1. Games
Two player games are very common. A winning strategy for one of the
two players (Alice) is a set of rules to follow, such that no matter what the
other player does, if Alice follows the rules she will win the game. It is a fact
that if Alice and Bob play a game which ends in a finite amount of time,
and one of the two players always wins, then there is a winning strategy for
either Alice or Bob. This is by no means a trivial remark!
Here are a a few common tricks and strategies one can use when analyzing
games.

1.1. Symmetry.
Question 1.1. There is a table with a square top of radius 10. Two players
take turn putting a dollar coin of radius 1 on the table. The player who
cannot do so loses the game. Show that the first player can always win.
Solution: The first player places her first coin in the middle of the table.
On every subsequent move, the first player places their coin C2 symmetri-
cally to the second players previous coin C1 . Since C1 does not pass through
the center, it follows that C1 and C2 cannot intersect (why?) And so if C1
fit on the table, so does C2 , as the board was symmetric up to that point.

1.2. Pairing.
Question 1.2 (USAMO 2004/4). Alice and Bob play a game on a 6 6 grid.
They take turns writing a number in an empty square of the grid (distinct
from all previous numbers thus far), and Alice goes first. When all squares
are filled, the square in each row with the largest number is colored black.
Alice wins if she can then draw a straight line (possibly diagonal) connecting
two opposite sides of the grid that stays entirely in black squares. Find, with
proof, a winning strategy for one of the players.
solution Consider the squares lying on the main diagonal, the diagonals
immediately above and below it, and the 2 corners. This consists of 3 squares
in each row. Mark all these squares. Bob can ensure that none of these are
ever colored black by always acting in the same row in Alice: if she picks a
marked square, he writes a higher number in an unmarked square. And if
she picks an unmarked square, he writes a lower number in a marked square.
1
2 JACOB TSIMERMAN

1.3. Strategy Stealing.

Question 1.3. The game of Chomp is played on an m × n board by Alice
and Bob as follows. Alice moves first. On a players move, they must place
an X on any square (i, j) which does not yet have an X on it, and they also
place an X on any square above and/or to the right of that square which
does not yet have an X on it. That is, any square (s, t) with s ≥ i and t ≥ j
which does not yet have an X also gets an X put in it. The person who
places the last X loses. Determine who has a winning strategy.
Solution The key is that the top right is a ‘throwaway’ move. In other
words, consider the highly related game of ‘champ’, which is the same except
its played on an m × n board minus the top right piece. Now if first player
wins in champ, then Alice can just play the winning champ strategy for
chomp, since the top right piece will immediately get an X. If first player
loses in champ, Alice simply plays her first move for chomp in the top right
and then plays the winning strategy for champ as the second player. Note
that champ is a difficult game to analyze, and we do not know who wins in
general!

2. Problems
2.1. Warmup Problems.
(1) (The matchstick game) Alice and Bob play a game with a pile of 10
matches, with Alice moving first. On each players turn, they must
remove between 1 and 3 matches from the pile. The person who
empties the pile wins.The initial pile has 10 matches. Figure out a
winning strategy for one of the players.
What if instead, the player who empties the pile loses?
(2) Alice and Bob play a game in which they take turns removing stones
from a heap that initially has n stones. The number of stones re-
moved at each turn must be one less than a prime number. The
winner is the player who takes the last stone. Alice plays first. Prove
that there are infinitely many n such that Bob has a winning strat-
egy. (For example, if n = 17, then Alice might take 6 leaving 11; Bob
might take 1 leaving 10; then Alice can take the remaining stones to
win.)
(3) Alice and Bob play a game in which the first player places a king on
an empty 88 chessboard, and then, starting with the second player,
they alternate moving the king (in accord with the rules of chess)
to a square that has not been previously occupied. The player who
cannot move loses. Which player has a winning strategy? What
about on a 5 × 5 board?
(4) Alice and Bob alternate writing in the entries of a 3×3 matrix. Alice
moves first, and only writes a 1, and Bob only writes a 0, into some
empty cell of the matrix. After 9 moves the game is over, and Alice
 WINTER CAMP 2020: GAME THEORY 3

wins if the determinant is non-zero. Determine whether Alice has a

winning strategy.
(5) Alice and Bob play a game as follows. They start with a row of 50
coins, of various values. The players alternate, and at each step they
pick either the first or last coin and take it. If Alice plays first, prove
that she can guarantee that she will end up with at least as much
money as Bob. Find an example where Bob can make more money
then Alice if there are 51 coins.
(6) Let n be a positive integer. Alice and Bob play a game with a set
of 2n cards numbered from 1 to 2n. The deck is randomly shuffled
and n cards are dealt to each of the players. Beginning with Alice,
the players take turns discarding one of their remaining cards and
announcing its number. The game ends as soon as the sum of the
numbers on the discarded cards is divisible by 2n + 1 and the last
player to discard wins the game. Prove that Bob has a winning
strategy.
(7) Two players play a game by starting with the integer 2020, and
taking turns replacing the current integer N with either bN/2c or
N − 1. The player who writes down 0 wins. Who has a winning
strategy?

2.2. Medium.
(1) Two players, Jacob and David, play a game in a convex polygon
with n ≥ 5 sides. On each turn, they draw a diagonal which does
not intersect any previously drawn diagonal. The player that creates
a quadrilateral (with no diagonal yet drawn) loses. If Jacob plays
first, for which n can he win?
(2) For a positive integer n, two players A and B play the following
game: Given a pile of N stones, the players alternate with A going
first. On a given turn, a plater is allowed to take either one stone,
or a prime number of stones, or kn stones for some positive integer
k. The winner is the one who takes the last stone. Assuming both
A and B play perfectly, for how many integers N does B win?
Can you find a bound N in terms of n for which A wins for all
s ≥ N?
(3) (IMO Shortlist 2017) Let p ≥ 2 be a prime number. Eduardo and
Fernando play the following game making moves alternately: in each
move, the current player chooses an index i in the set {1, 2, . . . , p−1}
that was not chosen before by either of the two players and then
chooses an element ai from the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Eduardo
has the first move. The game ends after all the indices have been
chosen .Then the following number is computed:
p−1
X
M = a0 + a1 10 + a2 102 + · · · + ap−1 10p−1 = ai .10i .
i=0
4 JACOB TSIMERMAN

The goal of Eduardo is to make M divisible by p, and the goal of

Fernando is to prevent this.
Prove that Eduardo has a winning strategy.
(4) There are 2000 components in a circuit, every two of which were
initially joined by a wire. The hooligans Vasya and Petya cut the
wires one after another. Vasya, who starts, cuts one wire on his turn,
while Petya cuts two or three. The hooligan who cuts the last wire
from some component loses. Who has the winning strategy?
(5) A and B play a version of Tic-Tac-Toe on an infinite grid, where
someone wins if they get 5 consecutive X’s or O’s in a row. Prove
that no-one has a winning strategy.
(6) A and B play a game, given an integer N , A writes down 1 first,
then every player sees the last number written and if it is n then in
his turn he writes n + 1 or 2n, but his number cannot be bigger than
N . The player who writes N wins. For which values of N does B
win?

2.3. Hard.
(1) (USAMO 1999) Alice and Bob play a game. Initially, there is a row
of n unfilled boxes. Starting with Alice, they take turns filling in
either S or O in an unfilled box. The player who first creates three
consecutive boxes spelling SOS wins (if there is no such player, they
tie). For which n can Alice guarantee a win? For which n does Bob
guarantee a win?
(2) Fix an integer k > 2. Two players, called Ana and Banana, play
the following game of numbers. Initially, some integer n ≥ k gets
written on the blackboard. Then they take moves in turn, with
Ana beginning. A player making a move erases the number m just
written on the blackboard and replaces it by some number m0 with
k ≤ m0 < m that is coprime to m. The first player who cannot move
anymore loses.
An integer n ≥ k is called good if Banana has a winning strategy
when the initial number is n, and bad otherwise.
Consider two integers n, n0 ≥ k with the property that each prime
number p ≤ k divides n if and only if it divides n0 . Prove that either
both n and n0 are good or both are bad.
(3) (IMO Shortlist 2014) Alice and Bob play the following game. To
start, Alice arranges the numbers 1, 2, . . . , n in some order in a row
and then Bob chooses one of the numbers and places a pebble on it.
A player’s turn consists of picking up and placing the pebble on an
adjacent number under the restriction that the pebble can be placed
on the number k at most k times. The two players alternate taking
turns beginning with Alice. The first player who cannot make a
move loses. For each positive integer n, determine who has a winning
strategy.
 WINTER CAMP 2020: GAME THEORY 5

(4) (RMM 2019) Alice and Bob play the following game. To start, Alice
arranges the numbers 1, 2, . . . , n in some order in a row and then Bob
chooses one of the numbers and places a pebble on it. A player’s turn
consists of picking up and placing the pebble on an adjacent number
under the restriction that the pebble can be placed on the number k
at most k times. The two players alternate taking turns beginning
with Alice. The first player who cannot make a move loses. For each
positive integer n, determine who has a winning strategy.
(5) (RMM 2018) Ann and Bob play a game on the edges of an infinite
square grid, playing in turns. Ann plays the first move. A move
consists of orienting any edge that has not yet been given an orien-
tation. Bob wins if at any point a cycle has been created. Does Bob
have a winning strategy?
(6) Tim and Allen play a game. They start with an empty set S. With
Tim going first and alternating, on each turn they pick a positive
integer greater than 1 which cannot be written as a sum of elements
in S (possibly with repetition), and add it to S. The player who
cannot move loses. Prove the game eventually ends, and determine
who has a winning strategy.