2
$\begingroup$

I am having trouble understanding how to solve this question:

Some five courses are offered in a semester. The group of students who take at least one of these courses consists of 155 students. There are 80 students registered in each course. For any two among these courses, there are precisely 40 students who take each of them. For any three of these courses, there are precisely 20 students who take each of them. For any four among these courses, there are precisely 10 students who take each of them. How many students in this group take every one among the five courses in this semester?

What I came up with is using a diagram I created to try and figure the problem out.

Course 1: has 40 people unaccounted for.

Course 2: has 30 people unaccounted for.

Courses 3 & 4 & 5: has 50 people unaccounted for.

By this process, only 30 people can take all five classes, but that leaves out 10 people in course 1 and 20 people in courses 3, 4 and 5.

This question comes from some inclusion/exclusion notes from my professor. The notes don't really explain inclusion/exclusion very well, or at least I don't understand it.

What am I missing? Can someone help me understand how to solve this question?

$\endgroup$
2
$\begingroup$

Although a Venn diagram can be very helpful in the case of $3$ events (courses), it is of diminishing helpfulness as the number of courses grows.

Call the courses $A,B,C,D,E$, or even $C_1,C_2,C_3,C_4,C_5$. There are $80$ people taking each of the $5$ courses.

If we add up the numbers of people taking the various courses, we get $5\cdot 80$. This is far bigger than the total of $155$ students. The reason is clear: we have "double-counted" the people who are taking both courses $A$ and $B$, also $A$ and $C$, and so on for all combinations of $2$ courses. There are $\binom{5}{2}=10$ such combinations.

Each such combination of $2$ courses is taken by $40$ students. If we subtract the number of courses taken by both $A$ and $B$, also the courses taken by $A$ and $C$, and so on, we should get closer to $155$. So the count of students should be closer to $5\cdot 80-10\cdot 40$.

But we have subtracted too much! For we have subtracted too many times the people who are taking $3$ of the courses. There are $\binom{5}{3}=10$ such combinations of courses, each taken by $20$ students, for a total of $10\cdot 20$. Thus the number of students should be closer to $5\cdot 80-10\cdot 40+10\cdot 20$.

However, we have added back too much, the $\binom{5}{4}=5$ combinations of $4$ courses. So we should subtract $5\cdot 10$.

The total number of students should therefore be close to $5\cdot 80-10\cdot 40+10\cdot 40-5\cdot 10$. This is almost right, except that we have subtracted once too many times the $x$ students taking all five courses. It follows that $$155=5\cdot 80-10\cdot 40+10\cdot 20-5\cdot 10+x.$$ Now we can find $x$.

$\endgroup$
  • $\begingroup$ That makes a lot of sense. I would have never thought to add and subtract the combinations like that. Thanks for the help; that was very informative! $\endgroup$ – datprog Mar 9 '14 at 16:59
  • $\begingroup$ You are welcome. The Inclusion/Exclusion process in this case is "too long" for a first exposure to PIE. I would have preferred $3$ courses, or $4$ at most. $\endgroup$ – André Nicolas Mar 9 '14 at 17:06

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.