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
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 '20 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$ – Fedor Petrov Nov 12 '20 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$ – Jérôme JEAN-CHARLES Nov 12 '20 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 '20 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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