brain teaser I can't get out

[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?

[ozymandias]

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
Physically Incorrect (http://www.physicallyincorrect.com)

[rock.freak667]

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:

[ozymandias]

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
Physically Incorrect (http://www.physicallyincorrect.com)

[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

[rock.freak667]

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

[angak001]

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

[ozymandias]

@RockFreak,

What was your friend's reasoning?


-----
Assaf
Physically Incorrect (http://www.physicallyincorrect.com)

[matticus]

there was no one at the party of course!

[angak001]

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

[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.

[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 .

[rock.freak667]

@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

[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?