wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Barely compatible gatherings
        
(Message started by: ecoist on Jun 6^th, 2008, 9:06pm)

Title: Barely compatible gatherings
Post by ecoist on Jun 6^th, 2008, 9:06pm

A barely compatible gathering of people, BCP, is a set of people with the following properties.

1) Every person in the set is friends with the same number, k, of people in the set.
2) If person a is not friends with person b, then a and b have exactly one friend in common in the set. If a and b are friends, then a and b have no friend in common in the set.

Show that there are only a finite number of integers n such that there exists a barely compatible gathering of n people.

Examples.
n=2. Two friends.

n=5. People equal the vertices of a pentagon. Two vertices are friends if they are adjacent.

n=10. People equal the ten 2-subsets of {1,...,5}. Two 2-subsets are friends if they are disjoint. (The Petersen graph)

Title: Re: Barely compatible gatherings
Post by Obob on Jun 7^th, 2008, 3:16pm

In graph-theoretic terms, [hide]there are only finitely many regular graphs of girth => 5 and diameter <= 2.[/hide]

Title: Re: Barely compatible gatherings
Post by Aryabhatta on Jun 8^th, 2008, 11:21am

Here is an attempt

[hide]

Let A be the adjacency matrix of the graph.

Then we can easily see that

A^2 + A = (k-1)I + J, where J is the all ones matrix.

now if s is an eigenvalue of A with eigenvector x, then we have that

[s^2 + s - (k-1)] x = Jx.

Thus we have that either s = k (in which case x is [1 1 ... 1]) or 2s = -1 +- sqrt(4k-3) (roots of s^2 + s - (k-1) = 0)

We can also show that the multiplicity of the eigenvalue k is 1. (true for any regular graph of degree k)

So since trace of A is zero, for some integers P and Q we must have that

P (-1 + sqrt(4k-3)) + Q(-1 - sqrt(4k-3)) + k = 0.

i.e
-k + P + Q = (P-Q) sqrt(4k-3)

We also have the P+Q = n-1 = k^2 (the eigenvalue corresponding to [1 1 ... 1] of A^2 is n-1, and must be square of corresponding for A, which is k)

So P-Q = (-k + k^2)/sqrt(4k-3)

Thus we must have that 4k-3 = t^2 for some integer t.

and that k(k-1)/t is an integer.

Thus we have that

(t^2+3)(t^2-1)/16t is an integer.

Thus we have that (t^4 + 2t^2 -3)/t is also an integer. (Mutiply by 16 and expand the numberator)

Thus t divides 3.

Hence there are only a finite number of such k.

[/hide]

Title: Re: Barely compatible gatherings
Post by Eigenray on Jun 9^th, 2008, 1:27am

Very close...but you're missing a factor of 2 in the trace equation.

Here is a similar problem:

There are n>3 people such that any two of them have exactly one common friend. Show that there is one person who is friends with everybody else.

Title: Re: Barely compatible gatherings
Post by ecoist on Jun 9^th, 2008, 2:50pm

If I'm not mistaken, eigenray, your problem is known as the Friendship Theorem. I learned of this problem in the form: if there are n people with the property that any two of them have exactly one friend in common, then Dale Carnegie is there. Eons ago Dale Carnegie wrote a book entitled "How to Win Friends and Inflluence People". About a year ago I saw online a purely combinatorial proof of the Friendship Theorem.