100 Combinatorics Problems.pdf

COMBINATORICS PROBLEMS

AMIR HOSSEIN PARVARDI

JUNE 16, 2011

This is a little bit dierent from the other problem sets I’ve made before. I’ve

written the source of the problems beside their numbers. If you need solutions,

visit AoPS Resources Page, select the competition, select the year and go to

the link of the problem.

All of these problems have been posted by Orlando

Doehring (orl).

Contents

1 Problems

1.1

IMO Problems

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

ISL and ILL Problems . . . . . . . . . . . . . . . . . . . . . . . .

1.3

Ohter Competitions

. . . . . . . . . . . . . . . . . . . . . . . . .

1.3.1

China IMO Team Selection Test Problems . . . . . . . . .

1.3.2

Vietnam IMO Team Selection Test Problems

. . . . . . .

1.3.3

Other Problems . . . . . . . . . . . . . . . . . . . . . . . .

Problems

1.1 IMO Problems

1. (IMO 1970, Day 2, Problem 4) Find all positive integers n such that

the set {n, n + 1 , n + 2 , n + 3 , n + 4 , n + 5 } can be partitioned into two subsets

so that the product of the numbers in each subset is equal.

2. (IMO 1970, Day 2, Problem 6) Given 100 coplanar points, no three

collinear, prove that at most 70% of the triangles formed by the points have all

angles acute.

3. (IMO 1971, Day 2, Problem 5) Prove that for every positive integer m

we can nd a nite set S of points in the plane, such that given any point A of

S , there are exactly m points in S at unit distance from A .

email: ahpwsog@gmail.com , blog: http://math-olympiad.blogsky.com .

4. (IMO 1972, Day 1, Problem 1) Prove that from a set of ten distinct two-

digit numbers, it is always possible to nd two disjoint subsets whose members

have the same sum.

5. (IMO 1975, Day 2, Problem 5) Can there be drawn on a circle of radius

1 a number of 1975 distinct points, so that the distance (measured on the chord)

between any two points (from the considered points) is a rational number?

6. (IMO 1976, Day 1, Problem 3) A box whose shape is a parallelepiped can

be completely lled with cubes of side 1 . If we put in it the maximum possible

number of cubes, each ofvolume, 2, with the sides parallel to those of the box,

then exactly 40 percent from the volume of the box is occupied. Determine the

possible dimensions of the box.

7. (IMO 1978, Day 2, Problem 6) An international society has its members

from six dierent countries. The list of members contain 1978 names, numbered

1 , 2 , . . . , 1978. Prove that there is at least one member whose number is the sum

of the numbers of two members from his own country, or twice as large as the

number of one member from his own country.

8. (IMO 1981, Day 1, Problem 2) Take r such that 1 ≤r≤n , and consider

all subsets of r elements of the set { 1 , 2 , . . . , n} . Each subset has a smallest

element. Let F ( n, r ) be the arithmetic mean of these smallest elements. Prove

that:

F ( n, r ) = n + 1

r + 1 .

9. (IMO 1985, Day 2, Problem 4) Given a set M of 1985 distinct positive

integers, none of which has a prime divisor greater than 23, prove that M

contains a subset of 4 elements whose product is the 4th power of an integer.

10. (IMO 1986, Day 1, Problem 3) To each vertex of a regular pentagon

an integer is assigned, so that the sum of all ve numbers is positive. If three

consecutive vertices are assigned the numbers x, y, z respectively, and y < 0,

then the following operation is allowed: x, y, z are replaced by x + y,−y, z + y

respectively. Such an operation is performed repeatedly as long as at least one

of the ve numbers is negative. Determine whether this procedure necessarily

comes to an end after a nite number of steps.

11. (1986, Day 2, Problem 6) Given a nite set of points in the plane, each

with integer coordinates, is it always possible to color the points red or white so

that for any straight line L parallel to one of the coordinate axes the dierence

(in absolute value) between the numbers of white and red points on L is not

greater than 1?

12. (IMO 1987, Day 1, Problem 1) Let p n ( k ) be the number of permuta-

tions of the set { 1 , 2 , 3 , . . . , n} which have exactly k xed points.

Prove that

k=0 kp n ( k ) = n !.

13. (IMO 1989, Day 1, Problem 3) Let n and k be positive integers and

let S be a set of n points in the plane such that

• no three points of S are collinear, and

• for every point P of S there are at least k points of S equidistant from P.

Prove that:

√

k < 1

2 n

14. (IMO 1989, Day 2, Problem 6) A permutation {x 1 , . . . , x 2n

} of the

set { 1 , 2 , . . . , 2 n} where n is a positive integer, is said to have property T if

|x i

| = n for at least one i in { 1 , 2 , . . . , 2 n− 1 }. Show that, for each n ,

there are more permutations with property T than without.

−x i+1

15. (IMO 1990, Day 1, Problem 2) Let n≥ 3 and consider a set E of

2 n− 1 distinct points on a circle. Suppose that exactly k of these points are to

be colored black. Such a coloring is good if there is at least one pair of black

points such that the interior of one of the arcs between them contains exactly

n points from E . Find the smallest value of k so that every such coloring of k

points of E is good.

16. (IMO 1991, Day 1, Problem 3) Let S = { 1 , 2 , 3 ,, 280 } . Find the

smallest integer n such that each n -element subset of S contains ve numbers

which are pairwise relatively prime.

17. (IMO 1992, Day 1, Problem 3) Consider 9 points in space, no four of

which are coplanar. Each pair of points is joined by an edge (that is, a line

segment) and each edge is either colored blue or red or left uncolored. Find the

smallest value of n such that whenever exactly n edges are colored, the set of

colored edges necessarily contains a triangle all of whose edges have the same

color.

18. (IMO 1993, Day 1, Problem 3) On an innite chessboard, a solitaire

game is played as follows: at the start, we have n 2 pieces occupying a square

of side n. The only allowed move is to jump over an occupied square to an

unoccupied one, and the piece which has been jumped over is removed.

For

which n can the game end with only one piece remaining on the board?

19. (IMO 1993, Day 2, Problem 6) Let n > 1 be an integer. In a circular

arrangement of n lamps L 0 , . . . , L n−1 , each of of which can either ON or OFF, we

start with the situation where all lamps are ON, and then carry out a sequence

of steps, Step 0 , Step 1 , . . . . If L j−1 ( j is taken mod n ) is ON then Step j changes

the state of L j (it goes from ON to OFF or from OFF to ON) but does not

change the state of any of the other lamps. If L j−1 is OFF then Step j does not

change anything at all. Show that:

• There is a positive integer M ( n ) such that after M ( n ) steps all lamps are

ON again,

• If n has the form 2 k

then all the lamps are ON after n 2 − 1 steps,

• If n has the form 2 k + 1 then all lamps are ON after n 2 −n + 1 steps.

1.2 ISL and ILL Problems

20. (IMO LongList 1959-1966 Problem 14) What is the maximal number

of regions a circle can be divided in by segments joining n points on the boundary

of the circle ?

21. (IMO LongList 1959-1966 Problem 45) An alphabet consists of n let-

ters. What is the maximal length of a word if we know that any two consecutive

letters a, b of the word are dierent and that the word cannot be reduced to a

word of the kind abab with a = b by removing letters.

[ 2 ]

22. (IMO ShortList 1973, Romania 1) Show that there exists exactly

sequences a 1 , a 2 , . . . , a k+1 of integer numbers ≥ 0 , for which a 1 = 0 and |a i

−

a i+1

| = 1 for all i = 0 , . . . , k.

23. (IMO ShortList 1974, USA 1) Three players A, B and C play a game

with three cards and on each of these 3 cards it is written a positive integer,

all 3 numbers are dierent. A game consists of shuing the cards, giving each

player a card and each player is attributed a number of points equal to the

number written on the card and then they give the cards back. After a number

( ≥ 2) of games we nd out that A has 20 points, B has 10 points and C has

9 points. We also know that in the last game B had the card with the biggest

number. Who had in the rst game the card with the second value (this means

the middle card concerning its value).

24. (IMO ShortList 1988, Problem 11) The lock of a safe consists of 3

wheels, each of which may be set in 8 dierent ways positions. Due to a defect

in the safe mechanism the door will open if any two of the three wheels are in

the correct position. What is the smallest number of combinations which must

be tried if one is to guarantee being able to open the safe (assuming the ”right

combination” is not known)?

25. (IMO ShortList 1988, Problem 20) Find the least natural number n

such that, if the set { 1 , 2 , . . . , n} is arbitrarily divided into two non-intersecting

subsets, then one of the subsets contains 3 distinct numbers such that the prod-

uct of two of them equals the third.

26. (IMO ShortList 1988, Problem 31) Around a circular table an even

number of persons have a discussion. After a break they sit again around the

circular table in a dierent order. Prove that there are at least two people such

that the number of participants sitting between them before and after a break

is the same.

27. (IMO Longlist 1989, Problem 27) Let L denote the set of all lattice

points of the plane (points with integral coordinates). Show that for any three

points A, B, C of L there is a fourth point D, dierent from A, B, C, such that the

interiors of the segments AD, BD, CD contain no points of L. Is the statement

true if one considers four points of L instead of three?

28. (IMO Longlist 1989, Problem 80) A balance has a left pan, a right

pan, and a pointer that moves along a graduated ruler. Like many other grocer

balances, this one works as follows: An object of weight L is placed in the left

pan and another of weight R in the right pan, the pointer stops at the number

R−L on the graduated ruler. There are n, ( n≥ 2) bags of coins, each containing

n(n−1)

2 + 1 coins. All coins look the same (shape, color, and so on). n− 1 bags

contain real coins, all with the same weight. The other bag (we dont know which

one it is) contains false coins. All false coins have the same weight, and this

weight is dierent from the weight of the real coins. A legal weighing consists of

placing a certain number of coins in one of the pans, putting a certain number

of coins in the other pan, and reading the number given by the pointer in the

graduated ruler. With just two legal weighings it is possible to identify the bag

containing false coins. Find a way to do this and explain it.

29. (IMO ShortList 1988, Problem 4) An n×n, n≥ 2 chessboard is num-

bered by the numbers 1 , 2 , . . . , n 2 (and every number occurs). Prove that there

exist two neighbouring (with common edge) squares such that their numbers

dier by at least n.

30. (IMO ShortList 1990, Problem 15) Determine for which positive inte-

gers k the set

X = { 1990 , 1990 + 1 , 1990 + 2 , . . . , 1990 + k}

can be partitioned into two disjoint subsets A and B such that the sum of the

elements of A is equal to the sum of the elements of B.

31. (IMO Shortlist 1993, Ireland 2) Let n, k∈

Z + with k≤n and let S

be a set containing n distinct real numbers. Let T be a set of all real numbers

of the form x 1 + x 2 + . . . + x k where x 1 , x 2 , . . . , x k are distinct elements of S.

Prove that T contains at least k ( n−k ) + 1 distinct elements.

32. (IMO Shortlist 1994, Combinatorics Problem 2) In a certain city,

age is reckoned in terms of real numbers rather than integers. Every two citizens

x and x ′ either know each other or do not know each other. Moreover, if they

do not, then there exists a chain of citizens x = x 0 , x 1 , . . . , x n = x ′ for some

integer n≥ 2 such that x i−1 and x i know each other. In a census, all male

citizens declare their ages, and there is at least one male citizen. Each female

citizen provides only the information that her age is the average of the ages of

all the citizens she knows. Prove that this is enough to determine uniquely the

ages of all the female citizens.

33. (IMO Shortlist 1995, Combinatorics Problem 5) At a meeting of

12 k people, each person exchanges greetings with exactly 3 k + 6 others. For any

two people, the number who exchange greetings with both is the same.

How

many people are at the meeting?

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: