|
|
USAMO 2008 #6
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 (i.e., is of the form $ 2^k$ for some positive integer $k$).
(Aops, Jacob Steinhardt)
Make the obvious re-interpretation as a graph. Let $ f : G \to \{0,1\}$ be an indicator function with $ f(v) = 0$ if a vertex is in the first partition and $ f(v) = 1$ otherwise (this corresponds, in the actual problem, to putting a mathematician in the first or second room). Then look at $ f$ as a function into the field with two elements, $ F_2$. Let $ V$ be the vector space of all such functions. Define the linear operator $ A : V \to V$ as
$ (Af)(v) = \sum_{v \sim w} f(v) - f(w)$
where $ \sim$ denotes adjacency. (Note that we can also think of $ A$ as a matrix, which is essentially the adjacency matrix where the diagonal is changed to be $ 1$ whenever the degree is odd; in more technical terms, it is the Laplacian of $ G$ over $ F_2$). Then $ f$ is a valid partition iff $ (Af)(v) = d(v)$, where $ d$ is the degree of $ v$, for all $ v$ (this is taken over $ F_2$). So we want all solution to $ Af = d$. Note that if $ Af = d, Ag = d$, then $ A(f - g) = 0$, so $ f - g$ is in the nullspace. Thus in particular the number of solutions, if non-zero, is the size of the nullspace of $ A$, which is $ 2^{dim(Null(A))}$ by considering all linear combinations of any basis of $ Null(A)$ over $ F_2$. Also let $ i$ be such that $ i(v) = 1$ for all $ v$. Then clearly $ Ai = 0$, so $ dim(Null(A)) > 0$, establishing that the number of ways to do this is $ 2^k$, $ k > 0$. Thus we need only prove the existence of a solution.
Since we can add a new vertex connected to exactly one previously existing vertex without changing the problem, WLOG all vertices have odd degree. Then we want to show that $ i \in Col(A)$. But it is a well-known fact in linear algebra that $ Col(A) = Null(A^T)^{\perp} = Null(A)^{\perp}$ since $ A$ is symmetric. Thus we need to show that if $ f \in Null(A)$, $ f$ is perpendicular to $ i$ and we will be done. So let $ f \in Null(A)$. Take the submatrix of $ A$ consisting of the rows and columns $ v$ such that $ f(v) = 1$. Then, since $ f \in Null(A)$, the sum of each row in this submatrix must be $ 0$ in $ F_2$. Thus the total number of $ 1$s in this submatrix is even. But since it is symmetric, the total number of $ 1$s off of the diagonal is even, so the total number of $ 1$s on the diagonal is even. But since every vertex has odd degree, the entire diagonal of $ A$ consists of $ 1$s, so this says that the size of the diagonal of this submatrix is even. But this is also the number of $ v$ such that $ f(v) = 1$, so $ f(v) = 1$ for an even number of $ v$, thus is perpendicular to $ i$, and we have our result. |
|
