problem 52

1.5.2 problem 52

Let $A_{i}$ be the event that the $i$ -th student takes the same seat on both days. The desired probability then is $1 - P (20 ⋃ i = 1 A_{i}) .$ By inclusion exclusion principle,

$P (20 ⋃ i = 1 A_{i}) = \sum_{i} P (A_{i}) - \sum_{i < j} P (A_{i} \cap A_{j}) + \sum_{i < j < k} P (A_{i} \cap A_{j} \cap A_{k}) - \dots + {(- 1)}^{21} P (A_{1} \cap \dots \cap A_{20})$ ,
where $P (A_{i}) = \frac{19!}{20!}$ , $P (A_{i} \cap A_{j}) = \frac{18!}{20!}$ and so on by naive definition of probability.
Hence,

\begin{matrix} P (⋃_{i = 1}^{20} A_{i}) & = \sum_{i = 1}^{20} \frac{1}{20} - \sum_{1 \leq i < j \leq 20} \frac{1}{20 * 19} + \sum_{1 \leq i < j < k \leq 20} \frac{1}{20 * 19 * 18} - \dots + \frac{1}{20!} = 1 - (\frac{20}{2}) \frac{1}{20 * 19} + (\frac{20}{3}) \frac{1}{20 * 19 * 18} - \dots + \frac{1}{20!} = 1 - \frac{1}{2!} + \frac{1}{3!} - \dots + \frac{1}{20!} \approx 1 - e^{- 1} \end{matrix}

[next] [prev] [prev-tail] [front] [up]