wu :: forums - Print Page


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

        riddles >> hard >> Math Conference Dining Rooms
        
(Message started by: william wu on May 5^th, 2008, 7:06pm)

Title: Math Conference Dining Rooms
Post by william wu on May 5^th, 2008, 7:06pm

From the recent USAMO 2008:

At a certain mathematical conference, every pair of mathematicians are either friends or strangers. At mealtime, every participant eats in one of two large dining rooms. Each mathematician insists upon eating in a room which contains an even number of his or her friends. Prove that the number of ways that the mathematicians may be split between the two rooms is a power of two.

Title: Re: Math Conference Dining Rooms
Post by Eigenray on May 5^th, 2008, 9:03pm

Interesting. I think the hard part is to show that there is at least one solution.

This could fail in two ways, for stupid values of 'friend':

Self-friendship, e.g., A is friends with himself, but there are no other friends.

Non-symmetric, e.g., everybody has A and B as a friend, but there are no other friends (for at least 3 people).

But if friendship is symmetric, and there are no self-friends, it looks like there is always a solution.

Title: Re: Math Conference Dining Rooms
Post by Eigenray on May 5^th, 2008, 10:49pm

Here is a non-constructive proof:
[hideb]Everything here is mod 2. Let A be the friendship matrix. If v_i = 0 or 1 is the room person i belongs to, then the number of friends of person i in the same room is

v_ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif A_ijv_j + (1-v_i)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifA_ij(1-v_j)
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifA_ij (1+v_i+v_j)
= s_i + s_iv_i + (Av)_i,

where s_i is the sum of the i-th row of A. Letting S be the diagonal matrix on s, we need to find a vector v such that (A+S)v = s. So if there exists one solution, any two solutions differ by an element of the null space of (A+S). Since this is a vector space over the field of 2 elements, its order is a power of 2.

To show there exists a solution, we show that rank(A+S) = rank([A+S; s]) by showing that (A+S) and [A+S; s] have the same left null space. Since A,S are symmetric, this is equivalent to showing that Aw = Sw implies <w,s>=0.

Suppose Aw=Sw, and let W = { i : w_i = 1}. Then for each i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/notin.gif W,
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{{jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifW}} A_ij = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_j A_ijw_j = (Aw)_i = (Sw)_i = s_iw_i = 0.

So in particular http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{{ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/notin.gifW; jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifW}} A_ij = 0. And since A is symmetric, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{{ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifW; jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifW}} A_ij = 0. Therefore

0 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{{ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifW; jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifW}} A_ij + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{{ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/notin.gifW; jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifW}} A_ij
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{{i; jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifW}} A_ij
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_j w_js_j,

as required.[/hideb]

Title: Re: Math Conference Dining Rooms
Post by Aryabhatta on May 5^th, 2008, 11:17pm

Almost the same thing I think (it was a long time ago, so I might be mistaken)

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1096040444;

Title: Re: Math Conference Dining Rooms
Post by Eigenray on May 6^th, 2008, 12:06am

Aha, yes, it's actually equivalent to the hint you posted [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1096040444;#4]here[/link].

But we can also use 'Proposition 1' [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1096040444;#3]here[/link] to finish the proof: (A+S)v = s has a solution, because s is the diagonal of A+S.