Putnam 1985, A1

Probability Level 5

Determine, with proof, the number of ordered triples $(A_{1}, A_{2}, A_{3})$ of sets which have the property that

(i) $A_{1} ∪ A_{2} ∪ A_{3} = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ , and
(ii) $A_{1} ∩ A_{2} ∩ A_{3} = ∅$ ,

where $∅$ denotes the empty set.

The answer is 60466176.

3 solutions

Pranshu Gaba
Jul 17, 2015

Each element $1, 2, 3, \ldots 10$ must belong to exactly one of the $6$ regions. By Rule of Product , it can be done in $6^{10} = \boxed{60466176}$ ways. $_\square$

Kenny Lau
Jul 19, 2015

This problem is done on the perspective of the numbers.

This problem is done by determining which set the numbers can be in. Let's take 1 as an example. It cannot be in neither sets, or (i) will not hold; it cannot be in all sets, or (ii) will not hold.

It either belongs or does not belong in set $A_1$ . There are three sets, giving $2\times2\times2=8$ choices. However, two aforementioned choices are discarded, leaving $6$ choices only for one number.

The same is true for all the integers from 1 to 10.

Therefore, the answer is $6$ multiplied itself $10$ times, or $6^{10}=\mbox{60466176}$ times.

Gauri shankar Mishra
Feb 1, 2016

Highly overrated ques

Putnam 1985, A1

The answer is 60466176.

3 solutions

0 pending reports