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 ).
(This problem was suggested by Sam Vandervelde.)
Solutions — 2
Solution 1
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 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.
Case 1: 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. 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 of 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 2
Let be the number of mathematicians. Represent the problem as a graph , with vertices and edges representing mathematicians and friendships, respectively. We seek partitions such that in each induced subgraph , every vertex has even degree.
Label the vertices , and let be the degree of . Let the notation indicate adjacency in the graph. We introduce , an matrix over the finite field . For every , let the entry if , and 0 otherwise. On the diagonal, let each equal modulo 2 (recall that our matrix has elements in ).
Let be the vector with entries equal to the degrees . Consider an vector of variables . We claim that there is a bijective correspondence between the solutions of the matrix equation and the valid partitions of the graph. Indeed, for any solution vector , partition the vertices by putting in if , and in otherwise. It is easy to check that if and only if this is a valid partition.
Basic linear algebra tells us that the number of solutions of is either 0 or a power of . Therefore, it remains to show that there is at least one solution. In fact, this is precisely the statement of Gallai's Cycle-Cocycle Partition Theorem (c.f. Exercise 1.35 in Graph Theory, by Reinhard Diestel, Problem 5.17 in Combinatorial Problems and Solutions, by László Lovász, with solution on page 287 of the second book, or the paper "Simple proofs to three parity theorems," by Yair Caro, published in 1996 in Ars Combinatoria, on pages 175–180 of volume 42).
In the remainder of this solution, we provide an alternate proof of this final existence result. We need to show that is in the column space of . By linear algebra, the column space of is the orthogonal complement of the nullspace of . Therefore, it suffices to show that for every vector in the null space of (i.e., ), we always have .
Consider the submatrix of consisting of the rows and columns for which . Since the diagonal of is , the product is precisely the number of 1's on the diagonal of . Now , so the sum of every row in must be 0 over , hence the total number of 1's in is even. But is symmetric, so it has an even number of off-diagonal 1's. Therefore, indeed has an even number of 1's on its diagonal, so our previous observation implies that over , as desired.