You're at a party.
induction/party Added material
Problem
You're at a party. Any two (different) people at the party have exactly one friend in common (the friend is also at the party). Prove that there is at least one person at the party who is a friend of everyone else. Assume that the friendship relation is symmetric and not reflexive.
Show solution
The problem can be solved by applying the spectral theory of graphs
(see for instance Bollobas' excellent book, _Extremal Graph Theory_).
The problem's condition is vacuous if there is only N=1 person at the "party",
impossible if N=2 (If you aren't your own friend, nor I mine, somebody *else*
must be our mutual friend), and trivial if N=3 (everybody must be everyone
else's friend). Henceforth assume N>3.
Let A,B be two friends, and C their mutual friend. Let a be the number
of A's friends other than B and C, and likewise b,c. Each of A's friends
is also friendly with exactly one other of A's friends, and with none of
B and C's other friends (if A1,B1 are friends of A,B resp. and of each other
then A1 and B have more than one mutual friend); likewise for B and C.
Let M=N-(a+b+c+3) be the number of people not friendly with any of A,B,C.
Each of them is friendly with exactly one of A's and one of B's friends;
and each pair of a friend of A and a friend of B must have exactly
one of them as a mutual friend. Thus M=ab; likewise M=ab=ac=bc. Thus
either M and two of a,b,c vanish, or a=b=c=k (say), M=k^2, and N=k^3+3k+3.
In the first case, say b=c=0; necessarily a is even, and A is a friend of
everybody else at the party, each of whom is friendly with exactly one other
person; clearly any such configuration (a graph of k/2+1 triangles with a
common vertex) satisfies the problem's conditions).
It remains to show that the second case is impossible. Since N=k^2+3k+3
does not depend on A,B,C, neither does k, and it quickly follows that the
party's friendship graph is regular with reduced matrix
[ 0 k+2 0 ]
[ 1 1 k ]
[ 0 1 k+1 ]
and eigenvalues k+2 and +-sqrt(k+1) and multiplicities 1,m1,m2 for some
*integers* m1 and m2 such that (m1-m2)*sqrt(k+1)=-(k+2) (because the graph's
matrix has trace zero). Thus sqrt(k+1) divides k+2 and k+1 divides
(k+2)^2=(k+1)(k+3)+1
which is only possible if k=0, Q.E.D.
Additional material
[ Editor: the following mail (1994-1995) concerns an inductive proof
that was once in this entry and has since been removed. It read: ]
Here is an easy solution by induction. Let P be the set of people in
the party, and n the size of P. If n=2 or 3, the result is trivial.
Suppose now that n>3 and that the result is true for n-1.
For any two distinct x,y in P, write x & y to mean that `x is a
friend of y', and x ~& y to mean that `x is not a friend of y'.
Take q in P. The hypothesis on the relation & is still satisfied on
P-{q}; by induction, the result is thus true for P-{q}, and there is
some p in P-{q} such that p & x for any x in P-{p,q}. We have two
cases:
a) p & q. Then the result holds for P with p.
b) p ~& q. By hypothesis, there is a unique r in P-{p,q} such that
p & r & q. For any x in P-{p,q}, if x & q, then p & x & q, and so
x=r. Thus r is the unique friend of q. Now for any s in P-{q,r}
there exists some x such that s & x & q, and so x=r. This means
that r & s for any s in P-{q,r}, and as r & q, the results holds in
P with r.
[ Editor: Ron Sommeling <sommel@sci.kun.nl> objected to the sentence
"The hypothesis on the relation & is still satisfied on P-{q}": ]
No, this is wrong.
Let a,b in P-{q} with a and b different. The assumption on the
relation & implies that there is a unique c in P (not equal to a or
b) such that a & c and b & c. BUT this unique c in P could be the
element q, so the assumption on & is NOT true for P-{q}. EVEN
STRONGER: It can never be true for P-{q}. The condition for & on P
can only be true if the number of elements in P is odd. Try
size(P)=5:
a1----a2----a5
| / \ |
| / \ |
| / \ |
| / \ |
a3 a4
Whatever element you take for q (a1,a2,a3,a4 or a5) the assumption
on P-{q} is never satisfied. (If you take q=a1 then a2 and a3 don't
have a common friend in P-{q} any longer.)
If n is odd and n > 3, and if the theorem is true, then there is a party
of n persons that has the "butterfly" shape of your diagram, that is, if
you remove the one person who knows everyone then you partition the
party into two equal subsets that do not know each other at all. To
construct such a party, take two qualifying parties of (n+1)/2 people
each in which the same person knows everyone in both parties, and aside
from that person no other person is in both parties.
-- David A. Karr <karr@cs.cornell.edu>, February 1994
In article <3r0v8d$61e@gap.cco.caltech.edu>, whuang@cco.caltech.edu
(Wei-Hwa Huang) writes:
For every odd positive number, such a network does exist.
(Basically, triangles all joined at one vertex.) However, I cannot
find an arrangement of an even number of people so that each pair of
people has exactly one friend.
In fact, if the claim of the puzzle is true, and if there is a party at
which every two people have exactly one common friend, then there cannot
be an even number of people at the party. There must be an odd number
of people, and their friendship network must be as you described it.
Proof: Suppose that P is a party at which every two people have exactly
one common friend, and assume the puzzle's claim is true. Then there is
at least one person in P who is a friend of everyone else. Pick such a
person, call him or her O. Now take any other person x. x is a friend
of O, and they must have exactly one common friend, call that unique
friend y. Neither x nor y can have any other friends, otherwise they
would have more than one friend in common with O. So x, y, and O form a
triangle, joined to the rest of the party at O and only at O.
It follows that all the party-goers other than O can be paired off, so
there must be an even number of them. So |P| is odd (an even number
plus 1, counting O), and the friendship links form triangles all joined
at one vertex, O.
As others have pointed out, the following step of the "proof" is just
plain wrong:
Take q in P. The hypothesis on the relation & is still satisfied on
P-{q};
One of |P| and |P-{q}| is even, so either the hypothesis is no longer
satisfied on P-{q}, or it was never satisfied on P in the first place.
-- David A. Karr <karr@cs.cornell.edu>, June 1995