Difference between revisions of "2008 USAMO Problems/Problem 6"

Latest revision as of 13:37, 11 July 2016

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$ ).

Solutions

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.

Solution 3

Let $n$ be the number of participants at the conference. We proceed by induction on $n$ .

If $n = 1$ , then we have one participant who can eat in either room; that gives us a total of $2 = 2^1$ options.

Let $n\geq 2$ . The case in which some participant, $P$ , has no friends is trivial. In this case, $P$ can eat in either of the two rooms, so the total number of ways to split $n$ participants is twice as many as the number of ways to split $(n - 1)$ participants besides the participant $P$ . By induction, the latter number is a power of two, $2^k$ , hence the number of ways to split $n$ participants is $2\times 2^k = 2^{k+1}$ , also a power of two. So we assume from here on that every participant has at least one friend.

We consider two different cases separately: the case when some participant has an odd number of friends, and the case when each participant has an even number of friends.

Claim: Some participant, $Z$ , has an odd number of friends.

Remove $Z$ from consideration and for each pair $(X,Y)$ of $Z$ 's friends, reverse the relationship between $X$ and $Y$ (from friends to strangers or vice versa).

Claim. The number of possible seatings is unchanged after removing $Z$ and reversing the relationship between $X$ and $Y$ in each pair $(X,Y)$ of $Z$ 's friends.

Proof of the claim. Suppose we have an arrangement prior to $Z$ 's departure. By assumption, $Z$ has an even number of friends in the room with him.

If this number is 0, the room composition is clearly still valid after $Z$ leaves the room.

If this number is positive, let $X$ be one of $Z$ 's friends in the room with him. By assumption, person $X$ also has an even number of friends in the same room. Remove $Z$ from the room; then $X$ will have an odd number of friends left in the room, and there will be an odd number of $Z$ 's friends in this room besides $X$ . Reversing the relationship between $X$ and each of $Z$ 's friends in this room will therefore restore the parity to even.

The same reasoning applies to any of $Z$ 's friends in the other dining room. Indeed, there will be an odd number of them in that room, hence each of them will reverse relationships with an even number of individuals in that room, preserving the parity of the number of friends present.

Moreover, a legitimate seating without $Z$ arises from exactly one arrangement including $Z$ , because in the case under consideration, only one room contains an even number of $Z$ 's friends.

End Claim

Thus, we have to double the number of seatings for $(n - 1)$ participants which is, by the induction hypothesis, a power of 2. Consequently, for $n$ participants we will get again a power of 2 for the number of different arrangements.

Case 2: Each participant has an even number of friends.

In this case, each valid split of participants in two rooms gives us an even number of friends in either room.

Let $(A,B)$ be any pair of friends. Remove this pair from consideration and for each pair $(C,D)$ , where $C$ is a friend of $A$ and $D$ is a friend of $B$ , change the relationship between $C$ and $D$ to the opposite; do the same if $C$ is a friend of $B$ and $D$ is a friend of $A$ . Note that if $C$ and $D$ are friends of both $A$ and $B$ , their relationship will be reversed twice, leaving it unchanged.

Consider now an arbitrary participant $X$ different from $A$ and $B$ and choose one of the two dining rooms. [Note that in the case under consideration, the total number of participants is at least 3, so such a triplet $(A, B; X)$ can be chosen.] Let $A$ have $m$ friends in this room and let $B$ have $n$ friends in this room; both $m$ and $n$ are even. When the pair $(A, B)$ is removed, $X$ 's relationship will be reversed with either $n$ , or $m$ , or $m + n - 2k$ (for $k$ the number of mutual friends of $A$ and $B$ in the chosen room), or 0 people within the chosen room (depending on whether he/she is a friend of only $A$ , only $B$ , both, or neither). Since $m$ and $n$ are both even, the parity of the number of $X$ 's friends in that room will be therefore unchanged in any case.

Again, a legitimate seating without $A$ and $B$ will arise from exactly one arrangement that includes the pair $(A, B)$ : just add each of $A$ and $B$ to the room with an odd number of the other's friends, and then reverse all the relationships between a friend of $A$ and a friend of $B$ . In this way we create a one-to-one correspondence between all possible seatings before and after the $(A,B)$ removal.

Since the number of arrangements for $n$ participants is twice as many as that for $(n - 2)$ participants, and that number for $(n - 2)$ participants is, by the induction hypothesis, a power of 2, we get in turn a power of 2 for the number of arrangements for $n$ participants. The problem is completely solved.

Solution 4 (proving only existence of solution)

By induction on the number of mathematicians, assuming solution exists for $n\leq k$ mathematicians. For $n=k+1$ mathematicians, if each of them has even degree then we're done. Otherwise, let $v$ be a node with odd degree, and denote its neighbors by $N(v)$ . We form a new graph $G'$ by deleting $v$ and flipping all edges between members of $N(v)$ . That is, for each pair of $a$ and $b$ in $N(v)$ , they're connected in $G'$ if and only if they're not in $G$ . By induction we know a solution $S'$ exists for $G'$ , and it is easily verifiable that the similar solution $S$ exists in $G$ by adding $v$ to the side in $S'$ with even number of neighbors in $N(v)$ .

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

@@ Line 67: / Line 67: @@
 Since the number of arrangements for <math>n</math> participants is twice as many as that for <math>(n - 2)</math> participants, and that number for <math>(n - 2)</math> participants is, by the induction hypothesis, a power of 2, we get in turn a power of 2 for the number of arrangements for <math>n</math> participants. The problem is completely solved.
+=== Solution 4 (proving only existence of solution) ===
+By induction on the number of mathematicians, assuming solution exists for <math>n\leq k</math> mathematicians. For <math>n=k+1</math>  mathematicians, if each of them has even degree then we're done. Otherwise, let <math>v</math> be a node with odd degree, and denote its neighbors by <math>N(v)</math>. We form a new graph <math>G'</math> by deleting <math>v</math> and flipping all edges between members of <math>N(v)</math>. That is, for each pair of <math>a</math> and <math>b</math> in <math>N(v)</math>, they're connected in <math>G'</math> if and only if they're not in <math>G</math>. By induction we know a solution <math>S'</math> exists for <math>G'</math>, and it is easily verifiable that the similar solution <math>S</math> exists in <math>G</math> by adding <math>v</math> to the side in <math>S'</math> with even number of neighbors in <math>N(v)</math>.
 {{alternate solutions}}

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

Page

Toolbox

Search