# For $n$ different sets whose union has size $n+1$ ,can you remove the same point from each set while retaining their difference

Let $$(A_i)_{i=1}^{n}$$ be $$n$$ different sets. Say $$Z := \bigcup_{i=1}^{n}A_i$$.
Q1: Is it true that if $$|Z| \gt n$$ then you can find $$x \in Z$$ such that the $$(A_i-{x)}$$ are still all different?
Q2: If $$|Z|\gt n-1$$ is a sufficient hypothesis, is this tight?

Remark : if Q1 is true then of course you can find $$X \subset Z$$ such that $$|Z-X|=n$$ and all $$A_i-X$$ are different.
The motivation (alternative formulation) is: working in the alphabet $${ \{ 0,1 \}}$$:
If you have $$n$$ different words each of size $$n+1$$, can you find $$i \in [1,n]$$ so that removing the $$i$$ th letter of each word still produces $$n$$ different words?

Assume that $$|Z|\geqslant n$$ but for any $$x\in Z$$ there exist indices $$i(x) such that $$A_{i(x)}\triangle A_{j(x)}=\{x\}$$ (where $$\triangle$$ stands for the symmetric difference). The graph on $$\{1,2,\ldots,n\}$$ with edges $$(i(x),j(x))$$ for all $$x\in X$$ contains a cycle, since the number of edges is not less than the number of vertices. But such a cycle clearly can not exist, a contradiction.
If $$|Z|=n-1$$, you may consider the sets $$\emptyset$$ and $$\{1,2,\ldots,i\}$$ for $$i=1,2,\ldots,n-1$$.
For Q2, $$n-1$$ is not sufficient because given $$A_0=\emptyset$$ and $$A_i$$ as singletons—say $$A_i=\{i\}$$—, then $$|Z|=n-1$$ but then $$A_i-j=A_0$$ if $$i=j$$.
• @JérômeJEAN-CHARLES If the empty set is forbidden, just replace Jack L.'s sets $A_i$ with their complements $\{1,2,\dots,n-1\}\setminus A_i$. That will do the trick if $n\ge3$. – bof Nov 12 '20 at 4:06