5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ ? Isn't that true for any subsets containing only one element? $\endgroup$ – user2345215 Mar 5 '14 at 9:54
  • $\begingroup$ @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. $\endgroup$ – wf34 Mar 5 '14 at 10:20
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If you use LaTeX, then use dollar-signs as well. $\endgroup$ – TMM Mar 5 '14 at 10:27
  • $\begingroup$ I am new in LaTeX how can I learn all symbols what I must use.Please, give me some information. $\endgroup$ – Elvin Mirzayev Mar 5 '14 at 10:29
  • $\begingroup$ @ElvinMirzayev just wrap all yours latex equations with dollar sign from both sides. Then it should start render properly $\endgroup$ – wf34 Mar 5 '14 at 10:30
  • $\begingroup$ 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$. $\endgroup$ – TMM Mar 5 '14 at 10:30
  • 1
    $\begingroup$ @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. $\endgroup$ – wf34 Mar 5 '14 at 10:45

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.