3
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

4
$\begingroup$

Assume that $|Z|\geqslant n$ but for any $x\in Z$ there exist indices $i(x)<j(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$.

$\endgroup$
2
  • $\begingroup$ The same question was asked )and got a similar answer) a couple years ago on math.se. $\endgroup$
    – bof
    Commented Nov 12, 2020 at 4:09
  • $\begingroup$ @bof Yes, I had a feeling that I have seen this already, but to find a reference was much harder than to remember and type a proof. $\endgroup$ Commented Nov 12, 2020 at 9:42
1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Nice counter example : What if the empty set is forbidden? $\endgroup$ Commented Nov 12, 2020 at 0:18
  • $\begingroup$ @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$. $\endgroup$
    – bof
    Commented Nov 12, 2020 at 4:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .