I've been aware of this problem for a few years, but never had any clue how to approach it. A couple of days ago, it suddenly occurred to me that group theory can come handy in this case. With quite some effort, I finally got it!
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.
Proof:
The group theory part is not too hard once we realize this is the direction. Let $V$ be the set of mathematicians, or nodes. Every operation of moving a subset $x$ of $V$ to the opposite room is actually an element of a group on $\{0,1\}^{|V|}$, which we call $g(x)$. So $2^{|V|}$, the total number of different $x$, is the product of the total number of distinct $g(x)$ and the number of $x$ such that $g(x)=0$, meaning there are $2^k$ distinct $x$ such that $g(x)=0$. We can get the same conclusion from linear algebra as well.
The far more interesting part is then to show that there is indeed at least a way to split the mathematicians between the two rooms. By induction on $|V|$, if all nodes have even degree then we're done. Otherwise, pick a node $v$ with odd degree. Build a new graph $G'$ by deleting $v$ and reversing all friendships among $N(v)$, the friends of $v$. By induction there's a way $S'$ to split $G'$ as desired, and now we only to add $v$ back to the side of $S'$ where he or she has even number of friends. The spilt $S$ obtained this way has $v$ and $N(v)$ fulfilled, and we're done.
Q.E.D.
No comments:
Post a Comment