Brain teaser I can't get out

  • #1
rock.freak667
Homework Helper
6,223
31
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?
 

Answers and Replies

  • #2
ozymandias
84
0
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:
  • #3
rock.freak667
Homework Helper
6,223
31
Does this make sense? (Do you have the solution?)

Sorry, I don't have the answer...I didn't even know how to begin to solve this :frown:
 
  • #4
ozymandias
84
0
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:
  • #5
angak001
13
0
This looks quite straight forward but when I tried working this out I ended up with a paper full of calculations that don't make sense lol .if you get the answer please i would like to know
 
  • #6
rock.freak667
Homework Helper
6,223
31
the person who gave it to me doesn't know the answer. But he got 84.
 
  • #7
angak001
13
0
oh ok ill try and see if me and my friends can work it out.
 
  • #8
ozymandias
84
0
@RockFreak,

What was your friend's reasoning?


-----
Assaf
http://www.physicallyincorrect.com" [Broken]
 
Last edited by a moderator:
  • #9
matticus
107
1
there was no one at the party of course!
 
  • #10
angak001
13
0
How are you so sure about that and how did you work that out?
 
  • #11
matticus
107
1
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.
 
  • #12
g_edgar
607
0
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 .
 
  • #13
rock.freak667
Homework Helper
6,223
31
@RockFreak,

What was your friend's reasoning?

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:

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.

I don't understand how you made this matrix and why u is a column vector of all 1s
 
  • #14
ozymandias
84
0
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?
 

Suggested for: Brain teaser I can't get out

  • Last Post
Replies
8
Views
688
Replies
3
Views
571
Replies
1
Views
366
Replies
5
Views
286
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
412
  • Last Post
Replies
8
Views
1K
Replies
2
Views
979
Replies
23
Views
979
Top