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
    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$ 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$ 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
    Nov 12, 2020 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.