MathDB
A collection of subsets each has exactly one of two elements

Source: Balkan MO 1997, Problem 2

April 24, 2006
combinatorics proposedcombinatorics

Problem Statement

Let S={A1,A2,…,Ak}S = \{A_1,A_2,\ldots ,A_k\} be a collection of subsets of an nn-element set AA. If for any two elements x,y∈Ax, y \in A there is a subset Ai∈SA_i \in S containing exactly one of the two elements xx, yy, prove that 2k≥n2^k\geq n. Yugoslavia
Back to ProblemsView on AoPS