4
$\begingroup$

Here's the question:

"A congress will be attended by two representatives from Colombia, three from Chile, four from Argentina and five from Brazil. Each of the $14$ representatives prepared their own speech, but only $6$ will be drawn to speak. If the draw rule provides that each of the four countries must have at least one representative speaking, the number of different ways to compose the set of six speeches that will be heard at the congress, regardless of the order, is equal to how much?"

I've been working on this question for two weeks. My answer is $1450$ - but I solved it via brute force. I literally counted all the possibilities of the rule being broken and subtracted from the $3003$ possibilities to form groups of 6 people out of $14$.

I tried to look at the problem with fewer countries, and fewer choices. It helped me to count, but I couldn't decipher the pattern with which the problem changes when adding a new representative or a new country.

Can someone help me?

$\endgroup$
5
  • 2
    $\begingroup$ With the conditions you gave, there are two possibilities: 1) there is one country with three representatives chosen and all others get one, 2) there are two countries with two representatives and two with one. Can you see why this is true? Looking at these two cases separately might help $\endgroup$
    – Slugger
    Sep 16 at 10:08
  • $\begingroup$ Clarification requested. Are the people that represent a specific country distinguishable? That is, in the distributions that involve exactly 1 person from Colombia, is it appropriate to apply the factor of $\binom{2}{1}$, since there are $2$ ways of selecting which Colombian will be chosen? $\endgroup$ Sep 16 at 10:11
  • 1
    $\begingroup$ @user2661923 I think the people are distinguishable, since it mentions that each people prepare a speech and we are asked to count the number of possible set of speeches $\endgroup$ Sep 16 at 10:18
  • $\begingroup$ @Slugger thank you! This helped a lot! $\endgroup$
    – Kaio Diniz
    Sep 16 at 10:27
  • 1
    $\begingroup$ @user2661923 Yep, people are distinguishable. Their speeches are different. :) $\endgroup$
    – Kaio Diniz
    Sep 16 at 10:27
5
$\begingroup$

A nice way to do this is to use the principle of inclusion-exclusion. Take all $\binom{14}6$ ways to choose $6$ people, then for each country, subtract the assignments where that country has no chosen representatives. The result is $$ \binom {14}6 -\underbrace{\binom{12}6}_{\text{Columbia missing}} -\underbrace{\binom{11}6}_{\text{Chile missing}} -\underbrace{\binom{10}6}_{\text{Argentina missing}} -\underbrace{\binom{9}6}_{\text{Brazil missing}} $$ However, there is a problem. Arrangements with two missing countries will be subtracted twice in the above computation. To fix this, we must add these doubly-subtracted arrangements back in. To the above, we add $$ +\underbrace{\binom{9}{6}}_{\text{Columbia + Chile}} +\underbrace{\binom{8}{6}}_{\text{Columbia + Argentina}} +\underbrace{\binom{7}{6}}_{\text{Columbia + Brazil}} +\underbrace{\binom{7}{6}}_{\text{Chile + Argentina}} +\underbrace{\binom{6}{6}}_{\text{Chile + Brazil}} $$ At this point, we are done! We would not be done if there were any arrangements counted by $\binom{14}6$ with three countries missing, but that is not possible.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you so much, Mike! Beautiful solution. And to top it off, I better understood the inclusion-exclusion principle. Thank you! $\endgroup$
    – Kaio Diniz
    Sep 16 at 14:53
3
$\begingroup$

Fo a second way , use generating functions. If there is at least one president in each country , then

Genereting function of Columbia : $$\binom{2}{1}x^1 +\binom{2}{1}x^2$$

Genereting function of Chile :

$$\binom{3}{1}x^1 + \binom{3}{2}x^2 +\binom{3}{3}x^3$$

Genereting function of Argentina :

$$\binom{4}{1}x^1 + \binom{4}{2}x^2 +\binom{4}{3}x^3 + \binom{4}{4}x^4$$

Genereting function of Brasil :

$$\binom{5}{1}x^1 + \binom{5}{2}x^2 +\binom{5}{3}x^3 + \binom{5}{4}x^4 +\binom{5}{5}x^5$$

Now, find the expansion of them and find the coefficient of $x^6$

Calculation in this link

So , answer is $1450$ , you are right !.By the way the binomial coefficients means the number of selection among candidates.For example , $\binom{5}{2}x^2$ means number of selection of two president among $5$ in Brasil.

Do you get the idea ?

$\mathbf{\text{MORE CLARIFICATION:}}$ In given link ,you will see that binomial expansions like $((1+x)^2 -1)$ , we know that when we expand it , it will give $2x +x^2$ . I wanted to write them clear form , but wolfram could not calculate them because of the lenght of expansion.Secondly , by the form of generating function (we started from $x^1$) , the number of president more than $3$ is automatically prevented.

$\endgroup$
4
  • 1
    $\begingroup$ Can you explain where the binomial coefficients are in the calculation link , and how more than $3$ from any country has been prevented ? $\endgroup$ Sep 16 at 12:39
  • $\begingroup$ @trueblueanil i add clarification, thanks.. $\endgroup$
    – Bulbasaur
    Sep 16 at 12:46
  • 1
    $\begingroup$ Nicely tackled the bad wolf, +1 $\endgroup$ Sep 16 at 12:49
  • $\begingroup$ @trueblueanil wolf sometimes lazy for calculating , thanks a lot $\endgroup$
    – Bulbasaur
    Sep 16 at 12:50
1
$\begingroup$

$$\sum_{\sum_{i=1}^4 \alpha_i=6\\1\leq \alpha_i \leq i+1}\binom{2}{\alpha_1}\binom{3}{\alpha_2}\binom{4}{\alpha_3}\binom{5}{\alpha_4}=1450$$

$\endgroup$
3
  • 1
    $\begingroup$ Question may be ambiguous. See my comment following the question. $\endgroup$ Sep 16 at 10:13
  • 3
    $\begingroup$ Come on! People will be distinguishable. $\endgroup$
    – Ashiq
    Sep 16 at 10:19
  • $\begingroup$ Thank you! Now I know my answer is probably right. But I lack the knowledge to understand your resolution. Anyway, thank you very much! $\endgroup$
    – Kaio Diniz
    Sep 16 at 10:31

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.