INDUCTION

SEYED HESSAM FIROUZI

(1) We choose n ≥ 3 points on a circle and number them 1 to n in some order. We say that
two non-adjacent points A and B are related if, in one of the arcs AB, all the points are
marked with numbers less than those at A, B. Show that the number of pairs of related
points is exactly n − 3. (Spain 1988)
(2) There are 2005 young people sitting around a large circular table. Of these, at most 668
are boys. We say that a girl G has a strong position, if, counting from G in either direction,
the number of girls is always strictly larger than the number of boys (G is herself included
in the count). Prove that there is always a girl in a strong position. (Nordic 2005)
(3) The exact quantity of gas needed for a car to complete a single loop around a track is
distributed among n containers placed along the track. Prove that there exists a position
starting at which the car, beginning with an empty tank of gas, can complete a loop around
the track without running out of gas. The tank of gas is assumed to be large enough. (Spain
1997)
(4) Rainbow is the name of a bird. This bird has n colors and it’s colors in two consecutive
days are not equal. There doesn’t exist 4 days in this bird’s life like i, j, k, l such that
i < j < k < l and the bird has the same color in days i and k and the same color in days
j and l different from the colors it has in days i and k. What is the maximum number of
days rainbow can live in terms of n? (Iran 2011)
(5) Let n be a natural number and suppose that w1 , w2 , . . . , wn are n weights . We call the set
of {w1 , w2 , . . . , wn } to be a Perfect Set
∑ if we can achieve all of the 1, 2, . . . , W weights with
sums of w1 , w2 , . . . , wn , where W = ni=1 wi . Prove that if we delete the maximum weight
of a Perfect Set, the other weights make again a Perfect Set. (Iran 2013)
(6) Suppose a m × n table. We write an integer in each cell of the table. In each move, we chose
a column, a row, or a diagonal (diagonal is the set of cells which the difference between
their row number and their column number is constant) and add either +1 or −1 to all of
its cells. Prove that if for all arbitrary 3 × 3 table we can change all numbers to zero, then
we can change all numbers of m × n table to zero. (Iran 2013)
(7) Suppose n is a natural number. In how many ways can we place numbers 1, 2, ...., n around
a circle such that each number is a divisor of the sum of it’s two adjacent numbers? (Iran
2012)
2
(8) A graph G with n vertices and m > n4 edges, contains triangle.
(9) Let n be a positive integer. Let Pn = {2n , 2n−1 · 3, 2n−2 · 32 , . . . , 3n }. For each subset X of
Pn , we write SX for the sum of all elements of X, with the convention that S∅ = 0 where
∅ is the empty set. Suppose that y is a real number with 0 ≤ y ≤ 3n+1 − 2n+1 . Prove that
there is a subset Y of Pn such that 0 ≤ y − SY < 2n . (Balkan 2012)
(10) An n × n matrix whose entries come from the set S = {1, 2, . . . , 2n − 1} is called a silver
matrix if, for each i = 1, 2, . . . , n, the i-th row and the i-th column together contain all
elements of S. Show that:
(a) there is no silver matrix for n = 1997;
(b) silver matrices exist for infinitely many values of n. (IMO 1997)
1
(11) On each day, more than half of the inhabitants of Évora eats sericaia as dessert. Show that
there is a group of 10 inhabitants of Évora such that, on each of the last 2010 days, at least
one of the inhabitants ate sericaia as dessert. (Portugal 2010)
(12) For n ∈ N find the minimum non-negative integer m such that we can label the edges of
Kn by numbers 1, . . . , m such that in every tringle, two edges are equal and less than the
third edge.
(13) Consider a ping-pong match between two teams, each consisting of 1000 players. Each
player played against each player of the other team exactly once (there are no draws in
ping-pong). Prove that there exist ten players, all from the same team, such that every
member of the other team has lost his game against at least one of those ten players. (Baltic
1998)
(14) Let G be a tournoment such that it’s edges are colored either red or blue. Prove that
there exists a vertex of G like v with the property that, for every other vertex u there is a
mono-color directed path from v to u. (Iran 2006)
(15) Suppose three direction on the plane . We draw 11 lines in each direction . Find maximum
number of the points on the plane which are on three lines. (Iran 2009)
(16) Suppose that T is a tree with k edges. Prove that the k-dimensional cube can be partitioned
to graphs isomorphic to T . (Iran 2008)
(17) A school has n students and k classes. Every two students in the same class are friends.
For each two different classes, there are two people from these classes that are not friends.
Prove that we can divide students into n − k + 1 parts taht students in each part are not
friends. (Iran 2002)
(18) The vertices of the graph G are colored black or white. In each turn we can choose a vertex
v and change the colors of v and all of its neighbors. Prove that begining from all vertices
white, we can reach to all vertices black.
(19) All subsets of size n of [n2 + n − 1] are partitioned to two subsets A and B. Prove that in
one part will be find n pairwise disjoint subsets.
(20) Six 3-elements subsets A1 , . . . , A6 of A are given. Prove that we can color elements of A by
red and blue such that none of A1 , . . . , A6 become monochromatic.
(21) We call three sets A, B and C triangle, if intersection of any two of them is nonempty, and
intersection of all of them is empty. Given 2n−1 subsets of size more than 1 of [n], prove
that there is a triangle between them.
(22) A word is defined as any finite string of letters. A word is a palindrome if it reads the same
backwards and forwards. Let a sequence of words W0 , W1 , W2 , ... be defined as follows:
W0 = a, W1 = b, and for n ≥ 2, Wn is the word formed by writing Wn−2 followed by Wn−1 .
Prove that for any n ≥ 1, the word formed by writing W1 , W2 , W3 , ..., Wn in succession is a
palindrome. (USA 2011)
(23) Let n be a positive integer and let S be a set of 2n + 1 elements. Let f be a function from
the set of two-element subsets of S to {0, . . . , 2n−1 − 1}. Assume that for any elements
x, y, z of S, one of f ({x, y}), f ({y, z}), f ({z, x}) is equal to the sum of the other two. Show
that there exist a, b, c in S such that f ({a, b}), f ({b, c}), f ({c, a}) are all equal to 0. (USA
2002)
(24) Let n be a positive integer. Suppose we are given 2n + 1 distinct sets, each containing
finitely many objects. Place each set into one of two categories, the red sets and the blue
sets, so that there is at least one set in each category. We define the symmetric difference
of two sets as the set of objects belonging to exactly one of the two sets. Prove that there
are at least 2n different sets which can be obtained as the symmetric difference of a red set
and a blue set. (USA 2011)

2
(25) Let n be a natural number. There are n boys and n girls standing in a line, in any arbitrary
order. A student X will be eligible for receiving m candies, if we can choose two students of
opposite sex with X standing on either side of X in m ways. Show that the total number
of candies does not exceed 31 n(n2 − 1). (Vietnam 2012)
(26) There are n boxes B1 , B2 , . . . , Bn from left to right, and there are n balls in these boxes. If
there is at least 1 ball in B1 , we can move one to B2 . If there is at least 1 ball in Bn , we
can move one to Bn−1 . If there are at least 2 balls in Bk , 2 ≤ k ≤ n − 1 we can move one
to Bk−1 , and one to Bk+1 . Prove that, for any arrangement of the n balls, we can achieve
that each box has one ball in it. (China 2011)
2
(27) In time 0 an insect A is at (0, 0) in latice Z . In every step it can move up or right a unit
distance. There is an infinite sequence X1 , X2 , . . . of latice points that at time i the point
Xi will become poisonous and remain poisonous. A knows the sequence. Prove that A can
move infinitely many steps healthy.
(28) Let U = {1, 2, . . . , n}, where n ≥ 3. A subset S of U is said to be split by an arrangement of
the elements of U if an element not in S occurs in the arrangement somewhere between two
elements of S. For example, 13542 splits {1, 2, 3} but not {3, 4, 5}. Prove that for any n − 2
subsets of U , each containing at least 2 and at most n − 1 elements, there is an arrangement
of the elements of U which splits all of them. (Shortlist 1998)
(29) Let k and n be integers with 0 ≤ k ≤ n − 2. Consider a set L of n lines in the plane such
that no two of them are parallel and no three have a common point. Denote by I the set of
intersections of lines in L. Let O be a point in the plane not lying on any line of L. A point
X ∈ I is colored red if the open line segment OX intersects at most k lines in L. Prove
1
that I contains at least (k + 1)(k + 2) red points. (Shortlist 2008)
2
(30) Let a1 , a2 , . . . , an be distinct positive integers and let M be a set of n − 1 positive integers
not containing s = a1 + a2 + . . . + an . A grasshopper is to jump along the real axis, starting
at the point 0 and making n jumps to the right with lengths a1 , a2 , . . . , an in some order.
Prove that the order can be chosen in such a way that the grasshopper never lands on any
point in M. (IMO 2009)
(31) In Lineland there are n ≥ 1 towns, arranged along a road running from left to right. Each
town has a left bulldozer (put to the left of the town and facing left) and a right bulldozer
(put to the right of the town and facing right). The sizes of the 2n bulldozers are distinct.
Every time when a left and right bulldozer confront each other, the larger bulldozer pushes
the smaller one off the road. On the other hand, bulldozers are quite unprotected at their
rears; so, if a bulldozer reaches the rear-end of another one, the first one pushes the second
one off the road, regardless of their sizes.
Let A and B be two towns, with B to the right of A. We say that town A can sweep
town B away if the right bulldozer of A can move over to B pushing off all bulldozers it
meets. Similarly town B can sweep town A away if the left bulldozer of B can move over
to A pushing off all bulldozers of all towns on its way.
Prove that there is exactly one town that cannot be swept away by any other one.
(Shortlist 2015)
(32) An integer N ≥ 2 is given. A collection of N (N + 1) soccer players, no two of whom are of
the same height, stand in a row. Sir Alex wants to remove N (N − 1) players from this row
leaving a new row of 2N players in which the following N conditions hold:
(1) no one stands between the two tallest players,
(2) no one stands between the third and fourth tallest players,
..
.
(N ) no one stands between the two shortest players.
3
Show that this is always possible. (Shortlist 2017)