# Prove that cardinality of the symmetric difference of subsets less than 3

We given a set $B = \{0,1,2,3,4,5,6,7,8,9\}$.
Task is to prove, that amongst 100 arbitrary picked subsets of set B there are at least two subsets $S_x$ and $S_y$, such as $| S_x \Delta S_y | \le 2$

I started with determining possible cardinalities of the subsets. Having that figured out I have realized that it isn't actually matter. So I am out of my depth to find a right track to solve it.

• ? Isn't that true for any subsets containing only one element? – user2345215 Mar 5 '14 at 9:54
• @user2345215 Correct. My mistake. I forgot to mention important part of the task. We have to prove that statement holds for any 100 subsets of B. I already fixed an description. – wf34 Mar 5 '14 at 10:20

Each subset $S_x \subseteq \{0,1,\dots, 9\}$ can be mapped to a vector $\vec{x} \in \{0,1\}^{10}$ by defining $x_i = 0$ if $i \notin S_x$ and $x_i = 1$ otherwise, for $i = 0, \dots, 9$. In terms of such vectors, the condition $|S_x \Delta S_y| \leq 2$ then translates to a Hamming distance of at most $2$ between the vectors $\vec{x}$ and $\vec{y}$. So if $100$ subsets of $B$ exist with pairwise symmetric difference more than $2$, then there exist $100$ vectors in $\{0,1\}^{10}$ with pairwise Hamming distance of at least $3$. In other words: there then exists an error-correcting code of size $100$ in $\{0,1\}^{10}$ with minimum distance at least $3$. Or, if we let $A_q(n,d)$ denote the maximum number of $q$-ary code words of dimension $n$ with minimum distance $d$, this translates to $$A_2(10,3) \stackrel{?}{\geq} 100.$$

To prove that no such code exists, one can use various well-known bounds from coding theory. For instance, the Singleton bound tells you that $$A_q(n,d) \leq q^{n-d+1} \quad \Rightarrow \quad A_2(10,3) \leq 2^8 = 256.$$ Obviously, that doesn't help us prove $A_2(10,3) < 100$. A better bound is obtained via the Hamming bound: $$A_q(n,d) \leq \frac{q^n}{\sum_{k=0}^{(d-1)/2} \binom{n}{k} (q - 1)^k} \quad \Rightarrow \quad A_2(10,3) \leq \frac{2^{10}}{1 + 10} < 94.$$ Since the upper bound on $A_2(10,3)$ is thus lower than $100$, it follows that no $100$ subsets of $B$ with pairwise symmetric difference at least $3$ can exist. Hence, given $100$ subsets, there must be two subsets with symmetric difference at most $2$.

There must be 3 conditions;

1) $S_x$ and $S_y$ subsets are the same. $S_x = S_y$

2) $S_x$ and $S_y$ subsets don't have same elements.So, they are different. $S_x \cap S_y=\emptyset$

3) $S_x$ and $S_y$ subsets have some same elements. $S_x \cap S_y \neq \emptyset$

And $| S_x \Delta S_y |=| S_x | + | S_y | - 2|S_x \cap S_y|$ formula is true.

Examples:

1)$| S_x | = | S_y | = |S_x \cap S_y|$ then $| S_x \Delta S_y |=2|S_x \cap S_y|- 2|S_x \cap S_y|=0\le 2$

2) It means that $S_x$ and $S_y$ subsets have 1 element and it is obvious that they must be different. Then consider the $|S_x \cap S_y|=0$ we can get the $| S_x \Delta S_y |=| S_x | + | S_y |- 2*0=| S_x | + | S_y |\geq 2$

if we look at $S_x$={0} and $S_y$={1} we get the $| S_x \Delta S_y |=| S_x | + | S_y | - 2|S_x \cap S_y|=1+1-2*0=2$

3) For example, $S_x$={0,1} and $S_y=${1,2} we get $| S_x \Delta S_y |=| S_x | + | S_y | - 2|S_x \cap S_y|=2+2-2*1=2$

At least they have 1 different.On other hand, $| S_x \Delta S_y |=| S_x/S_y | + | S_y/S_x |\geq 1+1=2$ So $| S_x \Delta S_y |\geq 2$

In conclusion this sets must consist of at least 1 different element or they must be equal.

• If you use LaTeX, then use dollar-signs as well. – TMM Mar 5 '14 at 10:27
• I am new in LaTeX how can I learn all symbols what I must use.Please, give me some information. – Elvin Mirzayev Mar 5 '14 at 10:29
• @ElvinMirzayev just wrap all yours latex equations with dollar sign from both sides. Then it should start render properly – wf34 Mar 5 '14 at 10:30
• If you write $S_x \cap S_y \neq \emptyset$ (so with dollar-signs) it will automatically render as $S_x \cap S_y \neq \emptyset$. – TMM Mar 5 '14 at 10:30
• @ElvinMirzayev You probably want to fix the formulas to get your answer more readability. I went thought your conclusions and agree with them, but task is to prove that such $S_x$ and $S_y$ exists in any 100 subsets of B. – wf34 Mar 5 '14 at 10:45