Let $n$ be an integer greater than $1$ and let $S$ be a finite set containing more than $n+1$ elements.Consider the collection of all sets $A$ of subsets of $S$ satisfying the following two conditions : (a) Each member of $A$ contains at least $n$ elements of $S$. (b) Each element of $S$ is contained in at least $n$ members of $A$. Determine $\max_A \min_B |B|$ , as $B$ runs through all subsets of $A$ whose members cover $S$ , and $A$ runs through the above collection.
Problem
Source: Romania TST 2014 Day 1 Problem 5
Tags: combinatorics unsolved, combinatorics
23.04.2015 15:34
We will prove, the required number is $|S|-n$. Let $\mathcal{A}$ is a set of subsets of $S$, satisfying (a) and (b). One can choose $|S|-n+1$ members of $\mathcal{A}$, covering $S$ as follows: first take any $A\in \mathcal{A}$, which covers at least $n$ elements of $S$, and then for each of the remaining at most $|S|-n$ elements, choose a set covering that element. Claim: There exist $|S|-n$ members of $\mathcal{A}$, covering $S$. Proof: If some member of $\mathcal{A}$ has more than $n$ elements, we are done in the same way as shown above. Suppose each member of $\mathcal{A}$ consists of $n$ elements of $S$. Take arbitrary $A\in \mathcal{A}$. Consider $A^c=S-A$. If some $A' \in \mathcal{A}$ meats two or more alements of $A^c$ we are done, so suppose $|A'\cap A^c|=1$ for all $A' \in \mathcal{A}, A' \neq A$. Fix $x\in A^c$. According to (b), any set consisting of $x$ plus $n-1$ elements of $A$ should belong to $\mathcal{A}$. But then, for every $x\in A^c$, one can choose $A_x\in \mathcal{A}$ with $x\in A_x$ and $A \subset \bigcup_{x\in A^c} A_x$, which means $S=\bigcup_{x\in A^c} A_x$ $\blacksquare$ Therefore, we proved $\max_A \min_B |B|\leq |S|-n$. Now, consider a family $\mathcal{A}$ of subsets of $S$ as follows: Suppose $S=\{1,2,\dots, m\}\, ,m\geq n+2$. Then $\mathcal{A} := \{ A\subset S : A= (\{1,2,\dots,n\} \setminus \{x\}) \cup \{y\}\,,\, x\in\{1,2,\dots n\}, y\in\{n+1,\dots,m\} \}$. Clearly, there do not exist $m-n-1$ members of $\mathcal{A}$ covering $S$, implying \[\max_A \min_B |B| = |S|-n.\]