2008 USAMO Problems/Problem 6
(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 for some positive integer ).
Solution 1 (linear algebra)
Make the obvious re-interpretation as a graph. Let be an indicator function with if a vertex is in the first partition and otherwise (this corresponds, in the actual problem, to putting a mathematician in the first or second room). Then look at as a function into the field with two elements, . Let be the vector space of all such functions. Define the linear operator as
where denotes adjacency. (Note that we can also think of as a matrix, which is essentially the adjacency matrix where the diagonal is changed to be whenever the degree is odd; in more technical terms, it is the Laplacian of over ). Then is a valid partition iff , where is the degree of , for all (this is taken over ). So we want all solution to . Note that if , then , so is in the nullspace. Thus in particular the number of solutions, if non-zero, is the size of the nullspace of , which is by considering all linear combinations of any basis of over . Also let be such that for all . Then clearly , so , establishing that the number of ways to do this is , . 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 . But it is a well-known fact in linear algebra that since is symmetric. Thus we need to show that if , is perpendicular to and we will be done. So let . Take the submatrix of consisting of the rows and columns such that . Then, since , the sum of each row in this submatrix must be in . Thus the total number of s in this submatrix is even. But since it is symmetric, the total number of s off of the diagonal is even, so the total number of s on the diagonal is even. But since every vertex has odd degree, the entire diagonal of consists of s, so this says that the size of the diagonal of this submatrix is even. But this is also the number of such that , so for an even number of , thus is perpendicular to , 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 , and move is ). 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, , 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 ). 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 and and you can show that in the same property will hold using parity.
Now that we've shown it is a group (which we will call ), we'll prove it has order two. Let be the identity.
Let , where is some element of . Now pick an element of which is not in . Notice that because the elements of are distinct, the elements of are distinct (if two elements of that set were the same, multiply by each on the right by and you have a contradiction). Now notice that for any , if we were to have , then . Therefore, and 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 . Call this . You progressively build larger and larger subgroups of until you get to 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 existed and was in the group.
Let be the number of participants at the conference. We proceed by induction on .
If , then we have one participant who can eat in either room; that gives us a total of options.
Let . The case in which some participant, , has no friends is trivial. In this case, can eat in either of the two rooms, so the total number of ways to split participants is twice as many as the number of ways to split participants besides the participant . By induction, the latter number is a power of two, , hence the number of ways to split participants is , 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, , has an odd number of friends.
Remove from consideration and for each pair of 's friends, reverse the relationship between and (from friends to strangers or vice versa).
Claim. The number of possible seatings is unchanged after removing and reversing the relationship between and in each pair of 's friends.
Proof of the claim. Suppose we have an arrangement prior to 's departure. By assumption, has an even number of friends in the room with him.
If this number is 0, the room composition is clearly still valid after leaves the room.
If this number is positive, let be one of 's friends in the room with him. By assumption, person also has an even number of friends in the same room. Remove from the room; then will have an odd number of friends left in the room, and there will be an odd number of 's friends in this room besides . Reversing the relationship between and each of 's friends in this room will therefore restore the parity to even.
The same reasoning applies to any of '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 arises from exactly one arrangement including , because in the case under consideration, only one room contains an even number of 's friends.
Thus, we have to double the number of seatings for participants which is, by the induction hypothesis, a power of 2. Consequently, for 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 be any pair of friends. Remove this pair from consideration and for each pair , where is a friend of and is a friend of , change the relationship between and to the opposite; do the same if is a friend of and is a friend of . Note that if and are friends of both and , their relationship will be reversed twice, leaving it unchanged.
Consider now an arbitrary participant different from and 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 can be chosen.] Let have friends in this room and let have friends in this room; both and are even. When the pair is removed, 's relationship will be reversed with either , or , or (for the number of mutual friends of and in the chosen room), or 0 people within the chosen room (depending on whether he/she is a friend of only , only , both, or neither). Since and are both even, the parity of the number of 's friends in that room will be therefore unchanged in any case.
Again, a legitimate seating without and will arise from exactly one arrangement that includes the pair : just add each of and to the room with an odd number of the other's friends, and then reverse all the relationships between a friend of and a friend of . In this way we create a one-to-one correspondence between all possible seatings before and after the removal.
Since the number of arrangements for participants is twice as many as that for participants, and that number for participants is, by the induction hypothesis, a power of 2, we get in turn a power of 2 for the number of arrangements for participants. The problem is completely solved.
Solution 4 (proving only existence of solution)
By induction on the number of mathematicians, assuming solution exists for mathematicians. For mathematicians, if each of them has even degree then we're done. Otherwise, let be a node with odd degree, and denote its neighbors by . We form a new graph by deleting and flipping all edges between members of . That is, for each pair of and in , they're connected in if and only if they're not in . By induction we know a solution exists for , and it is easily verifiable that the similar solution exists in by adding to the side in with even number of neighbors in .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
- <url>viewtopic.php?t=202908 Discussion on AoPS/MathLinks</url>
|2008 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|