MathDB

5 non-empty disjoint sets

Source: Vietnam TST 1991 for the 32nd IMO, problem 6

June 25, 2005

graph theorycombinatorics unsolvedcombinatorics

Problem Statement

Let a set

X

be given which consists of

2 \cdot n

distinct real numbers (

n \geq 3

). Consider a set

K

consisting of some pairs

(x, y)

of distinct numbers

x, y \in X

, satisfying the two conditions: I. If

(x, y) \in K

then

(y, x) \not \in K

. II. Every number

x \in X

belongs to at most 19 pairs of

K

. Show that we can divide the set

X

into 5 non-empty disjoint sets

X_1, X_2, X_3, X_4, X_5

in such a way that for each

i = 1, 2, 3, 4, 5

the number of pairs

(x, y) \in K

where

x, y

both belong to

X_i

is not greater than

3 \cdot n

.

Back to Problems View on AoPS