Distinctness is maintained after adding some element to all sets

Solution 1:

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.

Solution 2:

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.