MathDB

Two-element-subsets

Source: QEDMO 2005

November 8, 2005

combinatorics proposedcombinatorics

Problem Statement

Let

n\geq 3

be an integer. Let also

P_1,P_2,...,P_n

be different two-element-subsets of

M=\{1,2,...,n\}

, such that when for

i,j \in M , i\neq j

the sets

P_i,P_j

are not totally disjoint, then there is a

k \in M

with

P_k = \{ i,j\}

. Prove that every element of

M

occurse in exactly

2

of these subsets.

Back to Problems View on AoPS