Maths Olympiad Prep

Library / /65 of 169

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it United States

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 2k2^k for some positive integer kk).
(This problem was suggested by Sam Vandervelde.)

Solutions — 2

Solution 1

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

If n=1n = 1, then we have one participant who can eat in either room; that gives us total of 2=212 = 2^1 options.
Let n2n \ge 2. The case in which some participant, PP, has no friends is trivial. In this case, PP can eat in either of the two rooms, so the total number of ways to split nn participants is twice as many as the number of ways to split (n1)(n-1) participants besides the participant PP. By induction, the latter number is a power of two, 2k2^k, hence the number of ways to split nn participants is 2×2k=2k+12 \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.

Case 1: Some participant, ZZ, has an odd number of friends.
Remove ZZ from consideration and for each pair (X,Y)(X, Y) of ZZ's friends, reverse the relationship between XX and YY (from friends to strangers or vice versa).

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

Proof. Suppose we have an arrangement prior to ZZ's departure. By assumption, ZZ has an even number of friends in the room with him.
If this number is 0, the room composition is clearly still valid after ZZ leaves the room.
If this number is positive, let XX be one of ZZ's friends in the room with him. By assumption, person XX also has an even number of friends in the same room. Remove ZZ from the room; then XX will have an odd number of friends left in the room, and there will be an odd number of ZZ's friends in this room besides XX. Reversing the relationship between XX and each of ZZ's friends in this room will therefore restore the parity to even.
The same reasoning applies to any of ZZ'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 ZZ arises from exactly one arrangement including ZZ, because in the case under consideration, only one room contains an even number of ZZ's friends. \square

Thus, we have to double the number of seatings for (n1)(n-1) participants which is, by the induction hypothesis, a power of 2. Consequently, for nn 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)(A, B) be any pair of friends. Remove this pair from consideration and for each pair (C,D)(C, D), where CC is a friend of AA and DD is a friend of BB, change the relationship between CC and DD to the opposite; do the same if CC is a friend of BB and DD is a friend of AA. Note that if CC and DD are friends of both AA and BB, their relationship will be reversed twice, leaving it unchanged.
Consider now an arbitrary participant XX different from AA and BB 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)(A, B; X) can be chosen.] Let AA have mm friends in this room and let BB have nn friends in this room; both mm and nn are even. When the pair (A,B)(A, B) is removed, XX's relationship will be reversed with either nn, or mm, or m+n2km + n - 2k (for kk the number of mutual friends of AA and BB in the chosen room), or 0 people within the chosen room (depending on whether he/she is a friend of only AA, only BB, both, or neither). Since mm and nn are both even, the parity of the number of XX's friends in that room will be therefore unchanged in any case.
Again, a legitimate seating without AA and BB will arise from exactly one arrangement that includes the pair (A,B)(A, B): just add each of AA and BB to the room with an odd number of the other's friends, and then reverse all of the relationships between a friend of AA and a friend of BB. In this way we create a one-to-one correspondence between all possible seatings before and after the (A,B)(A, B) removal.
Since the number of arrangements for nn participants is twice as many as that for (n2)(n - 2) participants, and that number for (n2)(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 nn participants. The problem is completely solved.

Solution 2

Let nn be the number of mathematicians. Represent the problem as a graph GG, with vertices and edges representing mathematicians and friendships, respectively. We seek partitions V0V1V_0 \cup V_1 such that in each induced subgraph G[Vi]G[V_i], every vertex has even degree.
Label the vertices {v1,,vn}\{v_1, \dots, v_n\}, and let did_i be the degree of viv_i. Let the notation vivjv_i \sim v_j indicate adjacency in the graph. We introduce A=(aij)\mathbf{A} = (a_{ij}), an n×nn \times n matrix over the finite field F2={0,1}\mathbb{F}_2 = \{0,1\}. For every iji \neq j, let the entry aij=1a_{ij} = 1 if vivjv_i \sim v_j, and 0 otherwise. On the diagonal, let each aiia_{ii} equal did_i modulo 2 (recall that our matrix has elements in F2\mathbb{F}_2).
Let d\mathbf{d} be the n×1n \times 1 vector with entries equal to the degrees did_i. Consider an n×1n \times 1 vector of variables x\mathbf{x}. We claim that there is a bijective correspondence between the solutions of the matrix equation Ax=d\mathbf{A}\mathbf{x} = \mathbf{d} and the valid partitions of the graph. Indeed, for any solution vector x=(x1,,xn)T\mathbf{x} = (x_1, \dots, x_n)^T, partition the vertices by putting viv_i in V0V_0 if xi=0x_i = 0, and in V1V_1 otherwise. It is easy to check that Ax=d\mathbf{A}\mathbf{x} = \mathbf{d} if and only if this is a valid partition.
Basic linear algebra tells us that the number of solutions of Ax=d\mathbf{A}\mathbf{x} = \mathbf{d} is either 0 or a power of F2=2|\mathbb{F}_2| = 2. 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 d\mathbf{d} is in the column space of A\mathbf{A}. By linear algebra, the column space of A\mathbf{A} is the orthogonal complement of the nullspace of AT\mathbf{A}^T. Therefore, it suffices to show that for every vector y=(y1,...,yn)T\mathbf{y} = (y_1, ..., y_n)^T in the null space of AT\mathbf{A}^T (i.e., ATy=0\mathbf{A}^T\mathbf{y} = 0), we always have yTd=0\mathbf{y}^T\mathbf{d} = 0.
Consider the submatrix B\mathbf{B} of A\mathbf{A} consisting of the rows and columns ii for which yi=1y_i = 1. Since the diagonal of A\mathbf{A} is d\mathbf{d}, the product yTd\mathbf{y}^T\mathbf{d} is precisely the number of 1's on the diagonal of B\mathbf{B}. Now ATy=0\mathbf{A}^T\mathbf{y} = 0, so the sum of every row in B\mathbf{B} must be 0 over F2\mathbb{F}_2, hence the total number of 1's in B\mathbf{B} is even. But B\mathbf{B} is symmetric, so it has an even number of off-diagonal 1's. Therefore, B\mathbf{B} indeed has an even number of 1's on its diagonal, so our previous observation implies that yTd=0\mathbf{y}^T\mathbf{d} = 0 over F2\mathbb{F}_2, as desired.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.