Let $S=\{S_1,S_2,\ldots,S_n\}$ be a set of $n$ distinct subsets with $S_i \subseteq \{1,\ldots,n\}$ for $i=1,\ldots, n$ then $k \in \{1,\ldots,n\}$ exists with $S_i \cup \{k\}$ is distinct for $i=1,\ldots,n$.
I found this in a old problem sheet of mine about sets and graph theory. Is there a elegant solution to this problem?
On
THIS IS INCORRECT
Suppose that this wasn't the case. Then for each $k \in \{1, \dots, n\}$ you can find $S_a \subset S_b$ such that $S_b \setminus S_a = \{k\}$.
Consider a directed graph where the $n$ vertices correspond to the sets and there is an edge from $S_a$ to $S_b$ if and only if $S_b \setminus S_a$ consists of exactly one element. Clearly there won't be any loops so it is a forest with at most $n-1$ edges. Now by pigeonhole principle one of the edges must get two $k$s which is impossible.
This result follows from Bondy's theorem (in fact, it is equivalent) which states that,
Given $\displaystyle n$ distinct sets $\displaystyle S_1, S_2, \dots, S_n$, each a subset of $\displaystyle \{1,2, \dots, n\}$, there is a set $\displaystyle A \subset \{1,2, \dots, n\}$, with $\displaystyle |A| \leq n-1$ such that the sets $\displaystyle S_i \cap A$ are all distinct.
Pick a $\displaystyle k \notin A$. Then we have that if $\displaystyle S_i \cup \{k\} = S_j \cup \{k\}$, then $\displaystyle (S_i \cup \{k\}) \cap A = (S_j \cup \{k\}) \cap A$. Since $\displaystyle k \notin A$, it follows that $\displaystyle S_i \cap A = S_j \cap A$ contradicting the result of Bondy's theorem.
You can find a short proof and a sketch of an elegant linear algebra proof (originally due to Babai and Frankl) of Bondy's theorem, in the excellent book, Extremal Combinatorics by Stasys Jukna.