This is a problem from the 1985 Putnam Exam:
Determine, with proof, the number of ordered triples $(A_1, A_2, A_3)$ of sets with
(i) $A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6,7,8,9,10\},$ and
(ii) $A_1 \cap A_2 \cap A_3 = \emptyset.$
Express your answer in the form $2^a3^b5^c7^d$ with $a,b,c,d$ being nonnegative integers.
My Proof:
The first condition says that each integer between $1$ and $10$ inclusive appears in at least one of the three sets. The second condition states that no integer between $1$ and $10$ inclusive appears in all three of the sets at the same time. These conditions lead to six possible placements of each of the integer $1$ through $10.$ Namely
$n \in A_1$ and $n \notin A_2$ and $n \notin A_3$
$n \notin A_1$ and $n \in A_2$ and $n \notin A_3$
$n \notin A_1$ and $n \notin A_2$ and $n \in A_3$
$n \in A_1$ and $n \in A_2$ and $n \notin A_3$
$n \in A_1$ and $n \notin A_2$ and $n \in A_3$
$n \notin A_1$ and $n \in A_2$ and $n \in A_3$
where the first three cases arise from n being in only one of the sets, the last three arise from n being in two, and n is any integer between $1$ and $10$ inclusive. We must choose one of these conditions for each integer $1$ through $10$ to make sure that each number appears in the union. This leads to $6^{10}$ possibilities. Writing this in the desired form, we get $2^{10}3^{10}5^07^0$.
I have tested different combinations and the results all seem to satisfy the conditions, but my concern is that this seems to be too simple, and I'm concerned that I'm missing something. Please let me know if I am, but with HINTS ONLY please. And if I am not missing anything, please let me know if this constitutes a rigorous proof, or if there is an alternate way to approach this problem.
Thanks
Your solution is correct; see John Scholes's very similar solution. This is an A1 problem, and these are often easier than the other problems.