Math competition combinatorics problem help?

[Boorglar]

This is a question taken from the AMC 2012 12 B exam held in February.

I did not answer it during the exam, but now I try to complete all of it at home. I thought I found a solution, but it is not in the proposed choices, and so I am really lost... And the solution is not available for this question, for some reason.

" Amy, Beth and Jo listen to four different songs and discuss which ones they like. No song is liked by all three. Furthermore, 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. In how many ways is this possible?

(A) 108 (B) 132 (C) 671 (D) 846 (E) 1105 "


My answer was 168, which is not in the list. Apparently, the answer is supposed to be (B).

 

[Boorglar]

This is my attempt at a solution:

First, we can see that a maximum of 2 songs can be liked by any pair of girls at the same time, because if 3 songs are liked by, say, both A and B, then J cannot like any of these (otherwise it would be liked by all 3 girls). So J likes only one song. But she must share this song with A and with B, again a contradiction.

Now consider the case where only one song is shared for each pair. The first pair has 4 possible songs. Then the second pair has 3 possible songs (since the first song cannot be liked also by the second pair). Then the third pair has 2 possible songs (again for this reason). Finally, the last song will be either liked by A, B, J or nobody at all (but not two people at once, because I consider the case where only one song is shared in each pair). This makes 4 additional possibilities. In total, there are 4*3*2*4 possibilities in this case.

Now consider the case where at least one pair shares two songs. Only one pair can share two songs together, otherwise, say A and B like songs 1 and 2, and B and J like songs 3 and 4. Then the pair A and J will like either 1, 2, 3 or 4 but then this song will be liked by everyone, which is impossible. So there is only one pair sharing two songs. There are 3 pairs, so 3 possibilities for the pair that shares two songs. Now for this pair, there are 4 possibilities for the 1st song, and 3 possibilities for the second song. The second pair has two possibilities for their own song, which leaves only one possibility for the third pair. In total, there are 3*4*3*2*1 possibilities in this case.

These are all the possible cases, so adding everything we get 4*3*2*4 + 3*4*3*2*1 = 96 + 72 = 168.

So there are 168 ways possible.

 

[haruspex]

Now for this pair, there are 4 possibilities for the 1st song, and 3 possibilities for the second song.

But the order in which they like them doesn't matter.

 

[Boorglar]

O_O you're right! I hadn't thought about that... So it is the binomial coefficient (4 2) = 6, instead of 4*3=12 because we care about the combinations.

Thanks, I really should have seen that, but it's tricky...