3
$\begingroup$

I read this question on brilliant.org:

Winston must choose 4 courses for his final semester of school. He must take at least 1 science class and at least 1 arts class. If his school offers 4 science classes, 3 arts classes and 3 other classes, how many different choices for classes does he have?

My solution: His schedule can be written as {Science, Arts, Any, Any}, in which:

  • there are $4$ choices for the first Science class
  • there are $3$ choices for the first Arts class
  • Now that the requirements are satisfied, we can pool the rest of the classes, giving us $2$ slots for $3+(4-1) +(3-1) = 8$ classes, which can be filled in $8\times 7$ ways.

In total, he has $4\times 3\times 8\times 7 = 672$ ways to choose his classes. However, the website marked my answer as incorrect.

What's the correct answer and why?

$\endgroup$
  • 1
    $\begingroup$ Probably {Physics, Painting, Biology, Chemistry} is not a different schedule from {Biology, Painting, Chemistry, Physics}, but your enumeration scheme counts them as distinct. $\endgroup$ – Austin Mohr Jul 15 '13 at 4:14
1
$\begingroup$

Whenever I see the phrase "at least one", I am tempted to try to solve the complementary problem. Let's try to enumerate the schedules that either have no science class or no arts class.

If there is to be no science class, then we can choose our four classes from the remaining six options in $\binom{6}{4}$ ways.

If there is to be no arts class, then we can choose our four classes from the remaining seven options in $\binom{7}{4}$ ways.

A priori, we can't simply add these values together to get the number of schedules with no science class or no arts class, because we have counted twice the schedules that have no science class and no arts class. Fortunately for us, there are zero such schedules, since there are only three "other" classes. That is, we can't possibly fill out a four-class schedule without using a science or arts class.

Now, there are $\binom{6}{4} + \binom{7}{4}$ schedules that lack either a science class or an arts class. These are the bad schedules. We want to subtract this from the total number of unrestricted schedules, of which there are $\binom{10}{4}$.

Finally, the number of schedules that have at least one science class and at least one arts class is $$ \binom{10}{4} - \binom{7}{4} - \binom{6}{4} = 160. $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy