An element whose removal makes sets in a family distinct

Question

Let $n\geq 2$ and suppose that $\mathcal{A} \subseteq \mathcal{P}(n)$ is a family of at most $n-1$ sets. Prove that there is $x \in \{1,2,\ldots,n\}$ such that the sets $A\setminus x, A \in \mathcal{A}$ are distinct.

I tried to consider the characteristic vectors of these (if we suppose the contrary, then there must be at least $n$ pairs differing at exactly one entry) and either use Fisher's inequality or do a simple induction, but none of them work.

I think that a restatement of the previous paragraph is: $\textbf{Prove that any set of $n$ edges in an $n$-regular graph involves at least $n$ vertices}$ which I also cannot prove.

Any help appreciated!

Answer 1

Here's a sketch of a proof by induction on $n$.

Try removing the element $n$ from the sets. If it works, great. If not, then the family $\mathcal A' = \{A \setminus \{n\} : A \in \mathcal A\}$ is a family of at most $n-2$ subsets of $\{1, 2, \dots, n-1\}$. By induction, there is an element $x$ that, when removed from each set in $\mathcal A'$, keeps them distinct; verify that removing $x$ from each set in $\mathcal A$ also keeps them distinct.

(This actually still works for the stronger statement mentioned in bof's answer that "at most $n$ sets" works; you just need to strengthen the base case.)

Answer 2

In fact that your statement holds with "at most $n-1$ sets" improved to "at most $n$ sets". (And this is best possible; consider the $n+1$ sets $\{1,2,\dots,k\}$, $0\le k\le n$.)

Let $[n]=\{1,2,\dots,n\}$. Replace the sets with their characteristic functions, i.e., suppose $\mathcal F$ is a family of $n$ distinct functions $f:[n]\to\{0,1\}$; and assume for a contradiction that for each $x\in[n]$ there are two functions $f,g\in\mathcal F$ which differ only at $x$.

Let $K_n=(V,E)$ be a complete graph of order $n$ with vertex set $V$ and edge set $E$, and let the elements of $\mathcal F$ be indexed by $V$, i.e., $\mathcal F=\{f_v:v\in V\}$.

For each $x\in[n]$ choose an edge $e_x=uv\in E$ such that $f_u$ and $f_v$ differ only at $x$. Let $G$ be the spanning subgraph of $K_n$ with edge set $\{e_1,e_2,\dots,e_n\}$.

Since $G$ is a graph with $n$ vertices and $n$ edges, it contains a cycle, call it $v_1e_{x_1}v_2e_{x_2}\dots v_ke_{x_k}v_1$, where $x_1,x_2,\dots,x_k$ are distinct elements of $[n]$.

Since $f_{v_i}$ and $f_{v_{i+1}}$ differ only at at $x_i$, we have $f_{v_1}(x_k)=f_{v_2}(x_k)=\cdots=f_{v_k}(x_k)$, but $f_{v_k}(x_k)\ne f_{v_1}(x_k)$, which is absurd.