How Many People Were at the Party with Unique Acquaintances?

  • Thread starter rock.freak667
  • Start date
  • Tags
    Brain
In summary, the conversation discusses a math problem where at a party, each person knows exactly 22 others and for any pair of people who knew one another, there was no other person at the party that they both knew. It is deduced that there were 100 people at the party. Another method of solving the problem is by creating a matrix to represent the connections between people and using the fact that the matrix squared will have certain properties, such as having 22 as an eigenvalue. This method is commonly used in graph theory.
  • #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?
 
Mathematics news on Phys.org
  • #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"
 
Last edited by a moderator:
  • #3
ozymandias said:
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
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"
 
Last edited by a moderator:
  • #5
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
the person who gave it to me doesn't know the answer. But he got 84.
 
  • #7
oh ok ill try and see if me and my friends can work it out.
 
  • #8
@RockFreak,

What was your friend's reasoning?


-----
Assaf
http://www.physicallyincorrect.com"
 
Last edited by a moderator:
  • #9
there was no one at the party of course!
 
  • #10
How are you so sure about that and how did you work that out?
 
  • #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.
 
  • #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 .
 
  • #13
ozymandias said:
@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:

g_edgar said:
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
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?
 

FAQ: How Many People Were at the Party with Unique Acquaintances?

What is a brain teaser?

A brain teaser is a problem or puzzle that requires critical thinking and problem-solving skills to solve. It usually involves a scenario or question that may seem confusing or illogical at first, but has a logical solution.

How can brain teasers help improve brain function?

Brain teasers can help improve brain function by stimulating the brain and challenging it to think in new and creative ways. They can also improve memory, concentration, and cognitive abilities.

Why can't I solve this brain teaser?

There could be a variety of reasons why you are having difficulty solving a brain teaser. It could be that the problem is particularly challenging or that you are approaching it from the wrong angle. Taking a break and coming back to it with a fresh mind may also help.

Are brain teasers only for geniuses?

No, brain teasers are for everyone! They are a fun and engaging way to exercise your brain and improve critical thinking skills. Anyone can solve brain teasers with practice and patience.

How can I use brain teasers in my daily life?

There are many ways to incorporate brain teasers into your daily life. You can solve them during breaks at work or school, play brain teaser games with friends and family, or even use them as a warm-up activity before tackling more challenging tasks.

Similar threads

Replies
10
Views
647
Replies
1
Views
2K
Replies
7
Views
3K
Replies
10
Views
2K
Replies
2
Views
1K
Replies
5
Views
1K
Replies
1
Views
2K
Replies
44
Views
4K
Back
Top