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. Twoplayers
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 Cl. Since Cl does not pass through
the center, it follows that Cl and C2 cannot intersect (why?) And so if Cl
fit on the table, so does C2, as the board was symmetricup 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 nurnbers thus far), and Alice goes first. VVhenall squares
are filled, the square in each row with the largest number is colored black.
Alice wins if she can then draw a struight 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 luain 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 utunber in an unmarked square, And if
she picks an unmarked square, he writes a lower number in a marked square.
Question of 19played Oil / board bf/ Alit"
and os firgl, On (1plavetB move, "/,uht plaeg
on S on (10('8not have at/,X ort it, arzd they algo
place an S on; (Ibooeand/or to the of that gquare which
does hoi, an X on,it, That is, any (g,t) with8 i and t ? j
have an X (1180 an X put in it Theperson who
X loses, Determine who hag (1winninq g/,ratcgy.
key ig the top right, is a 'throwaway' rrjove. In other
the liighly related gajrjc of 'chnrrjp%which ig the garne except
011liii m k il board jniJJi18the top right piece. Now if first player
n Aliee c;[Link], play tho lwinning champ strategy for
ch01)ii •ee top right piece will .ijrjjrjediaf,elyget an X. If first player
'lice gillij)ly plays her first jrjovc for chomp in •thetop right

that 'difficult,game to analyze, a,nd we do not know 'Whowins in

2, PROBLEMS
2.1. Warmup Brobierns.
(1) (The matchstick: Ååme)AJå(teand Bob play a game with a pile of 10
With Alice moving first. On each players turn, they must
vretnovObetween å,nd matches from the pile. The person who
empties the pile wins,The initial pile has 10 matches. Figure out a
winning strategy fovi)iie of the players.
What, if int$teacl, Player who ernpties the pile loses?
(2) Alic,qy
and play game in which they take turns removing stones
frorp a be/p initially has stones. The number of stones re-
moved aUeaclilInrn be one less than a prime numbere The
j8 the who Cakesthe last stone. Alice plays first. Prove
that tjjere tare infinitely many n such that Bob has a winning strat-
egyj (For 17?then Alice might take 6 leaving Il; Bob
jnjght fake jcaving J(); Alice can take the remaining stones to
win;)
(3) Alice Bob play game in which the first player places a king on
ejnpf,y 88 chessboard, and then, starting with the second players
they alternate jnoving (he king (in accord with the rules of chess)
co square thal has been previously occupied. The plAverwho
cannot loseti, WIiiclJplayer has winningstrategy? What
about; b 5 board?
(4) Alice Bob alternatc writing in the entries of a 3 x 3 tuatrix. Alice
and wgåtesa l, and 1301)only writes a O, into some
cell of' the Aftcg•9 the gaxneis over, and Alice
 wins if the detertninant is non-zero. Deterrnine whether Alice has a
winning strategvs
(5) Alice and Bob play a garne as follows. They start with a row of 50
coins, of various values. The playrs 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 tnuch
money as Bob. Find an exatnple where Bob can tnake tnore tnoney
then Alice if there are 51 coins.
(6) Let n be a positive integer. Alice and Bob play a ganre with a set
of 2n cards ntnnbere€lfrotn I to '2n. The (leek is randotnly shuffled
and n cards are dealt to each of the plawrs. Beginning with Alice,
the players take turns discarding one of their retnaining cards and
announcing its nurnber. The garne ends as soon as the stun of the
nutnbenson the discardedcards is divisibleby 2n + I and the last
player to discard wins the garne. Prow that Bob has a winning
stratevy.
(7) Two playens play a gatne by starting with the integer 2020, and
taking turns replacing the current integer „Vwith either IN/ 2J or
N -- 1. The playr who writes down 0 wins. Who has a winning
stratekY?
2.2. Xledium.
(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 allowedto 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
(3) (IMO Shortlist 2017) Let p 2 2 be a prime ntunber. Eduardo and
Fernando play the following game making moves alternately: in each
move, the current player chooses an index i in the set {I, 2,
that was not chosen before by either of the two players and then
chooses an element ai from the set {O,1, 2, 3, 4, 5, 6, 7, S, 9}. Eduardo
has the first move. The game ends after all the indices have been
chosen -Then the following number is computed:

M + all() + (1210
2+ + ap-110P- 1 Eat.10'.
 The goal of Eduardo is to make M divisible by p, and the goal of
Fernando is to prevent th1S,
Prove that Eduardo has a winning strategy.
(4) There are 2000 cotnponenCsin a circuit, every two of which were
initially joined by a wire. The [Link] Pctya cut the
wires one after another. Vasya, who starts, cuts onc 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-Toeon an infinite grid, where
soméOnewins if they get 5 consecutiveX 's or o's in a row. Prove
'that no-ong hås a winning strategy.
(6) A and B play a game, given an integer N, A writes (lowri1 first,
then every layer sees the last number written and if it is n then
his turrl iVegn+ or 2n, but his number cannot be bigger than
N. The player who WyitesN wins. For which values of IV does B
win?

2.3. Hard.
(1) (USANIC)1999)Alice ånd piay a game, Initiallyjlthere is a row
of unfilled i)oxes. W!th/\lice, they take turns filling in
either S or () in' ari tinf1Jlec) player who first creates three
consecuCive bokes spellipU (it' there is no such player, they
tie). For,wbich fail ÅliC9/ •Wit)?For which does Bob
guarantee a Will?!
(2) Fix an integer), i and Banana/ play
the following/

Consider , each prune

io row
A players picking placing pebble on
adjacent vestrictioo pebble be placed
Cignes, two takiug
Alice, firs( player who guilijot, ixn@kea
pot positive integer who winning