Let n≥3 be an integer and let A1,A2,…,An be n distinct subsets of S={1,2,…,n}. Show that there exists x∈S such that the n subsets Ai−{x},i=1,2,…n are also disjoint.
HIDE: what i have is this we may assume that the union of the Ais is S.Source: Taiwan 2001
Tags: search, combinatorics unsolved, combinatorics
Let n≥3 be an integer and let A1,A2,…,An be n distinct subsets of S={1,2,…,n}. Show that there exists x∈S such that the n subsets Ai−{x},i=1,2,…n are also disjoint.
HIDE: what i have is this we may assume that the union of the Ais is S.