Exercise 1.52

Question

A certain class has 20 students, and meets on Mondays and Wednesdays in a classroom with exactly 20 seats. In a certain week, everyone in the class attends both days. On both days, the students choose their seats completely randomly (with one student per seat). Find the probability that no one sits in the same seat on both days of that week.

fifthist x · Accepted Answer

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(\bigcup\limits_{i=1}^{20}A_{i}).$ 
By inclusion exclusion principle,

$$P\left(\bigcup\limits_{i=1}^{20}A_{i}ight) = \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}) - 
\cdots + (-1)^{21}P(A_{1} \cap \cdots \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.
ewline

Hence,

\begin{align*}
P\left(\bigcup\limits_{i=1}^{20}A_{i}ight) & = \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} - 
\cdots + \frac{1}{20!} 
onumber && \
& = 1 - \binom{20}{2}\frac{1}{20*19} + \binom{20}{3}\frac{1}{20*19*18} - 
\cdots + \frac{1}{20!} 
onumber && \
& = 1 - \frac{1}{2!} + \frac{1}{3!} - \cdots + \frac{1}{20!} 
onumber && \
& \approx 1 - e^{-1} 
onumber
\end{align*}

Sher · Answer

Solution of fifthistx is correct but the last step's been missed. Remember to subtract the final answer from one to obtain the probability that the question is asking for.

Exercise 1.52

Answers

Comments

Comments

Exercise 1.52

Answers

Comments

Comments

Add answer