Results 1 to 4 of 4

Math Help - help with annoying question that needs a bit of logic

  1. #1
    Newbie
    Joined
    Feb 2007
    Posts
    16

    help with annoying question that needs a bit of logic

    Im taking a SMC test soon and was looking over a past paper, but had a little trouble with q13:
    UKMT Senior Mathematical Challenge 2006 (scroll to q13)

    I ended up with 30 after some time, but am also suspicious that the answer could be 36.

    Either way, I would still like some kind of logical approach to tackle this problem as I rarely practice this kind of question.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,394
    Thanks
    1478
    Awards
    1
    I think that you are correct. The answer is 30.
    However, that depends on the fact that the two colourings that I have shown are counted as different. I am not at all sure that there are different.

    That figure is known in graph theory as an unlabeled graph.
    The second figure that I give is a labeled graph and in that case the two colourings are clearly different. This graph is known as a bipartite graph. We can be partitioned into two set of vertices: {A,C} & {B,D,E}. There is no edge between any two vertices is the same cell. There are 3 ways to colour A & C the same colour. Hence there are 2^3 ways to colour B, D, & E some other colour. That gives us 24 ways. But there are 6 ways to colour A & C with different colours leaving only one way to colour B, D, & E: a total of 30 for the labeled graph.

    I would argue that the question is not clear on the point.

    POST SCRIPT.
    I have just proved that there are only 24 ways to colour an unlabeled graph.
    That is not one of the answers. So we must conclude that the question is about a labeled graph.
    Attached Thumbnails Attached Thumbnails help with annoying question that needs a bit of logic-net1.gif  
    Last edited by Plato; October 29th 2007 at 03:01 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    well, i dont know if my logic is correct but i think it this way..
    if you label it a,...,e and take any arbitrary circle, then you can choose any color for it, hence, there are three possibilities, while depending on this situation, other circles are left with two colors to choose from. therefore, the answer is 48.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    Quote Originally Posted by Plato View Post
    .....
    This graph is known as a bipartite graph. We can be partitioned into two set of vertices: {A,C} & {B,D,E}. There is no edge between any two vertices is the same cell. There are 3 ways to colour A & C the same colour. Hence there are 2^3 ways to colour B, D, & E some other colour. That gives us 24 ways. But there are 6 ways to colour A & C with different colours leaving only one way to colour B, D, & E: a total of 30 for the labeled graph.
    ....
    i think, you have mistaken that A and C have 3 ways, note that if A have 3 ways, B, E have two ways, and that C are left with 2 ways (supposing B, E have same color, which is possible since they are not connected) since its color depends on B, D and/or E (you can also suppose that B, D and E have same color). This is also true for the other circles.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: January 5th 2010, 02:05 AM
  2. Annoying permutations question
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 14th 2009, 04:19 AM
  3. A very annoying and simple logic derivation problem.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 14th 2009, 08:01 PM
  4. Annoying Algebra/Indices question
    Posted in the Algebra Forum
    Replies: 7
    Last Post: January 10th 2009, 07:32 PM
  5. Annoying exam question
    Posted in the Algebra Forum
    Replies: 4
    Last Post: December 30th 2008, 02:08 PM

Search Tags


/mathhelpforum @mathhelpforum