MathDB

Maximal size of set of subsets

Source: INMO 2014 P6

February 2, 2014

inductioncombinatorics proposedcombinatorics

Problem Statement

Let

n>1

be a natural number. Let

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

, and define

\mathcal{F}

to be the set of all those elements of

U

which belong to exactly one of

A

and

B

. Show that

|\mathcal{F}|\le 2^{n-1}

, where

\mathcal{F}

is a collection of subsets of

U

such that for any two distinct elements of

A,B

of

\mathcal{F}

we have

|A\Delta B|\ge 2

. Also find all such collections

\mathcal{F}

for which the maximum is attained.

Back to Problems View on AoPS