2008 USAMO Problems/Problem 6

Problem

(Sam Vandervelde) 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$ ).

Solution

Solution 1 (linear algebra)

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, without loss of generality 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.

Solution 2 (group theory)

Define an order to be a set of instructions, one instruction given to each mathematician. Each mathematician is told to either move or to stay (we can think of this as stay is $0$ , and move is $1$ ). Now take some good configuration. Consider the set of all orders which, when performed on this configuration, give us another good configuration. Note the identity order, $(0, 0, \ldots, 0)$ , is in this set. We claim this set is an abelian group under composition.

Proof: Clearly each is its own inverse, there is the identity, and the operation is clearly associative and commutative (because it's equivalent to addition of n-dimensional vectors $\mod{2}$ ). So it suffices to show this set of orders is closed under composition.

Consider any mathematician. If, in one of these orders, he is told to stay, then the number of his friends who are told to move must be even. Similarly, if he is told to move, then the number of his friends who are told to stay must be even. Now just consider two orders $A$ and $B$ and you can show that in $A \times B$ the same property will hold using parity.

Now that we've shown it is a group (which we will call $G$ ), we'll prove it has order two. Let $I$ be the identity.

Let $\{I, T_1\} = H_1$ , where $T$ is some element of $G$ . Now pick an element $T_2$ of $G$ which is not in $H_1$ . Notice that because the elements of $H_1$ are distinct, the elements of $\{T_2X|X \in H_1\}$ are distinct (if two elements of that set were the same, multiply by each on the right by $T_2^{ - 1}$ and you have a contradiction). Now notice that for any $A, B \in H_1$ , if we were to have $T_2A = B$ , then $T_2 = BA^{ - 1} \in H_1$ . Therefore, $H_1$ and $\{T_2X|X \in H_1\}$ are disjoint and of the same size. Moreover, the product of any element in the first group and any element in the second group is a member of the second group. Therefore, these two groups together form a group of order $2^2$ . Call this $H_2$ . You progressively build larger and larger subgroups of $G$ until you get to $G$ itself, whose order must then be a power of two. Therefore, the number of good configurations of the mathematicians was a power of two.

This, of course, was all assuming $I$ existed and was in the group.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

2008 USAMO (Problems • Resources)
Preceded by Problem 5	Followed by Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2008 USAMO Problems/Problem 6

Problem

Contents

Solution

Solution 1 (linear algebra)

Solution 2 (group theory)

See Also