MathDB

Let

E

be a family of subsets of

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

with the property that for each

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

there exist

B\in F

such that

\frac{n-d}2\leq |A \bigtriangleup B| \leq \frac{n+d}2

. (where

A \bigtriangleup B = (A\setminus B) \cup (B\setminus A)

is the symmetric difference). Denote by

f(n,d)

the minimum cardinality of such a family. a) Prove that if

n

is even then

f(n,0)\leq n

. b) Prove that if

n-d

is even then

f(n,d)\leq \lceil \frac n{d+1}\rceil

. c) Prove that if

n

is even then

f(n,0) = n

Problem Statement