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

3 Asked on December 13, 2021

1 Asked on December 13, 2021 by rino

2 Asked on December 13, 2021 by mjoseph

1 Asked on December 13, 2021 by alexander-cska

analytic geometry coordinate systems linear algebra linear transformations matrices

1 Asked on December 13, 2021 by jon-g

1 Asked on December 13, 2021

3 Asked on December 13, 2021 by saganritual

1 Asked on December 10, 2021 by gcc

2 Asked on December 10, 2021 by yash-bhatia

2 Asked on December 10, 2021 by cheese12345

1 Asked on December 10, 2021 by paranoid

1 Asked on December 10, 2021 by sottoj

1 Asked on December 10, 2021 by billy-senders

2 Asked on December 10, 2021 by user6767509

1 Asked on December 10, 2021 by lce

absolute convergence convergence divergence infinite product

2 Asked on December 10, 2021

1 Asked on December 10, 2021 by mahesh87

1 Asked on December 10, 2021

0 Asked on December 10, 2021 by lightbulb

Get help from others!

Recent Questions

- 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?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

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

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir