Problem:
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:
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: 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, Z, 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 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.
This problem was suggested by Sam Vandervelde.
The problems on this page are the property of the MAA's American Mathematics Competitions