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


which is only possible if k=0, Q.E.D.

PHP Warning

lib/DbaDatabase.php:154: Warning: dba_optimize() [<a href='function.dba-optimize'>function.dba-optimize</a>]: You cannot perform a modification to a database without proper access

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access