Let $F$ be a family of subsets of $S = \left \{ 1,2,...,n \right \}$ ($n \geq 2$). A valid play is to choose two disjoint sets $A$ and $B$ from $F$ and add $A \cup B$ to $F$ (without removing $A$ and $B$). Initially, $F$ has all the subsets that contain only one element of $S$. The goal is to have all subsets of $n - 1$ elements of $S$ in $F$ using valid plays. Determine the lowest number of plays required in order to achieve the goal.
Problem
Source:
Tags: induction, combinatorics, Set systems
Davi Medeiros
19.09.2014 12:12
We'll show that the answer is at least $3n-6$ by induction on $n$. The cases $n=2$ and $n=3$ are really trivial. Now, suppose that we need at least $3k-6$ moves to obtain $\{1,2,...,k \}- \{t \}, t=1,2,...,k$ from $ \{1 \}, \{2 \},..., \{k \}$. Now, suppose that we made $m$ moves to obtain $\{ 1,2,...,k+1 \} - \{ t \}, t=1,2,...,k+1$ from $ \{1 \},\{ 2 \},...,\{k+1 \}$. First, notice that we use $\{k+1 \}$ in at least 2 operations, because if we use $ \{k+1 \}$ in only one operation (we must use $\{k+1 \}$ in at lest one operation, since $\{ 2,3,..,k+1 \}$ appears in the end), let us say that $ \{k+1 \}$ was operated with the set $A \subset \{1,2,..,k \}$. Then, we can't obtain the set $\{1,2,...,k+1 \}-\{a \}$, where $a \in A$, contradiction. Now, let $F$ be the family of subsets of $ \{1,2,...,k+1 \}$ after the $m$ operations. For each $A\in F$, let $A'=A- \{k+1 \}$, and $F'= \cup A'$. Looking at $F' \subset \{ 1,2,..., k \}$, we see that $F$ initially had only $ \{1 \}, \{2 \},..., \{k \}$ (and the empty set $ \{k+1 \} - \{k +1 \}$). At the end, $F'$ have $\{1,2,...,k \}- \{t \}, t=1,2,...,k$, and $\{1,2,...,k \}= \{1,2,...,k+1 \} - \{k+1 \}$. Thus, we need, by hypothesis, at least $3k-6+1=3k-5$ moves to obtains $F'$ (the one more move is because the set $\{1,2,...,k \}$). Also, we use ${k+1}$ at least twice, so we need at least $3k-5+2=3k-3$ operations. Thus, $m \ge 3k-3=3(k+1)-6$, and the result follows from induction. Now, we'll show a example that with exactly $3n-6$ operation, we can obtain $\{1,2,...,n \}- \{t \}, t=1,2,...,n$ from $ \{1 \}, \{2 \},..., \{n \}$. $\{1 \}, \{2 \} \rightarrow \{1, 2 \}$ $\{1, 2 \}, \{3 \} \rightarrow \{1, 2, 3 \}$ $\{1, 2, 3 \}, \{4 \} \rightarrow \{1, 2, 3, 4 \}$ $\dots$ $\{1, 2, ..., n-3 \}, \{n-2 \} \rightarrow \{1, 2, ..., n-2 \}$ $\{1, 2, ..., n-2 \}, \{n-1 \} \rightarrow \{1, 2, ..., n\} - \{n \}$ $\{n \}, \{n-1 \} \rightarrow \{n, n-1 \}$ $\{n, n-1 \}, \{n-2 \} \rightarrow \{n,n-1, n-2 \}$ $\{n,n-1, n-2 \}, \{n-3 \} \rightarrow \{n, n-1, n-2, n-3 \}$ $\dots$ $\{n,n-1, ..., 4 \}, \{3 \} \rightarrow \{n, n-1, ..., 3 \}$ $\{n,n-1, ..., 3 \}, \{2 \} \rightarrow \{1, 2, ..., n\} - \{1 \}$ $\{1, 2, ..., n-2 \}, \{n \} \rightarrow \{1, 2, ...,n \} - \{n-1 \}$ $\{1, 2, ..., n-3 \}, \{n, n-1 \} \rightarrow \{1, 2, ...,n \} - \{n-2 \}$ $\dots$ $\{1 \}, \{n, n-1, ..., 3 \} \rightarrow \{1, 2, ...,n \} - \{2 \}$ Finally, the conclude that the minimum is $3n-6$.