12
$\begingroup$

jizz

I dont see what they mean by bijection of triples of subsets of $\{1, \ldots, 10\}$ and the $10\times3$ matrix with $0, 1$ entries?

How is that created?

$\endgroup$
  • $\begingroup$ You don't need to write $10x3$; you can write $10\times3$. I edited accordingly. ${}\qquad{}$ $\endgroup$ – Michael Hardy Mar 15 '15 at 13:42
  • $\begingroup$ @chi: The map is a bijection between the set of all ordered triples of subsets (without the conditions i and ii), and the set of all binary 10×3 matrices. $\endgroup$ – Henning Makholm Mar 15 '15 at 18:59
  • $\begingroup$ @HenningMakholm You are correct. I misread the very first part. $\endgroup$ – chi Mar 15 '15 at 19:05
10
$\begingroup$

For example, suppose the three sets are \begin{align} A_1 & = \{1,5,6,8\} \\ A_2 & = \{1,2,3,4,10\} \\ A_3 & = \{2,4,5,7,9,10\} \end{align} (Note that $A_1\cup A_2\cup A_3=\{1,2,3,4,5,6,7,8,9,10\}$ and $A_1\cap A_2\cap A_3=\varnothing$.)

Then the $10\times3$ matrix is $$ \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} $$ The first column of the matrix corresponds to the set $A_1$. It has a $1$ in the $1$st, $5$th, $6$th, and $8$th rows because the members of $A_1$ are $1,5,6,8$. Similarly the second and third columns correspond respectively to $A_2$ and $A_3$.

$\endgroup$
  • $\begingroup$ Michael Hardy (+1), at the end though. When they say: "The number of possibilities of each row of such a matrix is $2^3 - 2 = 6$" what possibility are they talking about? Also, how is it $2^3 - 2$ anyway? $\endgroup$ – Amad27 Mar 15 '15 at 16:12
  • $\begingroup$ There are eight $=2^3$ possible rows if you don't require the union of the three sets to contain all ten numbers and also don't require the intersection to be empty. Those eight are: $(0,0,0),\ (0,0,1),\ (0,1,0),\ (1,0,0),\ (0,1,1),\ (1,0,1),\ (1,1,0),\ (1,1,1)$. The requirement of non-intersection excludes $(1,1,1)$, and the requirement that all ten numbers be included excludes $(0,0,0)$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Mar 15 '15 at 18:21
  • $\begingroup$ I got that now =) But I dont understand something. How does the number of the possibilities of the rows of the matrices give the final answer? $\endgroup$ – Amad27 Mar 15 '15 at 18:22
  • $\begingroup$ You have six possibilities for the first row, six of the second, six for the third, etc., so you get $\underbrace{{}\,6\cdot6\cdots\cdots6\,{}}_{\text{10 factors}} = 6^{10}$ ways to fill in the blanks. ${}\qquad{}$ $\endgroup$ – Michael Hardy Mar 15 '15 at 18:33
  • $\begingroup$ There are three rows right? $$(abc); (abc); (abc)$$ $6$ possibilities for each row? $\endgroup$ – Amad27 Mar 15 '15 at 19:07
16
$\begingroup$

For any element $x \in \{1,\ldots,10\}$, in order to satisfy the constraints, $x$ must belong to either exactly 1 or exactly 2 of the sets $A_1,A_2,A_3$. This gives you 6 possibilities per element (why?), for a total of $6^{10}$ possibilities.

Don't bother with the matrix; this is just a fancy way of stating the same argument.

$\endgroup$
  • 5
    $\begingroup$ what have ever the matrices done to you? $\endgroup$ – abel Mar 15 '15 at 12:03
  • $\begingroup$ (+1) Great Answer @Yuval. But why only $1$ or $2$ of the sets $A_1, A_2, A_3$ though? $\endgroup$ – Amad27 Mar 15 '15 at 15:26
  • $\begingroup$ @Amad27 if an element $x$ belonged to all the sets then we would have $x \in A_1 \cap A_2 \cap A_3 \neq \emptyset$ $\endgroup$ – chi Mar 15 '15 at 16:09
  • $\begingroup$ @chi, using the matrix idea, they say: "The number of possibilities of each row is $2^3 - 2 = 6$." But which possibilities are they talking bout? $\endgroup$ – Amad27 Mar 15 '15 at 16:10
  • $\begingroup$ @Amad27 A generic row may be $(000),(001),(010),\ldots,(110),(111)$ for a total of $2^3$ rows -- yet two of them are impossible, as the book states. So we only get $2^3-2$ admissible rows. $\endgroup$ – chi Mar 15 '15 at 16:22

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.