math competition combinatorics question

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).

Re: math competition combinatorics question

My solution was:

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.

Re: math competition combinatorics question

Quote:

Originally Posted by

**boorglar** Now consider the case where at least one pair shares two songs. Only one pair can share two songs together...

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

... making 12 ordered pairs of songs, but you want only the number of unordered pairs of songs (for this pair of girls).

Re: math competition combinatorics question

You can also check the AoPS forums. I took this exam last year and also struggled with this question (I suck at combinatorics, but still passed with a 108). I'll probably look at this question again.