Mathematics Asked by ijm on November 30, 2020

Consider this problem:

A question paper on mathematics consists of twelve questions divided into three parts A, B

and C, each containing four questions. In how many ways can an examinee answer five

questions, selecting at least one from each part?

I solved this problem taking a case-by-case approach. The examinee could pick 1, 1 and 3 questions, or 2, 2 and 1 questions, from the three sections. Number of ways of picking these questions is ${4 choose 1} times {4 choose 1} times {4 choose 3}$ and ${4 choose 2} times {4 choose 2} times {4 choose 1}$.

We will now multiply the two numbers by $3!/2!=3$ to find the number of permutations. The correct answer is ${4 choose 1} times {4 choose 1} times {4 choose 3} times 3 + {4 choose 2} times {4 choose 2} times {4 choose 1} times 3 = 624$.

Obviously, this approach is not generalizable because it involves thinking about the possible distributions. If the number of questions in each section or the number of sections was large enough, it would be very time-consuming to employ this method. What would be an alternative approach that scales well?

We could use the Inclusion-Exclusion Principle.

There are $binom{12}{5}$ ways to select five of the twelve questions on the question paper. From these, we must subtract those selections which do not contain at least one selection from each section.

There are three ways to exclude a section and $binom{8}{5}$ ways to select five of the remaining eight questions.

Since it is not possible to exclude two of the sections and still select five questions from the remaining four questions, we are done.

$$binom{12}{5} - binom{3}{1}binom{8}{5} = 624$$

Suppose the examinee only had to answer four of the twelve questions, but was still required to answer at least one question from each part.

Observe that the examinee must answer two questions from one part and one from each of the others, which can be done in $$binom{3}{1}binom{4}{2}binom{4}{1}binom{4}{1} = 288$$ since there are three ways to choose the section from which two questions will be answered, $binom{4}{2}$ ways to choose two questions from that section, and four ways to choose a single question from each of the other sections.

By the Inclusion-Exclusion Principle, there are $$binom{12}{4} - binom{3}{1}binom{8}{4} + binom{3}{2}binom{4}{4} = 288$$ admissible ways to select the questions since there are $binom{12}{4}$ ways to select four questions, three ways to exclude one section and $binom{8}{4}$ ways to select four of the remaining eight questions, and $binom{3}{2}$ ways to exclude two sections and $binom{4}{4}$ ways to answer all four of the remaining four questions. The reason we must add the last term is that we subtracted each selection in which all the selected questions are drawn from one section twice, once for each way of designating one of the other two sections as the excluded section.

While the first method of solving this problem is simpler in this case, the Inclusion-Exclusion Principle can be more readily applied if the number of questions in each section ot the number of sections were large.

Correct answer by N. F. Taussig on November 30, 2020

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP