MathDB
Problems
Contests
International Contests
Balkan MO
1997 Balkan MO
2
2
Part of
1997 Balkan MO
Problems
(1)
A collection of subsets each has exactly one of two elements
Source: Balkan MO 1997, Problem 2
4/24/2006
Let
S
=
{
A
1
,
A
2
,
…
,
A
k
}
S = \{A_1,A_2,\ldots ,A_k\}
S
=
{
A
1
,
A
2
,
…
,
A
k
}
be a collection of subsets of an
n
n
n
-element set
A
A
A
. If for any two elements
x
,
y
∈
A
x, y \in A
x
,
y
∈
A
there is a subset
A
i
∈
S
A_i \in S
A
i
∈
S
containing exactly one of the two elements
x
x
x
,
y
y
y
, prove that
2
k
≥
n
2^k\geq n
2
k
≥
n
. Yugoslavia
combinatorics proposed
combinatorics