BrainDen.com - Brain Teasers
• 0

# Friendly Mathematicians

## Question

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.

• 1

## Recommended Posts

• 0

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 2s 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 = 20 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 = 21 options)

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

The 2s placements of the s strangers multiplies a subsequent series of 20 or 21 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 2n 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 2n-f.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.