0
$\begingroup$

The question is as follows:

Harvard Law School courses often have assigned seating to facilitate the “Socratic method.” Suppose that there are $100$ first year Harvard Law students, and each takes two courses: Torts and Contracts. Both are held in the same lecture hall (which has $100$ seats), and the seating is uniformly random and independent for the two courses. Find the probability that no one has the same seat for both courses (exactly; leave the answer as a sum).

Here is my attempt:

$$P(no\; same\; seat) = 1 - P(all\; same\; seats)=1-(\frac{1}{100}+\frac{1}{99}+...+\frac{1}{1})=1-\sum_{i=1}^{100}{\frac{1}{i}}$$

So my thinking goes like this. The $1st$ student can choose any seat in the first class, thus, to choose the same seat in the second class would be $\frac{1}{100}$. The $2nd$ student can choose any of the $99$ remaining seats for the first class, thus, to choose the same seat in the second class it would be $\frac{1}{99}$.

However, upon looking at the solution, it seems like my answer is completely wrong. Does anyone know why my method is wrong?

$\endgroup$
4
  • 2
    $\begingroup$ To begin, $Pr(all~same~seats)$ would be $\frac{1}{100}\times \frac{1}{99}\times\cdots$ not $\frac{1}{100}+\frac{1}{99}+\cdots$. Next, the opposite event of "No same seats" is not "All same seats." The correct opposite event is "At least one same seat." $\endgroup$
    – JMoravitz
    May 26, 2016 at 19:19
  • 5
    $\begingroup$ Letting each student be labeled by the seat they picked in the first class, the question is essentially asking what the probability is of a Derangement occurring when considering the seating for the second class. $\endgroup$
    – JMoravitz
    May 26, 2016 at 19:20
  • $\begingroup$ Also, the expression for the probability in the attempt is $< 0$, a sure sign that something has gone awry. $\endgroup$
    – Travis Willse
    May 26, 2016 at 19:24
  • 1
    $\begingroup$ This is somewhat related: math.stackexchange.com/questions/1799767/… $\endgroup$
    – Travis Willse
    May 26, 2016 at 19:24

1 Answer 1

Reset to default
1
$\begingroup$

The problem is known as derangements, usually presented as passengers with tickets randomly assigned seats on a plane or guests receiving the wrong hats. Solution to it is an inclusion-exclusion principle/theorem. Obviously the total number of seatings is $100!$. How many do we need to exclude to get all 'wrong' ones? Assume at least 1 person has a correct seat. You have $\binom{100}{1}$ such allocations. For each there are $99!$ seatings for other students. After you've subtracted this from $100!$ you need to add back cases where at least two students, $\binom{100}{2} \times 98!$ and so on. Can you take it from here?

$\endgroup$

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.