2
$\begingroup$

S is a set containing 10 elements. A subset P of S is chosen at random and the set S is reconstructed. Now another subset Q of S is chosen at random. Find the probabilities that-

$1)$ $P \cap Q$ contain exactly $3$ elements;
$2)$ $P \cup Q$ contain exactly $4$ elements;
$3)$ $P \cup Q = S$

Please try to give a good explanation. Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ Say something about what you think about this. $\endgroup$ – SchrodingersCat Dec 5 '16 at 16:25
  • 1
    $\begingroup$ What do you mean by "the set S is reconstructed"??? $\endgroup$ – barak manos Dec 5 '16 at 16:32
  • $\begingroup$ It means the elements of P are replaced. $\endgroup$ – Rohan Dec 5 '16 at 16:33
  • $\begingroup$ @barakmanos Here the word "reconstruted" is used just to make sure that choosing elements for P does not affect the choosing process for Q $\endgroup$ – Sujan Dutta Dec 5 '16 at 17:07
  • $\begingroup$ There is no probability associated with the question. What does choosing a subset of $S$ as random mean? Is each of the $2^{10}$ different subsets equally likely to be chosen? Or do the elements of $S$ have probabilities $p_1, p_2, \ldots, p_{10}$ and the probability of a choosing a subset $Q$ is just the probability of the event $Q$? $\endgroup$ – Dilip Sarwate Dec 5 '16 at 17:11
2
$\begingroup$

I’ll get you started. $S$ has $10$ elements, so it has $2^{10}=1024$ subsets. Thus, there are $2^{10}\cdot 2^{10}=2^{20}$ possible ordered pairs $\langle P,Q\rangle$ of subsets that you could pick, and they are all equally likely. To find the probability that $|P\cap Q|=3$, therefore, we need to count the ordered pairs $\langle P,Q\rangle$ such that $|P\cap Q|=3$ and divide that number by $2^{20}$.

One way to do this is to count the pairs that have each possible $3$-element intersection. Let $T$ be a $3$-element subset of $S$; we want to count the ordered pairs $\langle P,Q\rangle$ of subsets of $S$ such that $P\cap Q=T$. The trick here is to realize that each one of these pairs comes from a division of $S\setminus T$ into $3$ pairwise disjoint sets: for each element $k$ of $S\setminus T$ we must decide whether $k$ is to be in $P$, in $Q$, or in neither $P$ nor $Q$. $S\setminus T$ has $7$ elements, so we’re making a $3$-way choice $7$ times; this can be done in $3^7$ different ways. Thus, there are $3^7$ pairs $\langle P,Q\rangle$ such that $P\cap Q=T$. And there are $\binom{10}3$ possible choices for $T$, so there must altogether be $\binom{10}33^7$ ordered pairs $\langle P,Q\rangle$ of subsets of $S$ such that $|P\cap Q|=3$. The probability of getting such a pair is therefore

$$\frac{\binom{10}33^7}{2^{20}}=\frac{262,440}{1,048,576}=\frac{32805}{131072}\approx0.2503\;.$$

The other two parts can be analyzed using basically the same ideas. You’ll be dividing up either $P\cup Q$ or $S$ into $3$ parts.

$\endgroup$
  • $\begingroup$ Thank you....now I get it.... $\endgroup$ – Sujan Dutta Dec 7 '16 at 18:51
  • $\begingroup$ @Sujan: You’re welcome; glad it helped. $\endgroup$ – Brian M. Scott Dec 7 '16 at 21:40

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.