Friendly Mathematicians

[BMAD]

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.

 

 

[bonanova]

Now that I have a solution I can say, what a pretty problem!

 

For n mathematicians,

First we make an observation. Any mathematician that lacks friends altogether can dine in either room without affecting the outcome of the problem. Say there are s such strangers. They have 2^s placements. That number simply multiplies the number of non-s placements, allowing us to focus just on them. This is a nice simplification.

Make a complete n-graph, with n(n-1)/2 edges, and color each edge red or blue. Red edges are friendships; blue edges are strangerships. Erase all the blue edges. They don't matter. Draw a continuous green line that cuts (removes) some of the red edges in such a way that, in the resulting two sets of disjoint graphs, all nodes have even valence. The number of ways of doing this must be shown to be a power of 2.

To clarify, when a red edge is cut (removed) by the green line, its two nodes (mathematicians) are placed in opposite rooms. That is, the green line represents the wall between the two dining rooms. Nodes with even valences represent mathematicians dining with an even number of friends. We rule out any cut that prevents forming sets of graphs with only even valences.

 

When an edge is cut, there are two cases:

1. One of the edge's nodes has already been placed.
   The cut places the other node in the opposite room.
   (1 = 2⁰ options)
    
2. Neither of the edge's nodes has already been placed.
   The nodes are placed either in rooms (A, B) or (B, A), respectively.
   (2 = 2¹ options)

Both cases involve a multiplicative factor that is a power of 2.

The 2^s placements of the s strangers multiplies a subsequent series of 2⁰ or 2¹ choices that secures an even valence for all nodes.

The total number of placements is thus a power of 2.

 

For n mathematicians there are 2ⁿ placements. Constraining a mathematician to a room divides the number of placements by 2. Securing a placement in which each mathematician dines with an even number of friends involves assigning a room to a number f of mathematicians. (Cutting f red edges.) The number of such placements is 2^n-f.