Title Olympiad Combinatorics 7.9 MB 255
```                            Chapter6.pdf (p.1-31)
Chapter7.pdf (p.32-65)
Chapter8.pdf (p.66-94)
Chapter9.pdf (p.95-129)
Chapter1.pdf (p.130-159)
Chapter2.pdf (p.160-179)
Chapter3.pdf (p.180-205)
Chapter4.pdf (p.206-232)
Chapter5.pdf (p.233-255)
```
##### Document Text Contents
Page 1

Combinatorics

Pranav A. Sriram

August 2014

Page 2

Chapter 6: Counting in Two Ways 1

All USAMO and USA Team Selection Test problems in this chapter

American Mathematics Competitions.

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

express written consent from 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

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
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.

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

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?