Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Brain teaser I can't get out

  1. Jun 19, 2009 #1

    rock.freak667

    User Avatar
    Homework Helper

    this is how I was told

    At a party, each person knows exactly 22 others. For any pair of people (X & Y) who knew one another, there was no other person at the party that they both knew.

    For any pair of people, X and Y, who did not know one another, there were
    exactly 6 other people that they both knew.

    How many people were at the party?


    How does one start this?
     
  2. jcsd
  3. Jun 20, 2009 #2
    Curses, you've infected me with this now too! :smile:

    I'm not sure how to solve it, but here's a thought.

    Say there are N people.
    Pick a person X. X knows 22 people and doesn't know M people.
    Note that M+22+1=N.
    Let's call the group of people X knows A (having 22 members), and the group of people X doesn't know B (it has M people).
    Each member of A must know 22 people himself. However, the members of A can't know each other because of assumption #2 in your post. Hence each person in A knows X, plus 21 other people in B. This means there are "21*22 connections" going from A to B.
    Similarly, each person in B must know 6 people in A (because of assumption #1). That is a total of "6*M connections".

    It seems to me the number of outgoing connections from M must equal the number of incoming connections, so 6*M = 21*22, yielding M=77, so

    N = 1+22+M = 23+77 = 100.

    Does this make sense? (Do you have the solution?)

    -----
    Assaf
    http://www.physicallyincorrect.com" [Broken]
     
    Last edited by a moderator: May 4, 2017
  4. Jun 20, 2009 #3

    rock.freak667

    User Avatar
    Homework Helper

    Sorry, I don't have the answer...I didn't even know how to begin to solve this :frown:
     
  5. Jun 20, 2009 #4
    Argh, the suspense ... can you ask the person who gave you this question? I've got to know the answer! :smile:

    I've tried googling the problem but all I could find is Ramsey theory, which is definitely not what we're looking at.


    -----
    Assaf
    http://www.physicallyincorrect.com" [Broken]
     
    Last edited by a moderator: May 4, 2017
  6. Jun 20, 2009 #5
    This looks quite straight forward but when I tried working this out I ended up with a paper full of calculations that dont make sense lol .if you get the answer please i would like to know
     
  7. Jun 22, 2009 #6

    rock.freak667

    User Avatar
    Homework Helper

    the person who gave it to me doesn't know the answer. But he got 84.
     
  8. Jun 22, 2009 #7
    oh ok ill try and see if me and my friends can work it out.
     
  9. Jun 22, 2009 #8
    @RockFreak,

    What was your friend's reasoning?


    -----
    Assaf
    http://www.physicallyincorrect.com" [Broken]
     
    Last edited by a moderator: May 4, 2017
  10. Jun 24, 2009 #9
    there was no one at the party of course!
     
  11. Jun 24, 2009 #10
    How are you so sure about that and how did you work that out?
     
  12. Jun 24, 2009 #11
    lol. suppose no one was at the party. then all of the hypothesis hold vacuously. i don't claim that this is a unique solution, and most likely not the intended one.
     
  13. Jun 24, 2009 #12
    100 is correct. Here is another way to do it. Say there are n people. Invent a matrix A to describe knowing each other. Write a_{ij} for the entry in row i column j of matrix A. Define A as follows: a_{ii} = 0; for i and j different, if i knows j, then a_{ij} = 1; if i does not know j, then a_{ij} = 0. Note A is symmetric. Let B = A^2 be the matrix multiplied by itself. Let u be the column vector of all 1s.

    (1) "each person knows exactly 22 others" ... this translates to Au = 22u ... in linear algebra language, 22 is an eigenvalue of A, with eigenvector u . As a consequence, 22^2 is an eigenvalue of B, also with eigenvector u.

    (2) "For any pair of people who knew one another, there was no other person at the party that they both knew." ... this translates to: if i and j are different indices, and if a_{ij} = 1, then b_{ij} = 0. That is by the rule for multiplying matrices.

    (3) "For any pair of people who did not know one another, there were
    exactly 6 other people that they both knew." ... this translates to: if i and j are different indices, and if a_{ij} = 0, then b_{ij} = 6.

    (1') From (1) note that b_{ii} = 22.

    So in the matrix B, each row has:
    1 entry equal to 22
    22 entries equal to 0
    n-23 entries equal to 6
    So Bu = (22+6(n-23))u . As noted before, Bu = 22^2 u . Since u is not the zero vector, we conclude 22^2 = 22 + 6(n-23) . Solve for n to get n = 100 .
     
  14. Jun 24, 2009 #13

    rock.freak667

    User Avatar
    Homework Helper

    I can't remember, I was told over facebook and they don't save the chatlogs, so I don't know how to get back the reply.


    To those who got 100, it does seem reasonable. But I couldn't even begin the question so my hat is off to you :approve:


    EDIT:

    I don't understand how you made this matrix and why u is a column vector of all 1s
     
  15. Jun 24, 2009 #14
    Amazing solution, thanks for sharing it.

    So is squaring the "connections matrix A" a common trick in graph theory? What sort of things can you learn from it?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Brain teaser I can't get out
  1. Brain Teaser (Replies: 7)

  2. Brain teaser (Replies: 1)

  3. Brain Teaser (Replies: 6)

Loading...