MHB Can You Help Me Count the Different Ways to Organize My List?

[veronica1999]

First I tried to make an organized list but I kept on messing up.
Then I tried to subtract the cases that don't work but this also was not a good approach.
Could I get some help on setting up the cases I should be considering?

 

[Sudharaka]

First I tried to make an organized list but I kept on messing up.
Then I tried to subtract the cases that don't work but this also was not a good approach.
Could I get some help on setting up the cases I should be considering?

Hi veronica1999, :)

Under the given constraints each girl should have 2 or 3 songs that she likes. If a girl likes only one of the songs, then the following condition cannot be satisfied.

For each of the three pairs of the girls, there is at least one song liked by those two girls but disliked by the third.

Similarly, if a girl likes all four of the songs, then the condition,

No song is liked by all three.

cannot be satisfied.

Let me name the girls as A, B and C. Now consider each case,

[TABLE="class: grid, width: 550, align: center"]
[TR]
[TD="align: center"][/TD]
[TD="align: center"]No. of songs liked by A[/TD]
[TD="align: center"]No. of songs liked by B[/TD]
[TD="align: center"]No. of songs liked by C[/TD]
[/TR]
[TR]
[TD="align: center"]1)[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[/TR]
[TR]
[TD="align: center"]2)[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[/TR]
[TR]
[TD="align: center"]3)[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]3[/TD]
[/TR]
[TR]
[TD="align: center"]4)[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[/TR]
[TR]
[TD="align: center"]5)[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[/TR]
[TR]
[TD="align: center"]6)[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[/TR]
[TR]
[TD="align: center"]7)[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[/TR]
[/TABLE]

If we consider the first case,

'A' likes 3 songs out of 4. There are, \({}^4C_{3}\) ways to choose these three songs. 'B' also likes 3 songs out of 4. Suppose 'B' likes the same three songs that 'A' likes. Then 'C' should like a song that both 'A' and 'B' like. This cannot happen as it is given that,

No song is liked by all three.

Therefore, 'B' should like only two songs that 'A' like, and the other one is the one that 'A' dislikes. The number of ways to choose the two songs(out of the 3 that A likes) is given by, \({}^3C_{2}\). Now if you think carefully you will see that only a pair of songs are left for 'C' to like, without violating the given criteria.

Therefore the total number of possibilities for the first case \(={}^4C_{3}\times{}^3C_{2}\)

If the above explanation is hard to visualize the diagram that I have attached may help. The fours songs are denoted by 1,2,3 and 4.

Likewise I have considered each case separately. These are given in the following table.[TABLE="class: grid, width: 550, align: center"]
[TR]
[TD="align: center"][/TD]
[TD="align: center"]No. of songs liked by A[/TD]
[TD="align: center"]No. of songs liked by B[/TD]
[TD="align: center"]No. of songs liked by C[/TD]
[TD="align: center"]No. of Ways to choose the songs[/TD]
[/TR]
[TR]
[TD="align: center"]1)[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]\({}^4C_{3}\times{}^3C_{2}\)[/TD]
[/TR]
[TR]
[TD="align: center"]2)[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]\({}^4C_{3}\times{}^3C_{1}\)[/TD]
[/TR]
[TR]
[TD="align: center"]3)[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]\({}^4C_{2}\times{}^2C_{1}\)[/TD]
[/TR]
[TR]
[TD="align: center"]4)[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]\({}^4C_{3}\times{}^3C_{1}\times{}^2C_{1}\)[/TD]
[/TR]
[TR]
[TD="align: center"]5)[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]\({}^4C_{2}\times{}^2C_{1}\times{}^2C_{1}\)[/TD]
[/TR]
[TR]
[TD="align: center"]6)[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]\({}^4C_{2}\times{}^2C_{1}\times{}^2C_{1}\)[/TD]
[/TR]
[TR]
[TD="align: center"]7)[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]\({}^4C_{2}\times{}^2C_{1}\times{}^2C_{1}\)[/TD]
[/TR]
[/TABLE]

Therefore the total number of different ways \(=\left({}^4C_{3}\times{}^3C_{2}\right)+\left({}^4C_{3}\times{}^3C_{1}\right)+\left({}^4C_{2}\times{}^2C_{1}\right)+\left({}^4C_{3}\times{}^3C_{1} \times{}^2C_{1}\right)+3\left({}^4C_{2}\times{}^2C_{1}\times{}^2C_{1}\right)=132\)

Kind Regards,
Sudharaka.

​

 

[veronica1999]

Thank you!
You are really awesome.:D