wu :: forums
wu :: forums - Barely compatible gatherings

Welcome, Guest. Please Login or Register.
Jan 19th, 2022, 12:34pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: SMQ, towr, Icarus, Eigenray, Grimbal, william wu)
   Barely compatible gatherings
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Barely compatible gatherings  (Read 1026 times)
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Barely compatible gatherings  
« on: Jun 6th, 2008, 9:06pm »
Quote Quote Modify Modify

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)
IP Logged
Obob
Senior Riddler
****





   


Gender: male
Posts: 489
Re: Barely compatible gatherings  
« Reply #1 on: Jun 7th, 2008, 3:16pm »
Quote Quote Modify Modify

In graph-theoretic terms, there are only finitely many regular graphs of girth => 5 and diameter <= 2.
« Last Edit: Jun 7th, 2008, 3:26pm by Obob » IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Barely compatible gatherings  
« Reply #2 on: Jun 8th, 2008, 11:21am »
Quote Quote Modify Modify

Here is an attempt
 

 
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.
 
« Last Edit: Jun 8th, 2008, 11:35am by Aryabhatta » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Barely compatible gatherings  
« Reply #3 on: Jun 9th, 2008, 1:27am »
Quote Quote Modify Modify

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.
IP Logged
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Re: Barely compatible gatherings  
« Reply #4 on: Jun 9th, 2008, 2:50pm »
Quote Quote Modify Modify

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.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board