In how many ways can four students take two exams if none of the students can take both exams at the same time?

143 Views Asked by At

Four students are about to take two oral exams. Each exam is exactly 20 minutes long. In how many ways can those exams be conducted, if none of the students can take both exams at the same time?

I don't really know how to calculate all the possibilities of two "simultaneous" events. How can I combine them into one problem and solve this?

Edit: I think I came up with a solution: first I decide how the first exam will be conducted - there are $4!=24$ possible ways. Let's say it's the order ABCD. Then, using the inclusion-exclusion principle, I calculate that there are $9$ possibilities, in which none of the letters is in the same position as previously. So, the final answer is then $24 \cdot 9=216$?

1

There are 1 best solutions below

0
On BEST ANSWER

Your result is correct.

There are $4!$ ways of scheduling the first examination for the four students. For each such schedule, the second examination must be scheduled so that none of the students have both oral examinations in the same time slot. Therefore, the schedule for the second examination must be a derangement of the schedule for the first examination.

There are $4!$ possible schedules for the second examination, but we must exclude those in which one or more students has two examinations scheduled simultaneously. There are $\binom{4}{k}$ ways in which $k$ students could be scheduled to have the second examination at the same time as the first examination, and $(4 - k)!$ ways to schedule the remaining students for the second examination. Hence, by the Inclusion-Exclusion Principle, the number of ways to schedule the second examination so that no students have a conflict with the first examination is $$4! - \binom{4}{1}3! + \binom{4}{2}2! - \binom{4}{3}1! + \binom{4}{0}0!$$

Consequently, the number of ways to schedule the two examinations so that no students are scheduled to complete the two examinations at the same time is $$4!\left[4! - \binom{4}{1}3! + \binom{4}{2}2! - \binom{4}{3}1! + \binom{4}{0}0!\right]$$