# Brain teaser I can't get out

1. Jun 19, 2009

### rock.freak667

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. Jun 20, 2009

### ozymandias

Curses, you've infected me with this now too!

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
3. Jun 20, 2009

### rock.freak667

Sorry, I don't have the answer...I didn't even know how to begin to solve this

4. Jun 20, 2009

### ozymandias

Argh, the suspense ... can you ask the person who gave you this question? I've got to know the answer!

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
5. Jun 20, 2009

### angak001

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

6. Jun 22, 2009

### rock.freak667

the person who gave it to me doesn't know the answer. But he got 84.

7. Jun 22, 2009

### angak001

oh ok ill try and see if me and my friends can work it out.

8. Jun 22, 2009

### ozymandias

@RockFreak,

-----
Assaf
http://www.physicallyincorrect.com" [Broken]

Last edited by a moderator: May 4, 2017
9. Jun 24, 2009

### matticus

there was no one at the party of course!

10. Jun 24, 2009

### angak001

How are you so sure about that and how did you work that out?

11. Jun 24, 2009

### matticus

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. Jun 24, 2009

### g_edgar

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. Jun 24, 2009

### rock.freak667

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

EDIT:

I don't understand how you made this matrix and why u is a column vector of all 1s

14. Jun 24, 2009

### ozymandias

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?