Results 1 to 4 of 4

Thread: 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
    10
    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
    10
    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: Aug 5th 2011, 02:30 PM
  2. Replies: 0
    Last Post: Sep 25th 2010, 06:59 AM
  3. graph theorey
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 14th 2010, 07:41 AM
  4. graph theorey
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Apr 13th 2010, 03:19 PM
  5. Replies: 4
    Last Post: Feb 8th 2010, 11:33 AM

Search Tags


/mathhelpforum @mathhelpforum