Results 1 to 4 of 4

Math Help - math competition combinatorics question

  1. #1
    Newbie
    Joined
    Jun 2012
    From
    Moon
    Posts
    3

    Question 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).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jun 2012
    From
    Moon
    Posts
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,035
    Thanks
    49

    Re: math competition combinatorics question

    Quote Originally Posted by boorglar View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question from the ICAS Maths competition
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 20th 2010, 09:23 PM
  2. A nice problem for fun - Iranian math competition
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: December 7th 2009, 10:06 PM
  3. A problem from a grade 9 math competition
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 4th 2009, 05:38 PM
  4. math competition
    Posted in the Math Forum
    Replies: 8
    Last Post: August 14th 2008, 08:45 AM

Search Tags


/mathhelpforum @mathhelpforum