Problem

Source: Iranian National Olympiad (3rd Round) 2006

Tags: ceiling function, combinatorics proposed, combinatorics



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$