Results 1 to 4 of 4

Math Help - Graph Theorey??

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    1

    Graph Theorey??

    FOr some reason our algebra II teacher gave us this on a quiz...its like what is this?? total brute force, but i cna seem to do it...i know a little bit of graph theory, but is there a easy way to do this?

    Say that there are "p" students in the classroom. For EACH integer number "q" from [0,10], one can choose 5 studnets such that exctly "q" of them know eachother. What is the minimal possible value for "p"/

    A. 9 B. 10 C. 11 D. 12 E. None of the above

    anybody know how to do this with Graph Theorey? What about normally?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by mbluo View Post
    FOr some reason our algebra II teacher gave us this on a quiz...its like what is this?? total brute force, but i cna seem to do it...i know a little bit of graph theory, but is there a easy way to do this?

    Say that there are "p" students in the classroom. For EACH integer number "q" from [0,10], one can choose 5 studnets such that exctly "q" of them know eachother. What is the minimal possible value for "p"/

    A. 9 B. 10 C. 11 D. 12 E. None of the above

    anybody know how to do this with Graph Theorey? What about normally?
    I suppose q must go from 0 to 5, not 10 (you can't select a group of five students, ten of whom know each other). Also, the case q=1, if it means anything at all, must be the same as q=0. (Five students, one of whom knows each other? That doesn't make any sense.)

    The class must contain a clique of five students who all know each other (a complete subgraph on 5 vertices, if you want to put it mathematically). Suppose it also contains four (sad) students, each of whom knows nobody else in the class. That gives a total of 9 students (choice A above). By selecting q students from the clique and 5q sad students (q=1,2,3,4,5) you can get all the possibilities required.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2009
    Posts
    2
    Quote Originally Posted by mbluo View Post
    FOr some reason our algebra II teacher gave us this on a quiz...its like what is this?? total brute force, but i cna seem to do it...i know a little bit of graph theory, but is there a easy way to do this?

    Say that there are "p" students in the classroom. For EACH integer number "q" from [0,10], one can choose 5 studnets such that exctly "q" of them IN PAIRS know eachother. What is the minimal possible value for "p"/

    A. 9 B. 10 C. 11 D. 12 E. None of the above

    anybody know how to do this with Graph Theorey? What about normally?
    Sorry, I meant in pairs, it is 10 students, since 5C2=10. I think this makes it harder.
    thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Ah, I see what you mean. That does make it harder. I don't have a systematic way to tackle this, but by trial and error I found a solution with nine students.

    Graph Theorey??-students.jpg

    You can get each number of pairs from 0 to 10 inclusive by selecting these sets of five vertices.
    For 0 pairs, BCEHJ.
    For 1 pair, BCEFJ.
    For 2 pairs, BFGHJ.
    For 3 pairs, ABFGJ.
    For 4 pairs, AFGHJ.
    For 5 pairs, AEFGJ.
    For 6 pairs, ACFGJ.
    For 7 pairs, ACFGH.
    For 8 pairs, CDEFG.
    For 9 pairs, ADEFG.
    For 10 pairs, ACDFG.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: August 5th 2011, 01:30 PM
  2. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  3. graph theorey
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 14th 2010, 06:41 AM
  4. graph theorey
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: April 13th 2010, 02:19 PM
  5. Replies: 4
    Last Post: February 8th 2010, 10:33 AM

Search Tags


/mathhelpforum @mathhelpforum