# 1985 Putnam A1 Solution

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?

• You don't need to write $10x3$; you can write $10\times3$. I edited accordingly. ${}\qquad{}$ – Michael Hardy Mar 15 '15 at 13:42
• @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. – Henning Makholm Mar 15 '15 at 18:59
• @HenningMakholm You are correct. I misread the very first part. – chi Mar 15 '15 at 19:05

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

• 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? – Amad27 Mar 15 '15 at 16:12
• 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{}$ – Michael Hardy Mar 15 '15 at 18:21
• 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? – Amad27 Mar 15 '15 at 18:22
• 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{}$ – Michael Hardy Mar 15 '15 at 18:33
• There are three rows right? $$(abc); (abc); (abc)$$ $6$ possibilities for each row? – Amad27 Mar 15 '15 at 19:07

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.

• what have ever the matrices done to you? – abel Mar 15 '15 at 12:03
• (+1) Great Answer @Yuval. But why only $1$ or $2$ of the sets $A_1, A_2, A_3$ though? – Amad27 Mar 15 '15 at 15:26
• @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$ – chi Mar 15 '15 at 16:09
• @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? – Amad27 Mar 15 '15 at 16:10
• @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. – chi Mar 15 '15 at 16:22