Math Puzzle Solution: How Many People are at the Party?
This is a solution to the ‘How Many People are at the Party‘ puzzle.
The party has 100 people.
The intuitive solution reasons as follows: denote by N the number of people at the party.
Pick a person who’s at the party, call him X. X knows 22 people, which we’ll call group A. There is also a group of people X doesn’t know, which we’ll call group B. If we let M stand for the number of people in group B, then N = 1 + 22 + M, so all we have to do is deduce M. To do this, we think not of counting people, but of counting ‘connections’ between people.
Each person in group A knows 22 people. The people in group A can’t know each other or X, because that would violate factoid #2: friends have no mutual acquaintances. Hence, each person in A must know precisely 22 people who are in B. On the other hand, since X doesn’t know anyone in B they must have 6 mutual friends, which can only be in group A (had they been in B that would mean X knows people in B, which is contrary to assumption). This means that each person in B must know precisely 6 people in A.
So, what do we have? 22*21 connections going from A to B, and 6*M connections going from B to A:
These numbers must equal each other, so 6M=22*21, or M=73, which yields N=1+22+M=100, which is the number of people at the party.
One can approach the same problem using the more formal notion of adjacency matrices, used in graph theory. This solution was suggested by the user g_edgar over at physicsforums. Think of the people at the party as the vertices of a graph, and draw an edge between two people that know each other. Now form a matrix A, with Aij = 1 if i and j have an edge between them and 0 otherwise (Aii = 0 in this problem, because there are no edges from i to itself). By studying this matrix and its eigenvalues you can deduce the number of people at the party (number of vertices). This approach is known as spectral graph theory. In particular,let u=(1,1,1,. …, 1) be the vector of all 1s. Au will give you a vector, and its j-th component (Au)_j will count how many people each person knows. Here’s a simple example:
In our problem, we know this to be 22, so Au=22u. Hence 22 is an eigenvalue of A. You can see how our knowledge can be translated into very precise tidbits of information.
Taking the square of the adjacency matrix will yield a matrix B=A^2 which has nonzero values only for those entries which have a “distance” of two edges between them. In our problem, if vertices X and Y have an edge between them (i.e., A and B “know each other”), this means B_{XY} = 0, by factoid #2. In terms of graphs, here’s an example of the sort of thing factoid #2 disallows, and the corresponding squared adjacency matrices:
Notice the diagonals are nonzero. Why (for example) is the diagonal of X = 2? This is because X is connected to itself via 2 edges in a trivial way: X->Y->X and X->Z->X. In short, the diagonals measure the number of friends each vertex has.
B’s eigenvalues must equal the square of A’s eigenvalues, since Bu = (A^2)u = A(Au) = A(22u) = 22 Au = (22^2)u. We can also construct B’s eigenvalues by examining what we know about the party. I won’t go into the details here, but those of you who are interested can consult g_edgar’s post over at physicsforums: here.
