##### Document Text Contents

Page 1

Olympiad

Combinatorics

Pranav A. Sriram

August 2014

Page 2

Chapter 6: Counting in Two Ways 1

Copyright notices

All USAMO and USA Team Selection Test problems in this chapter

American Mathematics Competitions.

© Pranav A. Sriram. This document is copyrighted by Pranav A.

Sriram, and may not be reproduced in whole or part without

express written consent from the author.

About the Author

Pranav Sriram graduated from high school at The International

School Bangalore, India, and will be a Freshman at Stanford

University this Fall.

Page 127

Olympiad Combinatorics 30

mathematics and computer science, and uses techniques from

combinatorics, graph theory, field theory, probability and

linear algebra. Its applications range from file compression to

mining large scale web data. Coding theory is also the reason

your CDs often work even if they get scratched. While this

exercise asks for an existence proof, finding constructive

solutions to several similar problems remains an active

research area with high practical relevance.

13. Let F be a collection of k-element subsets of {1, 2, …, n} and let

x = |F|/n. Then there is always a set S of size at least

�

���/(���)

which does not completely contain any member of F.

14. [Another list coloring theorem]

Each vertex of an n-vertex graph G is assigned a list containing

at least k different colors. Furthermore, for any color c

appearing on the list of vertex v, c appears on the lists of at

most k/2e neighbors of v. Show that there exists a proper

coloring of the vertices of G such that each vertex is colored

with a color from its list.

15. [Due to Furedi and Khan]

Let F be a family of sets such that each set in F contains at

most n elements and each element belongs to at most m sets

in F. Show that it is possible to color the elements using at

most 1+(n–1)m colors such that no set in F is monochromatic.

16. [Due to Paul Erdos]

A set S of distinct integers is called sum-free if there does not

exist a triple {x, y, z} of integers in S such that x + y = z. Show

that for any set X of distinct integers, X has a sum-free subset

Y such that |Y| > |X|/3.

17. [IMO 2012, Problem 3]

The liar's guessing game is a game played between two

players A and B. The rules of the game depend on two positive

Page 128

Chapter 9: The Probabilistic Method

31

integers k and n which are known to both players.

A begins by choosing integers x and N with 1 ≤ x ≤ N. Player

A keeps x secret, and truthfully tells N to player B. Player B

now tries to obtain information about x by asking player A

questions as follows: each question consists of B specifying an

arbitrary set S of positive integers (possibly one specified in

some previous question), and asking A whether x belongs to S.

Player B may ask as many questions as he wishes. After each

question, player A must immediately answer it with yes or no,

but is allowed to lie as many times as she wants; the only

restriction is that, among any (k+1) consecutive answers, at

least one answer must be truthful.

After B has asked as many questions as he wants, he must

specify a set X of at most n positive integers. If x belongs to X,

then B wins; otherwise, he loses. Prove that:

1. If n ≥ 2

k

, then B can guarantee a win.

2. For all sufficiently large k, there exists an integer n ≥ 1.99

k

such that B cannot guarantee a win.

18. [Johnson-Lindenstrauss Lemma]

(i) Let X1, X2, …, Xd be d independent Gaussian random

variables. Let X = (X1, X2, …, Xd) be the d-dimensional

vector whose coordinates are X1, X2, …, Xd. Let k < d and let

X’ be the k-dimensional vector (X1, X2, …, Xk). Show that:

a) If α is a constant greater than 1,

Prob[ ||Xk|| ≥ α k/d ] ≤ exp(

�(�� � � ���)

�

)

b) If α is a constant smaller than than 1,

Prob[ ||Xk|| ≤ α k/d ] ≤ exp(

�(�� � � ���)

�

)

(ii) Part (i) says that the norm of a vector of independent

Page 254

Chapter 5: Combinatorial Games 19

written on the blackboard, and so on. The player who first

reaches a negative number loses the game. Prove that there

exist infinitely many values of t for which the first player has a

winning strategy for all pairs (a, b) with (a + b) = 2005.

8. [Rioplatense Math Olympiad 2010]

Alice and Bob play the following game. To start, Alice arranges

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.

9. [Russia 2007]

Two players take turns drawing diagonals in a regular (2n+1)-

gon (n > 1). It is forbidden to draw a diagonal that has already

been drawn or intersects an odd number of already drawn

diagonals. The player who has no legal move loses. Who has a

winning strategy?

10. [Indian Practice TST 2013]

A marker is placed at the origin of an integer lattice. Calvin

and Hobbes play the following game. Calvin starts the game

and each of them takes turns alternatively. At each turn, one

can choose two (not necessarily distinct) integers a and b,

neither of which was chosen earlier by any player and move

the marker by a units in the horizontal direction and b units in

the vertical direction. Hobbes wins if the marker is back at the

origin any time after the first turn. Determine whether Calvin

can prevent Hobbes from winning.

Note: A move in the horizontal direction by a positive quantity

will be towards the right, and by a negative quantity will be

towards the left (and similarly in the vertical case as well).

Page 255

Olympiad Combinatorics 20

11. [Based on South Korea 2009, Problem 5]

Consider an m × (m+1) grid of points, where each point is

joined by a line segment to is immediate neighbors (points

immediately to the left, right, above or below). A stone is

initially placed on one of the points in the bottom row. A and B

alternately move the stone along line segments, according to

the rule that no line segment may be used more than once.

The player unable to make a legal move loses. Determine

which player has a winning strategy.

12. [IMO Shortlist 1994, C6]

Two players play alternatively on an infinite square grid. The

first player puts an X in an empty cell and the second player

puts an O in an empty cell. The first player wins if he gets 11

adjacent X's in a line - horizontally, vertically or diagonally.

Show that the second player can always prevent the first

player from winning.

13. [Nim]

There are k heaps of stones, containing a1, a2 ak stones

respectively, where the ai A

and B play alternately as follows: in each turn, a player

chooses one non-empty heap and removes as many stones as

he or she wants. The person who takes the last stone wins.

Determine when each player has a winning strategy, and find

this winning strategy.

14. [The name of this problem would give the answer away]

There is one pile of N counters. A and B play alternately as

follows. In the first turn of the game, A may remove any

positive number of counters, but not the whole pile.

Thereafter, each player may remove at most twice the number

of counters his opponent took on the previous move. The

player who removes the last counter wins. Who has the

winning strategy?

Olympiad

Combinatorics

Pranav A. Sriram

August 2014

Page 2

Chapter 6: Counting in Two Ways 1

Copyright notices

All USAMO and USA Team Selection Test problems in this chapter

American Mathematics Competitions.

© Pranav A. Sriram. This document is copyrighted by Pranav A.

Sriram, and may not be reproduced in whole or part without

express written consent from the author.

About the Author

Pranav Sriram graduated from high school at The International

School Bangalore, India, and will be a Freshman at Stanford

University this Fall.

Page 127

Olympiad Combinatorics 30

mathematics and computer science, and uses techniques from

combinatorics, graph theory, field theory, probability and

linear algebra. Its applications range from file compression to

mining large scale web data. Coding theory is also the reason

your CDs often work even if they get scratched. While this

exercise asks for an existence proof, finding constructive

solutions to several similar problems remains an active

research area with high practical relevance.

13. Let F be a collection of k-element subsets of {1, 2, …, n} and let

x = |F|/n. Then there is always a set S of size at least

�

���/(���)

which does not completely contain any member of F.

14. [Another list coloring theorem]

Each vertex of an n-vertex graph G is assigned a list containing

at least k different colors. Furthermore, for any color c

appearing on the list of vertex v, c appears on the lists of at

most k/2e neighbors of v. Show that there exists a proper

coloring of the vertices of G such that each vertex is colored

with a color from its list.

15. [Due to Furedi and Khan]

Let F be a family of sets such that each set in F contains at

most n elements and each element belongs to at most m sets

in F. Show that it is possible to color the elements using at

most 1+(n–1)m colors such that no set in F is monochromatic.

16. [Due to Paul Erdos]

A set S of distinct integers is called sum-free if there does not

exist a triple {x, y, z} of integers in S such that x + y = z. Show

that for any set X of distinct integers, X has a sum-free subset

Y such that |Y| > |X|/3.

17. [IMO 2012, Problem 3]

The liar's guessing game is a game played between two

players A and B. The rules of the game depend on two positive

Page 128

Chapter 9: The Probabilistic Method

31

integers k and n which are known to both players.

A begins by choosing integers x and N with 1 ≤ x ≤ N. Player

A keeps x secret, and truthfully tells N to player B. Player B

now tries to obtain information about x by asking player A

questions as follows: each question consists of B specifying an

arbitrary set S of positive integers (possibly one specified in

some previous question), and asking A whether x belongs to S.

Player B may ask as many questions as he wishes. After each

question, player A must immediately answer it with yes or no,

but is allowed to lie as many times as she wants; the only

restriction is that, among any (k+1) consecutive answers, at

least one answer must be truthful.

After B has asked as many questions as he wants, he must

specify a set X of at most n positive integers. If x belongs to X,

then B wins; otherwise, he loses. Prove that:

1. If n ≥ 2

k

, then B can guarantee a win.

2. For all sufficiently large k, there exists an integer n ≥ 1.99

k

such that B cannot guarantee a win.

18. [Johnson-Lindenstrauss Lemma]

(i) Let X1, X2, …, Xd be d independent Gaussian random

variables. Let X = (X1, X2, …, Xd) be the d-dimensional

vector whose coordinates are X1, X2, …, Xd. Let k < d and let

X’ be the k-dimensional vector (X1, X2, …, Xk). Show that:

a) If α is a constant greater than 1,

Prob[ ||Xk|| ≥ α k/d ] ≤ exp(

�(�� � � ���)

�

)

b) If α is a constant smaller than than 1,

Prob[ ||Xk|| ≤ α k/d ] ≤ exp(

�(�� � � ���)

�

)

(ii) Part (i) says that the norm of a vector of independent

Page 254

Chapter 5: Combinatorial Games 19

written on the blackboard, and so on. The player who first

reaches a negative number loses the game. Prove that there

exist infinitely many values of t for which the first player has a

winning strategy for all pairs (a, b) with (a + b) = 2005.

8. [Rioplatense Math Olympiad 2010]

Alice and Bob play the following game. To start, Alice arranges

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.

9. [Russia 2007]

Two players take turns drawing diagonals in a regular (2n+1)-

gon (n > 1). It is forbidden to draw a diagonal that has already

been drawn or intersects an odd number of already drawn

diagonals. The player who has no legal move loses. Who has a

winning strategy?

10. [Indian Practice TST 2013]

A marker is placed at the origin of an integer lattice. Calvin

and Hobbes play the following game. Calvin starts the game

and each of them takes turns alternatively. At each turn, one

can choose two (not necessarily distinct) integers a and b,

neither of which was chosen earlier by any player and move

the marker by a units in the horizontal direction and b units in

the vertical direction. Hobbes wins if the marker is back at the

origin any time after the first turn. Determine whether Calvin

can prevent Hobbes from winning.

Note: A move in the horizontal direction by a positive quantity

will be towards the right, and by a negative quantity will be

towards the left (and similarly in the vertical case as well).

Page 255

Olympiad Combinatorics 20

11. [Based on South Korea 2009, Problem 5]

Consider an m × (m+1) grid of points, where each point is

joined by a line segment to is immediate neighbors (points

immediately to the left, right, above or below). A stone is

initially placed on one of the points in the bottom row. A and B

alternately move the stone along line segments, according to

the rule that no line segment may be used more than once.

The player unable to make a legal move loses. Determine

which player has a winning strategy.

12. [IMO Shortlist 1994, C6]

Two players play alternatively on an infinite square grid. The

first player puts an X in an empty cell and the second player

puts an O in an empty cell. The first player wins if he gets 11

adjacent X's in a line - horizontally, vertically or diagonally.

Show that the second player can always prevent the first

player from winning.

13. [Nim]

There are k heaps of stones, containing a1, a2 ak stones

respectively, where the ai A

and B play alternately as follows: in each turn, a player

chooses one non-empty heap and removes as many stones as

he or she wants. The person who takes the last stone wins.

Determine when each player has a winning strategy, and find

this winning strategy.

14. [The name of this problem would give the answer away]

There is one pile of N counters. A and B play alternately as

follows. In the first turn of the game, A may remove any

positive number of counters, but not the whole pile.

Thereafter, each player may remove at most twice the number

of counters his opponent took on the previous move. The

player who removes the last counter wins. Who has the

winning strategy?