MathDB

Indices of intersecting sets form a set

Source: 2012 Indonesia Round 2.5 TST 3 Problem 2

May 21, 2012

combinatorics unsolvedcombinatorics

Problem Statement

Let

P_1, P_2, \ldots, P_n

be distinct

2

-element subsets of

\{1, 2, \ldots, n\}

. Suppose that for every

1 \le i < j \le n

, if

P_i \cap P_j \neq \emptyset

, then there is some

k

such that

P_k = \{i, j\}

. Prove that if

a \in P_i

for some

i

, then

a \in P_j

for exactly one value of

j

not equal to

i

.

Back to Problems View on AoPS